Sudoku for manual solving (Hard, but not pathologically so?)

Advanced methods and approaches for solving Sudoku puzzles

Sudoku for manual solving (Hard, but not pathologically so?)

Postby chrisr » Tue Jul 18, 2006 7:27 pm

Hi,

This sudoku fell out of my generator program, and the simplest solution that I could find still has a number of complex features:

Code: Select all
...|...|1..
54.|...|...
.6.|1..|..9
---+---+---
..8|...|..3
...|..4|...
2..|.95|.8.
---+---+---
1..|..3|.78
6.7|..8|5.2
..9|2..|.1.

000000100540000000060100009008000003000004000200095080100003078607008502009200010

It would be interesting to see what others might make of it:) .

Chris
chrisr
 
Posts: 11
Joined: 19 October 2005

Postby ravel » Tue Jul 18, 2006 9:32 pm

I will try to forget, what i saw in the solver (swordfish, xy-wing, xwz-wing, UR4, turbot fish) before i do it on paper, really nice puzzle.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby algernon » Tue Jul 18, 2006 9:50 pm

Hmmm. My solver finds (beside trivials including one double):

*** Applied Strategy: Naked Tripple
In column_4 the 3 cells {r4c4, r5c4, r2c4} only allow the 3 values {8, 7, 6}

*** Applied Strategy: XYZ-Wing
XYZ-Wing for values {4, 9, 5} with XYZ=r7c4, XZ=r7c3, YZ=r8c4; the common value Z=4 is eliminated from the cell r7c5

*** Applied Strategy: XY-Chain
Value 2 has an xy-chain of cells {[r3c6:2,7], [r3c1:7,8], [r9c1:8,4], [r9c9:4,6], [r9c6:6,7], [r3c6:7,2]} and the cells {r3c3, r1c6} seeing both ends can have this value eliminated.

Michael
algernon
 
Posts: 25
Joined: 26 June 2006

Postby ravel » Wed Jul 19, 2006 7:50 am

So you have xy-chains before the techniques i mentioned in your solver.

This is a special xy-chain, because it ends in the starting cell, which directly shows that r3c6=2 (either it is 2 or it is 2).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Carcul » Wed Jul 19, 2006 9:18 am

Chrisr wrote:It would be interesting to see what others might make of it


Code: Select all
 *-----------------------------------------------------------------*
 | 789     789     23 | 45      345678  267 | 1       3456    4567 |
 | 5       4       1  | 678     3678    9   | 2678    236     67   |
 | 78      6       23 | 1       34578   27  | 478     345     9    |
 |--------------------+---------------------+----------------------|
 | 479     579     8  | 67      267     1   | 24679   24569   3    |
 | 3       1579    56 | 678     2678    4   | 2679    2569    1567 |
 | 2       17      46 | 3       9       5   | 467     8       1467 |
 |--------------------+---------------------+----------------------|
 | 1       2       45 | 459     456     3   | 469     7       8    |
 | 6       3       7  | 49      1       8   | 5       49      2    |
 | 48      58      9  | 2       4567    67  | 3       1       46   |
 *-----------------------------------------------------------------*

We cannot have at the same time r9c5/r1c9/r6c7<>4. But, if r1c9 is not "4":

1. [r6c7]-4-[r3c7]=4=[r13c8]-4-[r8c8]=4=[r8c4]-4-[r1c4]-5-[r1c9]=5=
=[r5c9]-5-[r5c3]-6-[r6c3]-4-[r6c7], => r6c7<>4.

2. [r9c5](-4-[r8c4]=4=[r8c8]-4-[r3c8])-4-[r9c9]-6-[r9c6]-7-[r3c6]-2-
-[r3c3]-3-[r3c8]-5-[r1c9]=5=[r5c9]-5-[r5c3]=5=[r7c3]=4=[r9c1]-4-
-[r9c5], => r9c5<>4.

So, r1c9 must be "4" and the puzzle is solved.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby algernon » Wed Jul 19, 2006 12:24 pm

ravel wrote:So you have xy-chains before the techniques i mentioned in your solver.

This is a special xy-chain, because it ends in the starting cell, which directly shows that r3c6=2 (either it is 2 or it is 2).


You are right, the swordfish is nearly to the end of the list my solver uses.
And I doubt that my solver recognizes the special case (will have to check, sometimes it does more than I intended:-)).

For whom it may
concern:

Code: Select all
Solved 38.239 of 50.000 puzzles (76,5%).
Solving took 9.060.564 ms (181,2 ms/puzzle).

                     | invocatio applicati eliminatio puzzle   used solved       duration     dur./inv.    dur./puz. |
