An Interesting Puzzle

Advanced methods and approaches for solving Sudoku puzzles

An Interesting Puzzle

Postby Carcul » Sat Jan 07, 2006 3:46 pm

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
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby tarek » Sat Jan 07, 2006 4:01 pm

It is a toughie.
However My human-style solver required only 6 simple T&Es to crack it. Many puzzles out there require more.
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby Carcul » Sat Jan 07, 2006 4:50 pm

Hi Tarek.

Tarek wrote: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).

Tarek wrote:Many puzzles out there require more.


Could you list these puzzles?

Thanks in advance.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby tarek » Sat Jan 07, 2006 5:03 pm

Carcul wrote: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.

Carcul wrote:
Tarek wrote: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 ???
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby Carcul » Sat Jan 07, 2006 5:18 pm

Hi Tarek.

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

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


Yes.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby tarek » Sat Jan 07, 2006 5:38 pm

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
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby tarek » Sun Jan 08, 2006 1:58 pm

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
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby rubylips » Sun Jan 08, 2006 5:54 pm

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.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Carcul » Sun Jan 08, 2006 10:13 pm

Thanks Rubylips.
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby maria45 » Sun Feb 05, 2006 8:33 pm

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
maria45
 
Posts: 54
Joined: 23 October 2005

Postby Carcul » Sun Feb 05, 2006 11:52 pm

Hi Maria45.

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


Congratulations. My solution have 27 steps.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Carcul » Thu Apr 06, 2006 7:59 am

Tarek wrote: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
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby tarek » Thu Apr 06, 2006 10:53 am

Congrats,

I am interested:D , 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:D .

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
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby Carcul » Thu Apr 06, 2006 11:14 am

Tarek wrote: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
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Mike Barker » Sat Apr 08, 2006 6:26 pm

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
Mike Barker
 
Posts: 458
Joined: 22 January 2006


Return to Advanced solving techniques