The New Sudoku Players' Forum

by **Carcul** » Mon Apr 10, 2006 12:33 pm

The Toughest Known Puzzle

The following puzzle (Puzzle #77 from top1465) is currently considered the toughest known Sudoku puzzle:

Code: Select all: *-----------------------* | 7 . . | . . . | 4 . . | | . 2 . | . 7 . | . 8 . | | . . 3 | . . 8 | . . 9 | |-------+-------+-------| | . . . | 5 . . | 3 . . | | . 6 . | . 2 . | . 9 . | | . . 1 | . . 7 | . . 6 | |-------+-------+-------| | . . . | 3 . . | 9 . . | | . 3 . | . 4 . | . 6 . | | . . 9 | . . 1 | . . 5 | *-----------------------*

Due to that fact, this puzzle has a natural interest for all those interested in computer and manual Sudoku solving. So, the purpose of this thread is to collect all logical solutions and other studies regarding Puzzle #77, and I invite here the others users of this forum to do that in this thread.

Having said that, I will begin to make my own contribution to the study of this puzzle by writing in the next paragraphs the solution of it that I have build by my own. The notation that I use in the logical deductions is described here.

After the basic logic is applied to this puzzle we arrive at the following grid:

Code: Select all: *---------------------------------------------------------------* | 7 1589 568 | 1269 13569 23569 | 4 125 123 | | 14569 2 456 | 1469 7 34569 | 156 8 13 | | 1456 145 3 | 1246 156 8 | 12567 1257 9 | |---------------------+--------------------+--------------------| | 2489 4789 2478 | 5 1689 469 | 3 1247 12478 | | 3458 6 4578 | 148 2 34 | 1578 9 1478 | | 234589 4589 1 | 489 389 7 | 258 245 6 | |---------------------+--------------------+--------------------| | 12568 1578 25678 | 3 568 256 | 9 1247 12478 | | 1258 3 2578 | 2789 4 259 | 1278 6 1278 | | 2468 478 9 | 2678 68 1 | 278 3 5 | *---------------------------------------------------------------*

From here, I have solved the puzzle through the following steps:

1. [r3c78](-1-[r3c1245])=6=[r2c7]-6-[r2c3]=6=[r3c1](-6-[r3c4|r7c1])-6-[r3c5](-5-[r79c5]-6,8-[r89c4| r7c6])-5-[r3c2]{(-4-[r6c2])-4-[r9c2]=4=[r9c1]-4-[r5c1]}-4-[r3c4](-2-[r8c4])-2-[r9c4]{-7-[r8c4](-9-[r8c6])-9-[r6c4]}(-7-[r9c7])-7-[r9c2](-8-[r9c7]-2-[r6c7])(-8-[r6c2])-8-[r78c1]=(Almost Unique Rectangle: r78c16)=8|1=[r78c1]-1-[r2c1]=1=[r1c2]-1-[r1c45]=1=[r2c4](-1-[r56c4]-8-[r6c5])=4=[r2c6]-4-[r5c6](-3-[r5c1])-3-[r6c5]-9-[r6c2](-5-[r6c7]-8-[r6c4])-5-[r5c1]-8-[r5c4]-4-[r6c4], => r3c7/r3c8<>1.

2. [r7c6]{-6-[r4c6]=6=[r4c5](-6-[r3c5])=1=[r5c4]-1-[r5c79]}{-6-[r7c13]=6=[r9c1](-6-[r3c125]-4-[r2c3])=4=[r9c2](-4-[r46c2])-4-[r3c2]=4=[r3c1]-4-[r456c1]}(-6-[r7c5])-6-[r9c5](-8-[r9c7]){-8-[r6c5]=8= [r6c4](-8-[r6c7|r6c2])=4=[X-Wing: r45c36]-4-[r45c89]=4=[r6c8]-4-[r7c8]}-8-[r7c5]-5-[r3c5]-1-[r3c2](-5-[r2c3]-6-[r2c7]=6=[r3c7]=7=[r3c8]-7-[r7c8])-5-[r6c2]-9-[r6c5]-3-[r5c6]-4-[r4c6]-9-[r8c6]=9=[r8c4]=7=[r9c4]-7-[r9c7](-2-[r6c7])(-2-[r8c79])-2-[r7c8]-1-[r8c79]=(Almost Unique Rectangle: r58c79)=1|5=[r5c7]-5-[r6c7], => r7c6<>6.

3. [r12c6](-6-[r1c4|r2c4|r3c5])-6-[r4c6]=6=[r4c5](=1=[r5c4]-1-[r1c4|r2c4]){-6-[r9c5](-8-[r7c5|r9c27])-8-[r6c5]=8=[r6c4]-8-[r6c27]}-6-[r7c5](-5-[r3c5]-1-[r2c3|r3c12]-5,6-[r1c3]-8-[r7c3])(-5-[r7c3|r8c6])-5-[r7c6](-2-[r7c3])-2-[r8c6]-9-[r4c6]-4-[r5c6]-3-[r6c5]-9-[r36c2]-4-[r9c2](-7-[r7c3]-6-[r2c3])-7-[r9c7](-2-[r3c7])-2-[r6c7](-5-[r6c8])-5-[r6c2](-4-[r6c8]-2-[r13c8]=2=[r1c9]-2-[r1c4])-4-[r3c2]-5-[r2c3]-4-[r2c4]-9-[r1c4], => r1c6/r2c6<>6.

4. [r5c1]=3=[r5c6]=4=[r2c6]-4-[r3c4]=4=[X-Wing: r39c12]-4-[r5c1], => r5c1<>4.

5. [r6c5](=3=[r1c5]-3-[r1c9])(=3=[r5c6]=4=[r2c6])(-8-[r6c247|r47c5])-8-[r9c5](-6-[r3c5])-6-[r7c5](-5-[r78c6]=5=[r1c6]-5-[r1c89]-1-[r1c2])-5-[r3c5]{-1-[r2c3|r3c12](-5-[r1c2])-5,6-[r1c3]-8-[r1c2]}-1-[r4c5]-9-[r6c4](-4-[r6c2])-4-[r6c78]-5-[r6c2]-9-[r1c2], => r6c5<>8.

6. [r2c1]{(-4-[r46c1])-4-[r9c1]=4=[r9c2]-4-[r46c2]}(-4-[r2c34])-4-[r3c12]=4=[r3c4]{=2=[r3c78](-2-[r1c89|r2c9]-5-[r1c6])=6=[r2c7](-6-[r2c4])-6-[r2c3](-5-[r2c6|r5c3])=6=[r3c1]-6-[r79c1]=6=[r7c3]}-4-[r2c6]=4=[r5c6](-4-[r5c9])(-4-[r5c3]=4=[r4c3]-4-[r4c89]=4=[r6c8]-4-[r7c8]=4=[r7c9])-4-[r256c4]-9-[r8c4]=9=[r8c6](-9-[r1c6])-9-[r2c6](-3-[r1c6]-2-[r7c6])-3-[r2c9]-1-[r2c4]-9-[r6c4](-8-[r6c7])-8-[r5c4](-1-[r5c7])-1-[r5c39]-7,8-[r5c7]-5-[r6c7](-2-[r9c7])-2-[r3c7](=2=[r3c8]-2-[r7c8])-7-[r9c7]-8-[r9c1]-2-[r7c1]=2=[r7c8], => r2c1<>4.

7. [r2c6](-9-[r2c1]=9=[r1c2]-9-[r6c2])(-9-[r8c6]=9=[r8c4]=7=[r9c4]-7-[r9c27])(=3=[r2c9]-3-[r1c9]){=4= [r5c6](-4-[r5c3])=3=[r6c5]}-9-[r1c5]=9=[r4c5]=1=[r5c4](-1-[r123c4])=8=[r6c4]-8-[r6c278]-2-[r4c89]-{Nice Loop: [r6c7]-5-[r6c2]-4-[r9c2]-8-[r9c7]-2-[r6c7]}-{(-8-[r9c1])-8-[r9c5]-6-[r9c1]}-(-5-[r6c8] =5=[r13c8]-5-[r2c7]=5=[r2c13]-5-[r3c2])-4-[r3c2]-1-[r3c5]=1=[r1c5]-1-[r1c9]-2-[r1c46]=2=[r3c4] =4=[r3c1](-4-[r46c1])-4-[r9c1](-2-[r4c1])=4=[r9c2]-4-[r46c2]=4=[r4c3]=2=[r4c1], => r2c6<>9.

8. [r5c4]{=1=[r4c5](-1-[r3c5])-1-[r4c89]}{(-4-[r5c3])-4-[r3c4]=4=[X-Wing: r39c12]-4-[r46c12]=4=[r4c3]-4-[r4c8]}(-4-[r6c4])-4-[r5c6]-3-[r6c5](-9-[r6c2])-9-[r6c4](-8-[r6c7])-8-[r6c2](-5-[r6c78]=5=[r5c7]=1=[r5c9]-1-[r12c9]-2-[r3c8])-5-[r6c7](-2-[r9c7])-2-[r4c8]-7-[r3c8](-5-[r3c5])=7=[r3c7]-7-[r9c7]-8-[r9c5]-6-[r3c5], => r5c4<>4.

9. [r6c1]{-9-[r2c1](=9=[r2c4]-9-[r1c6]=9=[r8c6]=5=[r7c56]-5-[r7c2])=9=[r1c2](-9-[r1c5])=8=[r1c3]-8-[r45c3]}(-9-[r6c24])-9-[r6c5](-3-[r1c5])-3-[r5c6](=3=[r5c1]){-4-[r6c4](-8-[r6c2]=8=[r4c12]-8-[r4c9])-8-[r6c278]-2-[r4c9]}-4-[r2c6]=4=[r2c3](=6=[r7c3]-6-[r7c5])(=6=[X-Wing: r23c17]-6-[r3c5])-4-[r3c12]=4=[r3c4](=2=[X-Wing: r36c78]-2-[r9c7])=2=[r3c78]-2-[r1c89|r2c9](-1-[r4c9])-5-[r1c5]-{Nice Loop: [r6c2]=5=[r3c2]-5-[r3c5]-1-[r1c5]-6-[r9c5](-8-[r9c2])-8-[r9c7]-7-[r9c2]-4-[r6c2]}-4-[r6c2]{-5-[r3c2](-1-[r7c2])-1-[r3c5]-5-[r7c5]-8-[r7c2]}(-5-[r6c8])-5-[r6c7](-2-[r3c7]-7-[r89c7])-2-[r6c8]-4-[r4c9]-7-[r78c9]=7=[r7c8]-7-[r7c2], => r6c1<>9.

10. [r2c1]{(=9=[r4c1]-9-[r4c5])=9=[r2c4](-9-[r1c6])-9-[r6c4]=9=[r6c5]=3=[r1c5]-3-[r1c69]}(-6-[r2c3|r3c1])(-6-[r2c7]=6=[r3c7]-6-[r3c5])-6-[r1c89|r2c7]-2-[r1c6]-5-[r3c5]-1-[r3c12]-4,5-[r2c3], => r2c1<>6.

11. [r2c1]{(=9=[r4c1]-9-[r4c5])=9=[r2c4](-9-[r1c6])-9-[r6c4]=9=[r6c5]=3=[r5c6](-3-[r1c6])=4=[r2c6](-4-[r2c3])=3=[r2c9]-3-[r1c9]}(-5-[r2c3|r3c12]-1-[r3c5])(-5-[r2c7])-5-[r2c3]-6-[r2c7]=6=[r3c7]-6-[r3c5]-5-[r1c6]-2-[r1c9]-1-[r2c7], => r2c1<>5.

12. [r1c5](-6-[r2c4|r3c5]){=3=[r6c5](-3-[r6c1])(-3-[r5c6]-4-[r5c3])=9=[r4c5](=1=[r5c4]=8= [r6c4]-8-[r6c1])-9-[r4c12]=9=[r6c2]-9-[r1c2]=9=[r2c1]-9-[r2c4]}-6-[r79c5]=6=[r9c4](-6-[r9c1])=7=[r8c4]=9=[r8c6]=2=[r7c6](-2-[r7c3])=5=[r7c5](-5-[r7c3])(=8=[r9c5]-8-[r9c1])-5-[r3c5](-1-[r2c4]-4-[r2c3]=4=[X-Wing: r39c12]-4-[r6c1])-1-[r2c3|r3c12](-5,6-[r1c3]-8-[r57c3])-5-[r1c2]=5=[r3c2](=4=[r3c1]-4-[r9c1]-2-[r6c1])-5-[r2c3]-6-[r7c3]-7-[r5c3]-5-[r6c1], => r1c5<>6.

13. [r1c3](-5-[r1c8|r5c3])(=8=[r1c2]-8-[r6c2])(-5-[r2c3|r3c12]-1-[r3c5])=6=[r1c4]-6-[r3c5]-5-[r3c78]=5=[r2c7]-5-[r56c7]=5=[r6c8]-5-[r6c2|r6c1]=5=[r5c1]=3=[r5c6](-3-[r6c5]-9-[r6c2])=4=[r6c4]-4-[r6c2], => r1c3<>5.

14. [r5c1](-8-[r789c1|r46c2|r5c379])(-8-[r5c4]-1-[r5c79])=3=[r6c1]-3-[r6c5](-9-[r6c2|r1c5])=3=[r5c6](-3-[r1c6])=4=[r6c4](-4-[r6c2]-5-[r5c3])(-4-[r3c4]=4=[X-Wing: r39c12]-4-[r4c2])=8=[r4c5](-8-[r4c9]=8=[r6c7]=2=[r6c8]-2-[r1c8])-8-[r79c5](-5-[r78c6]-2,9-[r1c6]-5-[r1c8]-1-[r4c8]=1=[r4c9])-5,6-[r3c5]-1-[r2c3|r3c12]-6-[r1c3](-8-[r78c3])=6=[r1c4]=9=[r2c4]-9-[r2c1](-1-[r78c1]=1=[r7c2] =8=[r7c9])=9=[r1c2]-9-[r4c2]-7-[r5c3]-4-[r5c9]=4=[r4c8]-4-[r7c8]=4=[r7c9], => r5c1<>8.

15. [r1c5](-5-[r1c89|r2c9]-2-[r1c46]=2=[r3c4]=4=[X-Wing: r39c12]-4-[r46c12]){(-5-[r3c5])-5-[r79c5]-6-[r3c5]-1-[r2c3|r3c12](-5-[r1c2])-6-[r1c3](=6=[r1c4])-8-[r5c3]}=3=[r6c5](=9=[r4c5]-9-[r4c12]=9=[r6c2]-9-[r1c2]=9=[r1c6]-9-[r8c6]=9=[r8c4]=7=[r9c4]-7-[r9c2])-3-[r5c6](-4-[r5c9])-4-[r5c3]=4=[r4c3]-4-[r4c89]=4=[r6c8]=5=[r3c8](-5-[r3c12]=5=[r2c3]-5-[r5c3])-5-[r3c2]-4-[r9c2]-8-[r4c2]-7-[r5c3], => r1c5<>5.

16. [r3c7](-5-[r3c12])(-5-[r56c7]=5=[r6c8]-5-[r6c12])(=6=[r2c7]-6-[r2c3])-5-[r3c5]=5=[r7c5]-5-[r7c123]=5=[X-Wing: r58c13]-5-[r2c3]=5=[r1c2]=8=[r1c3]=6=[r1c4]-6-[r3c5]-1-[r3c2]-4-[r2c3], => r3c7<>5.

17. [r1c6]{(-2-[r1c8])-2-[r12c9]-1-[r1c8]-5-[r1c2]}-2-[r7c6](-5-[r79c5]-8-[r4c5])(-5-[r7c123])-5-[r7c5]=5=[r3c5]-5-[r3c12]=5=[r2c3](-5-[r5c3])-5-[r8c3]=5=[r8c1]-5-[r56c1]=5=[r6c2]=9=[r6c45]-9-[r4c5]-1-[r4c89]=1=[X-Wing: r58c79]-1-[r2c7|r12c9]=1=[r1c8], => r1c6<>2.

18. [r3c4]=2=[r1c4]=6=[r1c3]-6-[r2c3|r3c12]-1-[r3c4], => r3c4<>1.

19. [r46c12](-4-[r3c1/2])-4-[r9c1/2]=4=[r9c2/1]-4-[r3c2/1]=4=[r3c4]=2=[r1c4]{(-2-[r1c8])-2-[r12c9](-1-[r458c9])(-1-[r2c7])-1-[r1c8]-5-[r1c6]}=6=[r1c3](=8=[r1c2]=9=[r2c1])-6-[r3c1|r3c2]-5-[r3c5](=5=[r7c5]-5-[r7c123])=5=[r2c6]=3=[r2c9]=1=[r2c4]-1-[r5c4]=1=[r4c5]-1-[r4c8]=1=[r5c7](=5= [r6c78]-5-[r6c12]=5=[X-Wing: r58c13]-5-[r3c1])-1-[r8c7]=1=[r8c1]-1-[r3c1], => r4c1/r4c2/r6c1/r6c2<>4.

20. [r3c1]{(-5-[r5678c1])-5-[r3c5]=5=[r7c5]-5-[r7c23]=5=[r8c3]-5-[r5c3]=5=[r6c2]-5-[r6c7]}(=4=[r9c1] =2=[r9c7]-2-[r6c7]-8-[r6c124])-5-[r2c3]-6-[r1c3](-8-[r5c3])=6=[r1c4]-6-[r3c5]-1-[r4c5]=1=[r5c4]=8=[r4c5]-8-[r4c123]=8=[r5c3], => r3c1<>5.

21. [r3c8]{=7=[r3c7](-7-[r89c7])=6=[r2c7]-6-[r2c3]-5-[r578c3]}-5-[r3c5]=5=[r7c5]-5-[r7c12]=5=[r8c1] (-5-[r6c1])-5-[r5c1](-3-[r6c1])(=5=[r6c2]-5-[r69c7]-2,8-[r8c7]-1-[r5c7])-3-[r5c6]{(-4-[r5c3])-4-[r6c4]=4=[r6c8]}-4-[r2c6]=4=[r2c4]=9=[r2c1](=1=[r2c9])-9-[r46c1](-8-[r5c3]-7-[r5c79])-2-[r9c1]=2=[r9c7]-2-[r6c7]-(Hidden Pair: r4c89 – “2,7”)-1-[r4c89]=1=[r5c9]-1-[r2c9], => r3c8<>5.

22. [r2c6]{=4=[r2c4]=9=[r2c1](-9-[r1c2])-9-[r4c1]}{=4=[r5c6](=3=[r1c6])-4-[r6c4]=4=[r6c8] =2=[X-Wing: r69c17]-2-[r4c1]}(-5-[r3c5])-5-[r2c3]-6-[r1c3]=6=[r1c4](-6-[r3c5]-1-[r4c5])=9=[r1c5]-9-[r4c5]-8-[r4c1], => r2c6<>5.

23. [r5c3]-5-[r2c3]=5=[r2c7]-5-[r56c7]=5=[r6c8]=4=[r6c4]-4-[r5c6]-3-[r5c1]-5-[r5c3], => r5c3<>5.

24. [r6c4]=4=[r6c8]=5=[r1c8]-5-[r1c6]-9-[r8c6]=9=[r8c4]-9-[r6c4], => r6c4<>9.

25. [r6c2]=9=[r6c5]=3=[r5c6]-3-[r5c1]-5-[r6c2], => r6c2<>5.

26. [r1c4]=6=[r1c3]=8=[r1c2]-8-[r6c2]-9-[r6c5]-3-[r1c5](-1-[r1c4])-1-[r3c5]-5-[r1c6]-9-[r1c4], => r1c4<>1,9.

27. [r5c1]=5=[r5c7](=1=[r8c7]-1-[r8c1])(-5-[r6c7])-5-[r6c8]=5=[r1c8]-5-[r1c6]-9-[r1c2]=9=[r2c1]-9-[r48c1]-2-[r9c1]=2=[r9c7]-2-[r6c7]-8-[r6c4]-4-[r5c6]-3-[r5c1],

which implies r5c1<>3 and that solve the puzzle.

Carcul

by **ravel** » Mon Apr 10, 2006 3:30 pm

Hi Carcul,

you again confirmed to be the uncrowned heavyweight sudoku world champion

The hardest step is nr 9, because it uses an 8-cell loop for the elimination.
All others are straightforward to follow.

If my buggy program is not wrong in this case, you would need more than basics
(including tuples at least up to triples and hidden pairs), x-wing and UR type 1 and 4
for elimination chains to be able to solve it. At least this is the only sudoku i know,
which my program could not solve with (monster) chains using this implemented techniques.

by **ravel** » Tue Apr 11, 2006 10:18 am

Carcul,

looking closer at nr. 9 the elimination was clear, but (besides of typos) i was missing r4c5=9, r4c8=1, r1c8=5, r3c1=6 to get to -5-[r1c5] before and [r3c5]-1- in the nice loop. Dont you need that ?

by **Carcul** » Tue Apr 11, 2006 12:09 pm

Hi Ravel.

Thanks for your comments.

Ravel wrote:i was missing r4c5=9, r4c8=1, r1c8=5, r3c1=6 to get to -5-[r1c5] before and [r3c5]-1- in the nice loop. Dont you need that?

I cannot see why is that needed. Let me try to explain. The "-5-[r1c5]" comes from the "=4=[r3c4](...)=2=[r3c78]-2-[r1c89|r2c9]". We have a grouped strong link on "2" in row 3: if r3c4 is not "2" then it can only be in one of r3c78. But in box 3 we have an ALS in cells r1c89/r2c9, where if r1c89 are not "2" then the set is locked on "1,3,5" and r1c8=5 which takes out "5" from r1c5.
The "[r3c5]-1-" in the loop is possible because r3c5 is "turned" a bivalue cell by the X-Wing on "6" in cells r23c17, which takes out "6" from r3c5.
Hope this help.

Regards, Carcul

by **tarek** » Tue Apr 11, 2006 12:46 pm

what a solution Carcul,

My solver had to go through several simple contradiction eliminations (probably 12+) to solve this one, not just the implication chains & nets, I will post the solver's log just to give others an insight to how difficult this puzzle is

tarek

by Pi » Tue Apr 11, 2006 1:15 pm

That's a beast, i printed it off and willsave it for a rainy day.

I once made a pretty hard one that needed X-wing hidden triple, naked quadruple + 3 Locked candidates but this is a totally diferent kettle of fish!

by **tarek** » Tue Apr 11, 2006 3:39 pm

here is what my solver prints out (demonstrating how difficult this puzzle is):

Code: Select all: *--------------------------------------------------------------------------* | 7 1589 568 | 1269 13569 23569 | 4 125 123 | | 14569 2 456 | 1469 7 34569 | 156 8 13 | | 1456 145 3 | 1246 156 8 | 12567 1257 9 | |------------------------+------------------------+------------------------| | 2489 4789 2478 | 5 1689 469 | 3 1247 12478 | | 3458 6 4578 | 148 2 34 | 1578 9 1478 | | 234589 4589 1 | 489 389 7 | 258 245 6 | |------------------------+------------------------+------------------------| | 12568 1578 25678 | 3 568 256 | 9 1247 12478 | | 1258 3 2578 | 2789 4 259 | 1278 6 1278 | | 2468 478 9 | 2678 68 1 | 278 3 5 | *--------------------------------------------------------------------------* 6 in r7c6 would lead to a contradiction (Simple contradiction elimination) 4 in r5c4 would lead to a contradiction (Simple contradiction elimination) 9 in r4c6 would lead to a contradiction (Simple contradiction elimination) 8 in r6c5 would lead to a contradiction (Simple contradiction elimination) 4 in r5c1 would lead to a contradiction (Simple contradiction elimination) 6 in r2c4 would lead to a contradiction (Simple contradiction elimination) 8 in r5c3 would lead to a contradiction (Simple contradiction elimination) 6 in r2c6 would lead to a contradiction (Simple contradiction elimination) *--------------------------------------------------------------------------* | 7 1589 568 | 1269 13569 23569 | 4 125 123 | | 14569 2 456 | 149 7 3459 | 156 8 13 | | 1456 145 3 | 1246 156 8 | 12567 1257 9 | |------------------------+------------------------+------------------------| | 2489 4789 2478 | 5 1689 46 | 3 1247 12478 | | 358 6 457 | 18 2 34 | 1578 9 1478 | | 234589 4589 1 | 489 39 7 | 258 245 6 | |------------------------+------------------------+------------------------| | 12568 1578 25678 | 3 568 25 | 9 1247 12478 | | 1258 3 2578 | 2789 4 259 | 1278 6 1278 | | 2468 478 9 | 2678 68 1 | 278 3 5 | *--------------------------------------------------------------------------* ****4 in r4c6 would lead to a contradiction (Complex contradiction elimination) 8 in r5c1 would lead to a contradiction (Simple contradiction elimination) 9 in r2c6 would lead to a contradiction (Simple contradiction elimination) 5 in r7c2 would lead to a contradiction (Simple contradiction elimination) 5 in r1c3 would lead to a contradiction (Simple contradiction elimination) 5 in r2c3 would lead to a contradiction (Simple contradiction elimination) Eliminating 1 from r3c7(ALS-XY A=46 in r2c3 B=12356 in r2c9,r1c9,r1c8,r2c7 C=1456 in r3c2,r3c5,r3c1 x=6 y=4 z=1) Eliminating 1 from r3c8(ALS-XY A=46 in r2c3 B=12356 in r2c9,r1c9,r1c8,r2c7 C=1456 in r3c2,r3c5,r3c1 x=6 y=4 z=1) Eliminating 5 from r3c7(ALS-XY A=46 in r2c3 B=12356 in r2c9,r1c9,r1c8,r2c7 C=1456 in r3c2,r3c5,r3c1 x=6 y=4 z=5) Eliminating 5 from r3c8(ALS-XY A=46 in r2c3 B=12356 in r2c9,r1c9,r1c8,r2c7 C=1456 in r3c2,r3c5,r3c1 x=6 y=4 z=5) 6 in r1c3 would lead to a contradiction (Simple contradiction elimination) Eliminating 6 from r2c1(ALS-XZ A=1456 in r3c5, r3c2, r3c1 B=46 in r2c3 x=4 z=6) Eliminating 4 from r2c1(ALS-XZ A=1456 in r3c5, r3c2, r3c1 B=46 in r2c3 x=6 z=4, a classic WXYZ wing) Eliminating 1 from r3c4(ALS-XZ A=1456 in r2c3, r3c2, r3c1 B=15 in r3c5 x=5 z=1) 5 in r2c1 would lead to a contradiction (Simple contradiction elimination) Candidates in r2c4 will force r2c9 to have only 3 as valid Candidates (Level 2 Poly Implication chains) Eliminating 2 From r1c6 (5 & 4 in r2c6 form an XY wing with 2 in r7c6 & r3c4) Eliminating 2 From r8c4 (5 & 4 in r2c6 form an XY wing with 2 in r7c6 & r3c4) Eliminating 2 From r9c4 (5 & 4 in r2c6 form an XY wing with 2 in r7c6 & r3c4) Eliminating 5 from r1c5(ALS-XZ A=3459 in r2c6, r5c6, r1c6 B=1259 in r1c9, r1c8, r1c2 x=9 z=5) Eliminating 1 from r1c4(ALS-XY A=3459 in r2c6,r5c6,r1c6 B=1259 in r1c9,r1c8,r1c2 C=15 in r3c5 x=9 y=5 z=1) Eliminating 1 from r1c5(ALS-XY A=3459 in r2c6,r5c6,r1c6 B=1259 in r1c9,r1c8,r1c2 C=15 in r3c5 x=9 y=5 z=1) Eliminating 5 from r7c1(ALS-XY A=2459 in r2c6,r7c6,r8c6 B=56789 in r8c4,r9c5,r9c4,r7c5 C=345 in r5c6,r5c1 x=9 y=4 z=5) Candidates in r5c1 will force r7c6 to have only 2 as valid Candidates (Level 3 Poly Implication chains) Candidates in r5c1 will force r3c5 to have only 1 as valid Candidates (Level 3 Poly Implication chains) Eliminating 1 from r7c1(ALS-XY A=67 in r7c3 B=1469 in r2c3,r2c4,r2c1 C=1478 in r7c8,r7c2,r7c9 x=6 y=7 z=1) Eliminating 1 From r8c9 ( XWing in Columns 17) Eliminating 5 from r6c2(ALS-XY A=467 in r7c3,r2c3 B=3457 in r5c3,r5c6,r5c1 C=45 in r3c2 x=7 y=4 z=5) Eliminating 8 from r9c2(ALS-XZ A=2468 in r7c1, r3c1, r9c1 B=2678 in r9c5, r9c4, r9c7 x=2 z=8) Eliminating 8 from r6c1(ALS-XZ A=24689 in r7c1, r3c1, r9c1, r4c1 B=4789 in r9c2, r6c2, r4c2 x=9 z=8) Candidates in r6c4 will force r8c3 to have only 25 as valid Candidates (Level 1 Poly Implication chains) Eliminating 4 from r6c1(ALS-XY A=25 in r8c3 B=245789 in r5c3,r6c2,r4c2,r4c3,r4c1 C=2468 in r7c1,r3c1,r9c1 x=5 y=2 z=4) Candidates in r6c7 will force r1c9 to have only 1 as valid Candidates (Level 2 Poly Implication chains)

**** Most difficult step
Level 1 Poly implication chain : simple xy chains
Level 2 Poly implication chain : simple implication chains (singles)
Level 3 Poly implication chain : simple implication nets (singles)
Simple contradiction elimination: singles
Complex contradiction elimination: subset level
Singles & box-line interactions steps removed

tarek

by **ravel** » Tue Apr 11, 2006 3:41 pm

Carcul wrote:Hope this help.

Yes, it did, thanks,
i missed to remove the 6 from r3c5.
The fact, that from the triple in [r1c89|r2c9] follows, that r1c8=5, IMHO should be denoted explicitly, e.g.
...-2-[r1c89|r2c9](=5=[r1c8])(-1-[r4c9])...
would have been clear for me.

by **Carcul** » Tue Apr 11, 2006 6:01 pm

Tarek wrote:here is what my solver prints out...

That's funny: in the total of 14 "simple contradiction eliminations" plus the "complex contradiction elimination" made by your solver (the first 14 steps of the print), 10 of them correspond directly or indirectly to deductions that I have made myself.

Regards, Carcul

by **tarek** » Tue Apr 11, 2006 7:56 pm

Carcul wrote:That's funny: in the total of 14 "simple contradiction eliminations" plus the "complex contradiction elimination" made by your solver (the first 14 steps of the print), 10 of them correspond directly or indirectly to deductions that I have made myself.

With such puzzle, there is little room to maneuver...I'm not surprised that several steps have the corresponding outcomes.

The contradiction eliminations that my solver used are the domesticated form of T&E, it has some method behind it , but is still T&E.

The use of Complex implication nets, which are beyond me & my solver at this moment (as are your impressive loops), should solve every puzzle

.

tarek

by **Excell** » Sun Apr 16, 2006 7:01 am

Hi all
I am new here and have been writing a solver. Does this puzzel have only one soloution? if so maybe somemone could send me the correct soloution.

Thanks in adavnce for any replies.

by **Ocean** » Mon Apr 17, 2006 1:45 pm

Carcul wrote:The following puzzle (Puzzle #77 from top1465) is currently considered the toughest known Sudoku puzzle:...

There are two alternative single cell xy-cycle backdoors (magic cells) for this puzzle: r2c7=5 or r6c8=5. Hardest method is then application of the xy-chain 1-(r2c1)-9-(r4c1)-8-(r6c2)-9-(r6c5)-8-(r5c4)-1, which appears after about 40 cells are filled in.

by **ravel** » Wed Apr 19, 2006 8:26 am

This puzzle is that hard, that i had to put another loop around my program to get some hints, how it could be solved. The result so far is, that it can be cracked with one of the following 10 step brute force eliminations.

r1c2<>5, r6c2<>4, r5c7<>1, r3c4<>4, r1c6<>2, r2c9<>1, r1c5<>9, r6c5<>3, r5c9<>1, r5c7<>5
r4c6<>4, r1c6<>2, r6c2<>4, r5c7<>1, r3c4<>4, r2c9<>1, r1c5<>9, r6c5<>3, r5c9<>1, r1c8<>1
r7c6<>6, r1c6<>2, r6c2<>4, r5c7<>1, r3c4<>4, r2c9<>1, r1c5<>9, r6c5<>3, r5c9<>1, r2c7<>6
r1c4<>1, r6c2<>4, r5c9<>1, r4c6<>9, r4c6<>4, r1c6<>2, r5c7<>1, r2c3<>4, r6c5<>3, r1c8<>1

Each elimination can be made with singles, tuples, locked candidates, xwing and UR type 1, but i dont know, how to do it effectively or if some of them can be done with advanced methods.
To check all possible orders of eliminations to find an optimum would last years with my program, so i did it in a greedy way starting from each of the 20 eliminations that are possible at the beginning. Since UR type 2 is not implemented, Carculs first chain would need 3 eliminations. So many improvements are possible.

Compare: for the ancient toughest puzzle easily 4 step eliminations could be found:
r3c5<>1, r2c3<>4, r5c4<>8, r3c2<>9
r3c5<>1, r3c5<>8, r2c3<>4, r3c2<>9
r3c5<>1, r5c5<>1, r2c3<>4, r3c2<>9

by **ravel** » Thu Apr 20, 2006 8:52 am

[Edit:]I started a new thread now about the hardest sudokus. So the following is history

When i tried my program with some other ultra hard puzzles, i got this ranking (but note that an xy-wing here would be a step like a monster chain, i made no closer look at the steps):
11 steps:top1465 #125 (also here)
10 steps: top1465 #77 (this toughest known), Vidar's monster 3
8 steps : gfroyle's beauty
4 steps : ancient toughest known, top1465 #244, Emily's friend's, RW's

[Edit: ]
added Emily's friend's puzzle
removed the 3-steppers, there are many around
added RW's

by **inventor** » Tue May 09, 2006 2:36 pm

ravel wrote:When i tried my program with some other ultra hard puzzles, i got this ranking (but note that an xy-wing here would be a step like a monster chain, i made no closer look at the steps):
11 steps:top1465 #125 (also here)
10 steps: top1465 #77 (this toughest known), Vidar's monster 3
8 steps : gfroyle's beauty
4 steps : ancient toughest known, top1465 #244, Emily's friend's
3 steps : Vidar's tough one (monster 1), Vidar's monster 4

[Edit: added Emily's friend's puzzle]

Thanks for your reply!

Ooops! These ones were realy hard, thank you!

The first one of your links, the 11 steps "top 1465", I haven't tried, mostly because I didn't like the sideways coding.

The second one, the 10 steps "Vidar's monster 3" has been tried, and unfortunately could not be solved whitout a gessing after 2 simple starting steps.....

After a correct guessing 6 in r1c2 then, after 4 more simple steps, a new guess was requierd!

Obiously the worst one ever experienced! My program's rated this puzzle to 35 points.

The third one, "gfroyl's beauty" required an emediate guess without any initiative steps ..

After gessing 1 in r3c2 the rest went on smoothly. Rating: 26 points. ( A guess=5 points, else 1, 2, 3 and 4 points for ordinary techniques).

The fourth one, "Emily's friend's" was solved without any problem

(meaning solved by using only simple techiques, and the new techique). The rating was 33 points, a real hard one after all....

:?:

When I edited this "Emily's friend's" into the sudoku program (the program for this site), it refused to verify.... Have someone others experienced that? What is wrong?

I also tried "Emily's friend's" for the "SadMans sudoku" http://www.sadmansoftware.com/sudoku/ which verified it, but could not solve it without two guesses... So I think my program do well after all....

What is the bottom line here? Well, obiously that any supertechnique solving any sudoku is not found yet! But we try, don't we?

If you (or others) have more such hard ones, let me know!

The New Sudoku Players' Forum

The Toughest Known Puzzle

The Toughest Known Puzzle

Re: The Toughest Known Puzzle