Direct Elimination   | 2.438.532 1.131.919 18.819.652 50.000 50.000 38.239     26.107 ms       0,01 ms       0,52 ms |
Hidden Single        | 1.306.613   617.116  1.432.665 50.000 49.927 38.237    155.735 ms       0,12 ms       3,11 ms |
Area Intersection    |   689.497   240.368    485.022 50.000 49.140 37.765    903.663 ms       1,31 ms      18,07 ms |
Naked Pair           |   449.129    40.401    104.476 50.000 25.440 22.236     78.253 ms       0,17 ms       1,57 ms |
Hidden Pair          |   408.728    34.590    108.055 49.999 23.960 19.563    335.368 ms       0,82 ms       6,71 ms |
Naked Tripple        |   374.138     7.562     25.281 49.942  6.813  5.985    175.531 ms       0,47 ms       3,51 ms |
Hidden Tripple       |   366.576     2.387      9.808 49.939  2.307  1.966    235.532 ms       0,64 ms       4,72 ms |
X-Wing               |   364.189     9.530     24.644 49.930  8.546  7.693  1.914.867 ms       5,26 ms      38,35 ms |
Simple Coloring      |   354.659    27.772     36.671 49.926 19.345 16.744    683.785 ms       1,93 ms      13,70 ms |
XY-Wing              |   326.887    18.477     26.276 49.912 14.199 13.519    104.985 ms       0,32 ms       2,10 ms |
XYZ-Wing             |   308.410    11.895     12.604 49.896 10.358  9.122     44.937 ms       0,15 ms       0,90 ms |
XY-Chain             |   296.515    79.491    118.713 49.839 30.381 29.142    158.125 ms       0,53 ms       3,17 ms |
WXYZ-Wing            |   217.024       399        422 41.510    398    320     39.518 ms       0,18 ms       0,95 ms |
AIC                  |   216.625   204.132    224.198 41.499 40.186 29.734  2.579.801 ms      11,91 ms      62,17 ms |
APE                  |    12.493       560        565 11.945    450    120    217.728 ms      17,43 ms      18,23 ms |
Naked Quad           |    11.933        29        153 11.830     29     11     11.328 ms       0,95 ms       0,96 ms |
Hidden Quad          |    11.904         1          9 11.819      1      1      3.384 ms       0,28 ms       0,29 ms |
Swordfish            |    11.903       139        650 11.818    138     55    375.962 ms      31,59 ms      31,81 ms |
Jellyfish            |    11.764         3         14 11.763      3      2    517.409 ms      43,98 ms      43,99 ms |
total Duration:  8.562.018 ms


This report shows the statistics of my solver on the top50000, which is also the order in which methods are applied.

