New technique : Tuleja's theorem

ChPicard · Posted: Sat Sep 19, 2009 2:06 pm Post subject: New technique : Tuleja's theorem

Hi

Read this article about Tuleja's technique. Very interesting.

http://www.geometer.org/mathcircles/sudoku.pdf

pages 5 to 9.

Best regards

...

evert2 · Posted: Sun Sep 20, 2009 6:03 pm Post subject:

To me it looks like putting the basic sudoku rules in a slightly different way. I can't see what move you could make using this, where none of the existing techniques help you out.

If you have a different opinion on this, enlighten me please.

[edit]Sorry, no it has nothing to do with locked candidates[/edit]

Sudoku-Bob · Posted: Sat Oct 24, 2009 3:25 pm Post subject: Not really a new technique

This really isn't a new technique, but it's rarely mentioned on forums.

A guy named Felix proved this back in 2005. Not sure when Tuleja proved it. I use this technique almost exclusively for first-pass at solving puzzles - Often no need for fishing, x-wing, etc.

Example: USA Today's 4-star puzzle from 10/21/2009 (Wednesday of this week). Difficulty: 4 stars out of 5:

3_5_867_9+
___95____+
__2_3_8__+
2___1_3_8+
__1___6__+
8_3_9___4+
__8_6_2__+
____29___+
5_417_9_3

Rather than keeping track of a candidate grid (1-9) for each of the 81 cells, Felix said that you can keep track of two directions for each cell, based on how that number "travels" across the puzzle or down the puzzle. Using tick marks, you can mark either North or South, as well as either East or West, in each cell. Once your puzzle is solved, you can see that each cell will have 2 tick marks (NE, SE, NW, or SW... never NS or EW). The North and South tick marks tell how that digit travels as you read left to right across the grid. The East and West tick marks tell how that digit travels as you read top to bottom down the grid.

In my USA Today example, above, the digit "9" in r2c4 travels NORTH to r1c9, as you move from block 2 to block 3, (traveling from row 2 to row 1 is North. So mark cells r2c4 and r1c9 (where the digits "9" appear) with a NORTH mark. English readers (like Felix) read left to right, and top to bottom. So as you "read" the grid left to right, the "9" moves North from row 2 to row 1.

"3" is also traveling North, from r1c1 to r3c5, wrapping, of course, since there's no row 0.

However "5" is traveling South from r1c3 to r2c5.

so EVERY "3" and "9" in rows 1-2-3 can be marked with a North tick mark. And EVERY "5" in rows 1-2-3 can be marked with a South tick.

Since at least one digit is traveling North, and at least one is traveling South, you know that the quantity of six will travel one direction (called the "major" direction, or majority direction), and the quantity of three will travel in the other (called the "minor" direction), along those first three rows.

If you ever see two digits traveling in the same direction together, then you know it's the majority direction. (example from puzzle above, The digits 3&8 travel North together (i.e. same row and block), from r6c3 & r6c1, to r4c7 & r4c9. So you KNOW that North is the majority direction in rows 4-5-6.

If you ever see two digits travel in the same direction together, and you have shown that any other digit is traveling in the opposite direction, then you have identified a "floater" (going in the minority direction). You also know that the third cell next to the two traveling together can be marked with the minority mark. (In the above example, this can be shown in the following two steps... your first obvious "fill-in" when solving this puzzle is probably r5c5= "4" (as "4" is the only digit left in column 5), and then you see that "4" is traveling SOUTH from r5c5 to r6c9. Since 8&3 are traveling NORTH together in rows 4-5-6, and "4" is traveling SOUTH, you IMMEDIATELY know that North is a MAJORITY and SOUTH is a minority in rows 4-5-6. So you can mark the unsolved r5c4 and r5c6 with NORTH tick marks (and those are obviously 8-3 or 3-8), but also mark r4c7 and r6c2 with SOUTH tick marks.)

Solve the above puzzle using this technique, and you'll arrive at a point where you can even mark certain unsolved cells with a North, South, East or West tick mark. And then you can see how powerful this technique is. I'm surprised it's not mentioned in forums more, but I read it as "Felix's Directional Technique for Solving Sudoku".

Sometimes all nine digits will travel in the same direction (called a 9-majority). Other times (usually?) six will go one way (majority), three the other (minority).

With Felix's Directional Technique, you can sometimes solve puzzles without having to resort to x-wing, and other fish techniques (although the puzzle, above, doesn't require fishing even if you don't use Felix's technique.)

I'll see if I can locate the paper I found on this technique, and post a link.