The New Sudoku Players' Forum

[Carcul]

Consider the following puzzle:

Code: Select all

 . 5 2 | . . 6 | 8 . .
 . . . | . . 7 | . 2 .
 . . . | . . . | 6 . .   
-------+-------+------
 . . 4 | 8 . . | 9 . .
 2 . . | 4 1 . | . . .
 . . 1 | . . . | . . 8
-------+-------+------
 . . 6 | 1 . . | 3 8 .
 . . . | . 9 . | . . 6
 3 . . | 6 . . | 1 . 9


I would like to know how the various solvers (electronic and human) out there rate this grid. I have read in the progammers forum that, some time ago, one solver rated this puzzle harder than the "toughest known puzzle". Is this the case?

Carcul

[tarek]

It is a toughie.
However My human-style solver required only 6 simple T&Es to crack it. Many puzzles out there require more.

[Carcul]

Hi Tarek.

My human-style solver required only 6 simple T&Es to crack it.

I am a human solver and T&E does not make part of my style, as with many others in this forum (I think).

Many puzzles out there require more.

Could you list these puzzles?

Thanks in advance.

Carcul

[tarek]

I am a human solver and T&E does not make part of my style, as with many others in this forum (I think).

I am too a HUMAN solver but I programmed a solver which attempts to emulate human-style, that solver couldn't crack it without T&E. The solver doesn't implement colouring nor full tabling.

Many puzzles out there require more.

Could you list these puzzles?

Well known puzzles that require T&E can be found in the top1465 list, #77 is considered by many as the toughest (documented in many forum topics).

Now, did you solve your puzzle without T&E ???

[Carcul]

Hi Tarek.

Is #77 the so caled "toughest known puzzle"? If not, please post the puzzle.

Now, did you solve your puzzle without T&E ???

Yes.

Regards, Carcul

[tarek]

Then you must have used advanced techniques not implemented in my solver.

I think then your question would be regarding the toughest puzzle not requiring T&E.

I couldn't comment on that (At this stage at least )

regards,

tarek

[tarek]

This is #77 From the 1465

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 


The plethora of advanced techniques mentioned in the forums here are impressive, reducing the need to use T&E in many cases. Many of these I haven't yet implemented in my solver & hence it resorted to T&E (which is the the final step).

It would be interesting to see what would be your take on the #77 Carcul

regards,

Tarek

[rubylips]

My solver solves the puzzle but makes heavy use of inferred links (links that have been inferred from tables). The full solution is long, complicated and not particularly instructive, so I won't print it here.

Alternatively, the solver will crack the puzzle with five guesses provided one of the Locked Candidates or Disjoint Subsets strategy types is employed in addition to the trivial search for singles and hidden singles.

[Carcul]

Thanks Rubylips.

[maria45]

Hello Carcul,

yes, I solved your puzzle and it required 36 forcing chains and 3 contradictions. Didnt check if there was an easier solution. Comparing the puzzle with the so far hardest (the one from tlips) is not quite easy, as I solved that one with 20 forcing chains, but also used uniqueness, which I avoided in solving your puzzle, so may be, the puzzle are about equally hard.

Greetings, Maria

[Carcul]

Hi Maria45.

I solved your puzzle and it required 36 forcing chains and 3 contradictions.

Congratulations. My solution have 27 steps.

Regards, Carcul

[Carcul]

It would be interesting to see what would be your take on the #77 Carcul

As I also thought that it would be interesting, I have tried to solve that puzzle: so, I have now solved puzzle #77 from Top 1465 without using guessing or trial and error (regarding my definition of T&E). In the next few days I will try to post my solution in the case you (or others) is still interested in my "take".

Regards, Carcul

[tarek]

Congrats,

I am interested , and don't worry, although I don't use nice loops, I can read them....

My browser has no problems with your long loops so bring it on .