The reason for doing swordfish so late is that my implementation works on general topologies, and swordfish w/o the distinction of row/column/block is a combinatorical
nightmare. If it is put earlier in the list, it uses about 500 ms instead of 31 ms, and is invoked several times, so total solve time for a "typical" hard sudoku increases from 180 ms to 1800 ms. This is bad, if you often pipe the top50000 through the solver, which I do daily to monitor the progress of my solver (200 solved two weeks ago w/o XY-Chain, 9000 solved last week, 38000 solved after first AIC implementation).
Solving methods depending on uniqueness are not implemented due to religous reasons (My understanding of the puzzle is "Find the solution and _prove_ it is unique). I am curious to find out how many of the 50000 can be tackled w/o uniqueness exploits.

Michael
algernon
 
Posts: 25
Joined: 26 June 2006

Postby algernon » Wed Jul 19, 2006 12:33 pm

algernon wrote:I am curious to find out how many of the 50000 can be tackled w/o uniqueness exploits.


Then again, if I could implement Carcul in Java, the answer would be 50000.:D
algernon
 
Posts: 25
Joined: 26 June 2006

Re: Sudoku for manual solving (Hard, but not pathologically

Postby daj95376 » Wed Jul 19, 2006 5:17 pm

chrisr wrote:It would be interesting to see what others might make of it:) .


Filtering out N/H Singles, I get:

Code: Select all
  c3b1  -  23    Naked  Pair   (both column and box eliminations performed)
    b1  -  9     Locked Candidate (1)
  c4    -  678   Naked  Triple
    b5  -  2     Locked Candidate (1)
r2      -  2     Locked Candidate (2)
r349    -  5     Swordfish
r7c3    ~  6     XY-Wing
r7c4    ~  4     XYZ-Wing   (i.e., [r7c5]<>4)

Which leads to:

Code: Select all
 *-----------------------------------------------------------*
 | 89    89    2     | 45b   7     6     | 1     3     45a   |
 | 5     4     1     | 8     3     9     | 26    26    7     |
 | 7     6     3     | 1     45    2     | 8     45b   9     |
 |-------------------+-------------------+-------------------|
 | 49    579   8     | 67    2     1     | 4679  4569  3     |
 | 3     179   56    | 67    8     4     | 2679  269   15    |
 | 2     17    46    | 3     9     5     | 467   8     14    |
 |-------------------+-------------------+-------------------|
 | 1     2     45    | 459   6     3     | 49    7     8     |
 | 6     3     7     | 49c   1     8     | 5     49c   2     |
 | 48    58    9     | 2     45    7     | 3     1     6     |
 *-----------------------------------------------------------*

Now, simple forcing chains (a-b-c) can be applied to get [r1c9]=4.

Code: Select all
[r1c9]=5 => [r1c4]=4 => [r8c4]=9
         => [r3c8]=4 => [r8c8]=9 => [r8]=INVALID

[Edit:] -OR- the forcing chain can be replaced with a Templates exclusion on 4s.

Code: Select all
r1c9    =  4     Templates

N/H Singles complete the solution.
Last edited by daj95376 on Thu Jul 20, 2006 1:57 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku for manual solving (Hard, but not pathologically

Postby chrisr » Wed Jul 19, 2006 11:05 pm

daj95376 wrote:
Code: Select all
  c3b1  -  23    Naked  Pair   (both column and box eliminations performed)
    b1  -  9     Locked Candidate (1)
  c4    -  678   Naked  Triple
    b5  -  2     Locked Candidate (1)
r2      -  2     Locked Candidate (2)
r349    -  5     Swordfish
r7c3    ~  6     XY-Wing
r7c4    ~  4     XYZ-Wing   (i.e., [r7c5]<>4)


Now, simple forcing chains (a-b-c) can be applied to get [r1c9]=4.

Code: Select all
[r1c9]=5 => [r1c4]=4 => [r8c4]=9
         => [r3c8]=4 => [r8c8]=9 => [r8]=INVALID

N/H Singles complete the solution.


This looks similiar to the solution I found. However, I didn't use an XY-Wing and I then completed the puzzle by Multi-Colouring the 4s:

Code: Select all
 *-------------------------------------------------------------------*
 | 89      89      2   | 45a*    7       6   | 1       3       45A   |
 | 5       4       1   | 8       3       9   | 26      26      7     |
 | 7       6       3   | 1       45A     2   | 8       45a*    9     |
 |---------------------+---------------------+-----------------------|
 | 479a*   579     8   | 67      2       1   | 4679    4569    3     |
 | 3       1579    56  | 67      8       4   | 2679    2569    1567  |
 | 2       17      46A | 3       9       5   | 467*    8       1467a*|
 |---------------------+---------------------+-----------------------|
 | 1       2       45a*| 459     6       3   | 49b     7       8     |
 | 6       3       7   | 49b     1       8   | 5       49B     2     |
 | 48A     58      9   | 2       45a*    7   | 3       1       6     |
 *-------------------------------------------------------------------*


I'm still trying to understand Carcul's solution. Could it be based upon a template argument for positioning the 4s?
chrisr
 
Posts: 11
Joined: 19 October 2005

Re: Sudoku for manual solving (Hard, but not pathologically

Postby daj95376 » Thu Jul 20, 2006 12:31 am

chrisr wrote:This looks similiar to the solution I found. However, I didn't use an XY-Wing and I then completed the puzzle by Multi-Colouring the 4s:

I'm still trying to understand Carcul's solution. Could it be based upon a template argument for positioning the 4s?


Once your puzzle is reduced as shown above, there probably aren't too many variations on solving it. It's very possible that your solution is close to mine. [Edit:] (deleted comment about XYZ-Wing.)

Carcul and I have crossed paths several times. He has a more thorough understanding of chains (and how to express them) than I. My solver's original solution was a medium-length elimination chain. When I examined it, I noticed that only a few of the steps in the chain were really needed. So, I posted the shorter chain above.

I don't think Carcul uses templates, but don't hold me to that. [Edit:] I have templates implemented enough to run your puzzle. I updated my posting above.
Last edited by daj95376 on Thu Jul 20, 2006 1:48 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Carcul » Thu Jul 20, 2006 8:10 am

Chrisr wrote:I'm still trying to understand Carcul's solution. Could it be based upon a template argument for positioning the 4s?


What is a template?
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ravel » Thu Jul 20, 2006 8:20 am

Carcul wrote:
Chrisr wrote:I'm still trying to understand Carcul's solution. Could it be based upon a template argument for positioning the 4s?

What is a template?

A possible setting for one number (in all units) , so the question means, if it is a nishio solution - no.
ravel
 
Posts: 998
Joined: 21 February 2006


Return to Advanced solving techniques