From that ancient time when I made theat statement, my solver has improved 'a bit', The biggest challange now seems to be the #2 of the top 1465, as one of several puzzles that requires subset level contradiction elimination to solve.....

Tarek

[Carcul]

The biggest challange now seems to be the #2 of the top 1465

Yes, I know perfectly that puzzle, but I still think that #77 is much harder than #2: the reason is that, as was already demonstrated by Bennys, a straightforward solution for that puzzle can be reached in a dedution that uses a combination of ALSs: as far as I could see during solving, such a deduction could not be made for #77 (using ALSs or any other combination of techniques), but obviously this doesn't mean that its impossible. So, although I am aware that #2 may be considered the hardest by the computer programs, I think that from a human point of view (at least from mine) puzzle #77 is by far the toughest one.

Regards, Carcul

[Mike Barker]

I guess I'd rate your first puzzle as less difficult than #77 since my solver can solve this, but not #77. Here's the solution it came up with. It is still a work in progress and so I won't guarantee the solution. I've started to implement some of Ron's and Carcul's suggestions, but have a ways to go. I have the mutual exclusion rule implemented for ALS and nice loops and have all of the eliminations reported (although not very concisely). I still use "~" to show the discontinuity in a nice loop (although not necessary, I kind of like the added detail) and don't show the final link for discontinuous nice loops where the start and end nodes don't share a house (it's actually all of the cells where eliminations occur). Also I use the strong-link approach for X-cycles instead of X-wings, Turbot fish, etc. so, for example, two grouped strong links could be either a finned X-wing or a grouped Turbot fish depending on whether the loop is continuous or discontinuous. Finally, I use the generalized version of mYZ-wings (eg WXYZ-wing). All steps are logical (no T&E).

(Updated with MER algorithm)

Hidden Single: r3c6 => r3c6=1,r3c1<>1,r3c2<>1,r3c8<>1,r3c9<>1
Locked Column: r123c4 => r6c4<>9
Locked Column: r123c5 => r7c5<>4,r9c5<>4
Locked Column: r23c5 => r9c5<>8
Two Grouped Strong Links: r6c4=7=r8c4-7-r8c7=7=r56c7~7~ => r6c8<>7
WXYZ-wing: r12c4|r1c5, r2c7 => r2c5<>4,r1c8<>4,r1c9<>4
ALS xz-rule with A=2 cells: r5c79-3-r5689c8 => r4c8<>5,r4c8<>7,r4c9<>7
ALS xy-rule with B=5 cells: r12c4-3-r12379c5-7-r46c5|r456c6 => r6c4<>5,r6c4<>2,r8c7<>5,r8c7<>7
Locked Column Box: r1389c8|r137c9 => r5c8<>7,r5c9<>7
ALS xy-rule with B=2 cells: r28c7-5-r12c4-3-r8c4|r79c5 => r8c6<>2,r3c4<>9,r3c4<>3
ALS xy-rule with B=3 cells: r2c3457-4-r568c7-5-r5c9 => r2c9<>3
ALS xy-rule with B=2 cells: r1c4589-1-r2c79-5-r3c12389 => r3c5<>4
Hidden Single: r1c5 => r1c5=4,r1c1<>4
Nice Loop: r2c7-4-r6c7=4=r6c8-4-ALS:r89c8~5~ => r3c8<>5
Nice Loop: r23c9=4=r7c9-4-ALS:r7c56|r9c5|r8c4-3-r1c4-9-r1c8=9=r3c8~9~r23c9 => r3c8<>4
Nice Loop: r23c9=4=r7c9-4-ALS:r7c56|r9c5|r8c4-3-ALS:r12c4-5-r2c7-4-r23c9 => r7c1<>4,r7c2<>4,r9c6<>2,r8c6<>5,r9c6<>5,r6c4<>3,r2c5<>5,r2c9<>5
Naked Single: r6c4 => r6c1<>7,r6c2<>7,r6c5<>7,r6c7<>7,r8c4<>7,r4c5<>7
Hidden Single: r5c7 => r5c7=7,r5c2<>7,r5c3<>7
Two Grouped Strong Links: r46c6=2=r7c6-2-r7c9=2=r4c9~2~ => r4c5<>2
Nice Loop: r2c2=6=r456c2-6-ALS:r1467c1-1-r8c1=1=r8c2~1~r2c2 => r2c2<>1
Hidden Single: r8c2 => r8c2=1,r8c1<>1
ALS xz-rule with A=1 cells: r8c7-4-r78c1|r7c2|r89c3 => r7c9<>2
Hidden Single: r8c7 => r8c7=2,r8c4<>2,r6c7<>2
Hidden Single: r3c4 => r3c4=2,r3c5<>2
Hidden Single: r4c9 => r4c9=2,r4c6<>2
Hidden Single: r4c8 => r4c8=1,r1c8<>1
Two Strong Links: r3c5=5=r3c9-5-r2c7=5=r6c7~5~ => r6c5<>5
ALS xy-rule with B=4 cells: r45789c6-2-r7c12|r89c3-8-r46c12|r5c3 => r5c2<>9
ALS xy-rule with B=1 cells: r2c3457-4-r6c7-5-r5c289 => r2c2<>8
Row Jellyfish Fillet-o-Fish: r3c59|r4c156|r6c1678|r7c1569 => r5c9<>5
Naked Single: r5c9 => r5c2<>3,r5c3<>3,r5c6<>3,r5c8<>3,r1c9<>3,r3c9<>3,r6c8<>3
Locked Column: r46c2 => r2c2<>3,r3c2<>3
Hidden Column Pair: r13c8 => r1c8=39,r3c8=39
Naked Row Pair: r1c48 => r1c1<>9
Locked Column: r13c9 => r7c9<>7
ALS xy-rule with B=1 cells: r4c256-5-r5c6-9-r589c3 => r7c2<>7,r9c2<>7
ALS xy-rule with B=3 cells: r6c12578-9-r589c3-7-r7c1269 => r7c5<>2
ALS xz-rule with A=2 cells: r9c26-2-r7c1259 => r9c8<>4
Three Strong Links: r2c7=4=r6c7-4-r6c8=4=r8c8-4-r8c1=4=r9c2~4~ => r2c2<>4
ALS xz-rule with A=2 cells: r25c2-9-r2389c3 => r5c3<>8
Hidden Single: r5c2 => r5c2=8,r3c2<>8,r9c2<>8
Hidden Single: r5c8 => r5c8=6,r6c8<>6
Naked Row Pair: r6c78 => r6c1<>5,r6c6<>5
ALS xz-rule with A=3 cells: r267c2-2-r45789c6 => r6c6<>3
VWXYZ-wing: r7c1569, r6c6 => r6c1<>9
Naked Single: r6c1 => r6c2<>6,r6c5<>6,r2c1<>6,r4c1<>6,r4c2<>6
Hidden Single: r2c2 => r2c2=6
Hidden Single: r4c5 => r4c5=6
Locked Column: r45c6 => r7c6<>5
VWXYZ-wing: r9c3568, r7c6 => r8c6<>4
ALS xz-rule with A=2 cells: r26c5-2-r9c358 => r2c3<>8
ALS xz-rule with A=2 cells: r25c3-5-r6c56|r5c6 => r2c5<>3
Naked Single: r2c5 => r2c1<>8,r3c5<>8
ALS xz-rule with A=3 cells: r7c269-9-r4c12|r6c2 => r7c1<>5
Two Strong Links: r3c5=5=r3c9-5-r7c9=5=r7c5-5-r3c5 => r9c5<>5
VWXYZ-wing: r7c1269, r9c8 => r9c3<>7
VWXYZ-wing: r5679c6, r9c3 => r5c3<>5

The Solution is completed with naked singles