Benchmark Sudoku List

Advanced methods and approaches for solving Sudoku puzzles

Postby RW » Wed Apr 19, 2006 7:49 pm

Havard wrote:Where does really Unique Rectangles fit into the solving hierarchy?


There is a problem related to this. Consider this grid:

Code: Select all
 *--------------------------------------------------*
 | 5    2    9    | 168  18   3    | 7    4    168  |
 | 4    3    6    | 189  7   *159  | 2   *1589 189  |
 | 1    8    7    | 2    4   *569  | 3   *59   69   |
 |----------------+----------------+----------------|
 | 3    14   58   | 189  6    2    | 45   7    189  |
 | 9    46   2    | 5    18   7    | 46   18   3    |
 | 7    16   58   | 4    3    19   | 56   189  2    |
 |----------------+----------------+----------------|
 | 2    9    4    | 16   5    16   | 8    3    7    |
 | 8    7    1    | 3    2    4    | 9    6    5    |
 | 6    5    3    | 7    9    8    | 1    2    4    |
 *--------------------------------------------------*


Here the UR lets us exclude candidate 9 from r2c6. However, if we first do some coloring on the 9's, we would exclude candidate 9 from r2c8, making the UR invisible to a computer solver that looks for certain candidates (but we could still make the same uniqueness reduction). This is more common than you think, I've seen lot's of these situations where techniques that exclude single candidates "destroy" uniqueness patterns. Therefore uniqueness techniques should be higher in the hirarchy than coloring XY-wing etc.

To make it a bit more confusing, take a look at this puzzle:

Code: Select all
 *-----------*
 |.56|.7.|...|
 |8..|.9.|.7.|
 |4..|.68|.2.|
 |---+---+---|
 |56.|9..|2..|
 |...|.8.|...|
 |..3|..7|.46|
 |---+---+---|
 |.9.|82.|..4|
 |.4.|.5.|..2|
 |...|.3.|96.|
 *-----------*


Simple sudoku gets this far:

Code: Select all
 *-----------------------------------------------------------*
 | 1     5     6     | 3     7     2     | 4     89    89    |
 | 8     3     2     |*14    9    *145   | 6     7     15    |
 | 4     7     9     | 15    6     8     | 15    2     3     |
 |-------------------+-------------------+-------------------|
 | 5     6     178   | 9     4     3     | 2     18    78    |
 | 27    12    4     | 26    8     56    | 3     159   79    |
 | 9     28    3     | 25    1     7     | 58    4     6     |
 |-------------------+-------------------+-------------------|
 | 36    9     15    | 8     2     16    | 7     35    4     |
 | 36    4     17    | 167   5     9     | 18    38    2     |
 | 27    128   1578  |*47    3    *14    | 9     6     15    |
 *-----------------------------------------------------------*


Again we can make the uniqueness reduction r9c4<>4 (UR: r29c46), but number 1 has been removed by coloring. This time however, the coloring was done a long time ago, at a point where the uniqueness rectangle wasn't visible yet. From that point it required two xy-wings to solve the cells that made this uniqueness rectangle visible. This means that in this particular case it doesn't matter where the uniqueness rectangles are in your hierarchy, if colors come before xy-wing the 1 would be removed from r9c4 anyway. Both the UR and the xy-wing has to come before coloring. But what if there is a puzzle where we need to do some coloring to find a uniqueness rectangle that can be destroyed with an xy-wing? Can you make a solver that could solve both of these puzzles? Or even worse, there might be puzzles where coloring removes a candidate from a UR that would be revealed by multiple colors on another number.

I don't program any solver myself, so this really doesn't consern me, but I always wondered how you tackle this problem.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Wed Apr 19, 2006 9:51 pm

Havard wrote:This post-initiative is great! Hope someone can find a worthy jellyfish substitute...

Take a look at these 4, especially the 3rd with 3 exclusions.

501094000020605900000000000000002017030040060000000500000000020000030800060809300
019000600000000080070250040300000000906000000020937000002800090000409001000060003
700002001000150080300000000100940602004010070007800000070000000000200069900003010
000080050930000700000601002698040500000000040500000208400020070069000000052000900

They are puzzles 311, 724, 739, and 1391 of the top1465.

[edit: After a more detailed look, #1391 may actually be the most interesting. Following two multi-color steps and an xyz-wing, there are three finned fish, one right after the other. First a finned x-wing, then a finned swordfish, and then a finned jellyfish. How cool is that?]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Ruud » Wed Apr 19, 2006 11:12 pm

Ron wrote:After a more detailed look, #1391 may actually be the most interesting. Following two multi-color steps and an xyz-wing, there are three finned fish, one right after the other. First a finned x-wing, then a finned swordfish, and then a finned jellyfish. How cool is that?

Cool. But not for this list.:(

I already found a new finned jellyfish, with minimal interference by other techniques. Unless somebody shoots it down, its going to be the replacement.

Having 2 multi-color steps and an xyz-wing with 3 filets in a single sudoku, how big are the chances that 2 solvers can replicate the 3 fish?

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Havard » Thu Apr 20, 2006 11:20 am

Ruud wrote:Please can you verify it before I put another misser in the list?
Ruud.


Sure! That one looks perfect to me!:)
Havard
 
Posts: 377
Joined: 25 December 2005

Postby RW » Thu Apr 20, 2006 11:50 am

Ruud wrote:For the benchmark list, I prefer isolated cases. If you can find a case with only singles and a reverse-BUG, I would appreciate it.


Adding 2 in r1c9 and 9 in r4c9 to the givens should solve this problem:

000070502000001060040560310012000609000000103009000420081040730050700000006038000

This puzzle requires only a reverse-BUG (which can be applied directly in the starting grid) and singles.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Thu Apr 20, 2006 12:05 pm

Ruud wrote:
Code: Select all
#Jellyfish with 2 tentacles
.---------------.---------------.---------------.
| 689  2    7   |*13   1346 146 |-19   5   *1389|
| 3    1    4   | 9    5    8   | 7    2    6   |
| 689  5    689 | 2    1367 167 | 4   #18  #1389|
:---------------+---------------+---------------:
| 2    68   168 | 4    1678 167 | 3    9    5   |
|*189  4    3   |*158  2    159 | 6    7    18  |
| 5    7    69  |*18   69   3   | 2   *18   4   |
:---------------+---------------+---------------:
| 678  368  5   | 378  38   19  | 19   4    2   |
| 4    89   18  | 6    189  2   | 5    3    7   |
|*17   39   2   |*1357 1349 1459| 8    6   *19  |

I tend to get seasick when fishing:) so I could be wrong, but ...

... with only one (non-fin) candidate in col 8, isn't this a sashimi jellyfish too?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Ruud » Fri Apr 21, 2006 1:40 am

Ron wrote:with only one (non-fin) candidate in col 8, isn't this a sashimi jellyfish too?

I only looked at the fact that there are real parts of fish in the box where the damage occurs. With one core candidate in that box, this must be the rare ikizukuri variety. That sole candidate is the beating heart of the otherwise gutted jellyfish.:D

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby ronk » Fri Apr 21, 2006 1:58 am

Ruud wrote:... this must be the rare ikizukuri variety. That sole candidate is the beating heart of the otherwise gutted jellyfish.:D

I could have gone a whole lifetime without learning that.:(
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby SHuisman » Sun Apr 23, 2006 8:35 am

Code: Select all
# 1 naked pair (1,8) in row 9, 1 hidden quad (1,3,6,8) in box 9
Code:
000005004000000910000900038000304507070080060803502000490003000025000000600700000
.------------------.------------------.------------------.
| 12379 8     12679| 26    123   5    | 267   27    4    |
| 237   4     267  | 268   23    678  | 9     1     5    |
| 127   5     1267 | 9     4     167  | 267   3     8    |
:------------------+------------------+------------------:
| 29    1     29   | 3     6     4    | 5     8     7    |
| 5     7     4    | 1     8     9    | 23    6     23   |
| 8     6     3    | 5     7     2    | 14    49    19   |
:------------------+------------------+------------------:
| 4     9     178  | 268   125   3    |*1278  257  *126  |
| 17    2     5    | 4     19    168  |*1378  79   *1369 |
| 6     3     18   | 7     259   18   | 24    2459  29   |
'------------------'------------------'------------------'


It also contains a quad in the bottom row !
with 245 and 9 ! Though you can't eliminate any cells.
SHuisman
 
Posts: 17
Joined: 23 March 2006

Postby gsf » Sun Apr 23, 2006 1:50 pm

SHuisman wrote:
Code: Select all
# 1 naked pair (1,8) in row 9, 1 hidden quad (1,3,6,8) in box 9
Code:
000005004000000910000900038000304507070080060803502000490003000025000000600700000
.------------------.------------------.------------------.
| 12379 8     12679| 26    123   5    | 267   27    4    |
| 237   4     267  | 268   23    678  | 9     1     5    |
| 127   5     1267 | 9     4     167  | 267   3     8    |
:------------------+------------------+------------------:
| 29    1     29   | 3     6     4    | 5     8     7    |
| 5     7     4    | 1     8     9    | 23    6     23   |
| 8     6     3    | 5     7     2    | 14    49    19   |
:------------------+------------------+------------------:
| 4     9     178  | 268   125   3    |*1278  257  *126  |
| 17    2     5    | 4     19    168  |*1378  79   *1369 |
| 6     3     18   | 7     259   18   | 24    2459  29   |
'------------------'------------------'------------------'


ruud, would you consider focusing the pencilmarks on the hidden quad
the pairs etc. leading up to it get in the way
Code: Select all
 139   8   19  | 26   13    5  | 267  27    4
 237   4   267 | 268  23   678 |  9    1    5
 127   5  1267 |  9    4   167 | 26    3    8
---------------+---------------+---------------
 29    1   29  |  3    6    4  |  5    8    7
  5    7    4  |  1    8    9  | 23    6   23
  8    6    3  |  5    7    2  | 14   49   19
---------------+---------------+---------------
  4    9   78  | 268  25    3  |1278  257  126
 17    2    5  |  4   19   68  | 38   79   36
  6    3   18  |  7   259  18  | 24  2459  29
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Tue May 09, 2006 6:33 pm

Ruud,

The Uniqueness test 4 can actually be a type 3 as the quantum cell forms a naked quad........

tarek
User avatar
tarek
 
Posts: 2631
Joined: 05 January 2006

Re: Benchmark Sudoku List

Postby maria45 » Fri Aug 04, 2006 12:51 pm

Hello Ruud,

your list is really impressive. But you wrote:
Ruud wrote:Techniques that depend on a unique solution

Some people feel uneasy about using uniqueness as a feature. One could of course subsume these uniqueness-examples under the more advanced forcing chains. In

Ruud wrote:# Uniqueness test 2
Code: Select all
000610000003000500095000078000004005042030760800500000410000620009000300000096000
.------------.------------.------------.
| 7   8   4  | 6   1   5  | 9   3   2  |
| 1   2   3  |*789-78 *789| 5   4   6  |
| 6   9   5  | 34  24  23 | 1   7   8  |
:------------+------------+------------:
| 9   3   16 | 17  67  4  | 2   8   5  |
| 5   4   2  |*89  3  *89 | 7   6   1  |
| 8   7   16 | 5   26  12 | 4   9   3  |
:------------+------------+------------:
| 4   1   8  | 37  5   37 | 6   2   9  |
| 2   6   9  | 148 48  18 | 3   5   7  |
| 3   5   7  | 2   9   6  | 8   1   4  |
'------------'------------'------------'

one could for example see this forcing chain:
r8c6=8, r2c5=8 or r8c6=1, r6c6=2, r6c5=6, r4c5=7, r2c5=8
which eliminates the 7 from r2c5 just as the uniqueness assumption does, only in a different way.

Greetings, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Postby Ruud » Sat Aug 05, 2006 12:29 am

Hi Maria,

Thanks for your input. The list is back on page 1:)

maria45 wrote:Some people feel uneasy about using uniqueness as a feature.


The list is not meant to defend any standpoint on uniqueness. I do have an opinion, but there are better places for this discussion. It is a list that shows selected examples for each technique. The puzzles have been selected in such a way that the fewest possible tricks are required to reach the state in which the technique can be shown.

There is no use in finding alternatives for the uniqueness step, because the puzzles were not selected for these alternatives. There are better examples for forcing chains.

Those people who want to avoid uniqueness-based methods should simply skip those examples.

cheers,
Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby unkx80 » Sat Sep 02, 2006 9:30 pm

Just to let you know, your uniqueness test 4 (*) example also contains a uniqueness test 1 (#), unless I have understood uniqueness constraints wrongly.

Code: Select all
000410000020090105006700090802000000000803000000000309080004500507080060000072000
.------------.------------.------------.
|*79 *79  5  | 4   1   8  | 6   3   2  |
| 4   2   8  | 3   9   6  | 1   7   5  |
| 3   1   6  | 7   2   5  | 8   9   4  |
:------------+------------+------------:
| 8   3   2  |#19  46 #179| 47  5   16 |
|*679*579 14 | 8   456 3  | 47  2   16 |
| 67  57  14 | 2   456 17 | 3   8   9  |
:------------+------------+------------:
| 2   8   9  | 6   3   4  | 5   1   7  |
| 5   4   7  |#19  8  #19 | 2   6   3  |
| 1   6   3  | 5   7   2  | 9   4   8  |
'------------'------------'------------'


Thanks for compiling this list!
unkx80
 
Posts: 7
Joined: 26 August 2006

Postby Obi-Wahn » Tue Apr 17, 2007 11:06 pm

It's a pity that this thread isn't kept uptodate anymore.:(
I think it's really helpful for anyone who's trying to code his own solver. So I'd like to contribute with a bunch of examples for Sue De Coq which I implemented lately. I realize that this technique doesn't seem to be very popular, but I'm not particularly fond of chains and a pattern technique like this is actually easier for me to find.
All of the examples can be solved with singles and Sue De Coq only

Ruud, I found that SudoCue captures only less than two thirds of the possible Sue De Coqs, so if you happen to look into this post you might want to check the extended examples. Only the first 4 are recognized by SudoCue.


Sue De Coq

# Basic form as devised by Sue De Coq in his original post
3 unsolved cells with 5 candidates in the intersection of row 5 and box 6 and one bivalue cell in each the row and the box.
Code: Select all
2..5.8...985...7............3......5....2....4...1.93...3..6.....2....6779.4.15.2
.------------------.------------------.-------------------.
| 2     167  147   | 5     469   8    | 146   149    3    |
| 9     8    5     | 13    46    23   | 7     124    146  |
| 3     16   14    | 17    469   27   | 12468 5      14689|
:------------------+------------------+-------------------:
| 6     3    179   | 79    8     47   | 12-4  127-4  5    |
| 5    @17   89-17 | 369-7 2     3-47 |*1468 *147   *1468 |
| 4     2    78    | 67    1     5    | 9     3     @68   |
:------------------+------------------+-------------------:
| 8     5    3     | 2     7     6    | 14    149    149  |
| 1     4    2     | 8     5     9    | 3     6      7    |
| 7     9    6     | 4     3     1    | 5     8      2    |
'------------------'------------------'-------------------'

{17} in the row, {68} in the box, {4} in the intersection and 7 eliminations


# Same pattern in column 9 and box 9
Code: Select all
..7.13.6..8...4.922....8..5.....5..9......24.1...8....3.........9....6..825..1...
.---------------------.---------------------.-------------------------.
| 9      5      7     | 2      1      3     | 48      6       @48     |
| 6      8      13    | 57     57     4     | 13      9        2      |
| 2      14     134   | 69     69     8     | 137     137      5      |
:---------------------+---------------------+-------------------------:
| 47     6      28    | 1347   2347   5     | 1378    1378     9      |
| 5      37     89    | 1379   379    679   | 2       4        367-18 |
| 1      347    29    | 3479   8      2679  | 357     357      367    |
:---------------------+---------------------+-------------------------:
| 3      147    6     | 45789  24579  279   | 4589-17 258-17  *1478   |
| 47     9      14    | 34578  23457  27    | 6       258-137 *13478  |
| 8      2      5     | 34679  34679  1     | 49-37  @37      *347    |
'---------------------'---------------------'-------------------------'

{48} in the column, {37} in the box, {1} in the intersection and 11 eliminations


# 2 unsolved cells with 4 candidates in the intersection of row 1 and box 1 and one bivalue cell each in the row and the box.
Code: Select all
.......5.96.8..4...3....9....764.......5....345.2..6..8...9...5...7.238....4.6.7.
.---------------.----------------.---------------.
|*127  4   *128 | 9   236-7  3-7 |@78   5   16-78|
| 9    6   @12  | 8   27     5   | 4    3   17   |
| 57   3    58  | 1   67     4   | 9    2   678  |
:---------------+----------------+---------------:
| 13   189  7   | 6   4      389 | 5    19  2    |
| 26   189  26  | 5   17     789 | 78   4   3    |
| 4    5    139 | 2   137    3789| 6    19  78   |
:---------------+----------------+---------------:
| 8    7    4   | 3   9      1   | 2    6   5    |
| 16   19   169 | 7   5      2   | 3    8   4    |
| 35   2    35  | 4   8      6   | 1    7   9    |
'---------------'----------------'---------------'

{78} in the row, {12} in the box and 4 eliminations


# 3 unsolved cells with 5 candidates in the intersection of column 3 and box 7, a bivalue cell in the box and a trivalue cell in the column.
Code: Select all
52.....6....59........83..4..81...564.5.....26......9..4.8..1......3198..........
.--------------------.------------------.------------------.
| 5     2       3    | 7     1     4    | 8     6     9    |
| 78    78      4    | 5     9     6    | 2     3     1    |
| 19    16     @169  | 2     8     3    | 5     7     4    |
:--------------------+------------------+------------------:
| 237   37      8    | 1     24    9    | 47    5     6    |
| 4     9       5    | 6     7     8    | 3     1     2    |
| 6     17      27-1 | 3     245   25   | 47    9     8    |
:--------------------+------------------+------------------:
| 39-7  4      *79   | 8     6     57   | 1     2     357  |
|@27    56-7   *267  | 4     3     1    | 9     8     57   |
| 138-7 1358-7 *17   | 9     25    257  | 6     4     357  |
'--------------------'------------------'------------------'

{169} in the column, {27} in the box and 5 eliminations


# 2 unsolved cells with 5 candidates in the intersection of column 3 and box 4, one bivalue cell in the column and 2 cells in the box.
Code: Select all
8..3...56.147...9.........16..4...89..2.9..........31...........76.5.......9.78.4
.-------------------.---------------.---------------.
| 8     29    @79   | 3    124  1249| 47   5    6   |
| 3     1      4    | 7    6    5   | 2    9    8   |
| 2579  6      5-79 | 28   248  2489| 47   3    1   |
:-------------------+---------------+---------------:
| 6     3     *17   | 4    127  12  | 5    8    9   |
|@15   @58     2    | 158  9    3   | 6    4    7   |
| 479-5 49-58 *5789 | 568  78   68  | 3    1    2   |
:-------------------+---------------+---------------:
| 1249  2489   138-9| 126  1234 1246| 19   7    5   |
| 149   7      6    | 18   5    148 | 19   2    3   |
| 125   25     135  | 9    123  7   | 8    6    4   |
'-------------------'---------------'---------------'

{79} in the column, {158} in the row and 6 eliminations


# 3 unsolved cells with 6 candidates in the intersection of row 5 and box 4, 2 cells each in the row and the box and an additional candidate in the box.
Code: Select all
.....5864......5...3..41..9.5.....4.......9.2..2.74..6.27.5......8......6.9.13...
.------------------.-------------------.------------------.
| 279   79    1    | 2379   239   5    | 8     6     4    |
| 2479  679   46   | 2789   289   2789 | 5     13    13   |
| 8     3     5    | 6      4     1    | 27    27    9    |
:------------------+-------------------+------------------:
|@179   5     36   | 12389  23689 2689 | 13    4     78   |
|*147  *678  *346  | 15-38 @368  @68   | 9     57-8  2    |
|@19    8-9   2    | 13589  7     4    | 13    58    6    |
:------------------+-------------------+------------------:
| 3     2     7    | 489    5     689  | 46    19    18   |
| 5     1     8    | 2479   269   2679 | 46    39    37   |
| 6     4     9    | 78     1     3    | 27    278   5    |
'------------------'-------------------'------------------'

{368} in the row, {179} in the box, {4} in the intersection and 4 eliminations


# 2 unsolved cells with 5 candidates in the intersection of column 1 and box 4, 3 cells in the column, 2 cells in the row and one additional candidate each in the column and the box.
Code: Select all
...7.....61.5.4........8.69......3....1.52...4..86.5.7....27..3.97....423........
.--------------------.------------------.------------------.
| 29-8  2348   23489 | 7     139   6    | 124   135   145  |
| 6     1      239   | 5     39    4    | 27    37    8    |
|@57    3457   345   | 2     13    8    | 14    6     9    |
:--------------------+------------------+------------------:
|*2589  568-2  568-29| 149   7     19   | 3     1289  146  |
|*789   678-3  1     | 349   5     2    | 4689  89    46   |
| 4    @23    @239   | 8     6     139  | 5     129   7    |
:--------------------+------------------+------------------:
|@158   4568   4568  | 169   2     7    | 1689  1589  3    |
|@15    9      7     | 136   8     135  | 16    4     2    |
| 3     2568   2568  | 169   4     159  | 16789 15789 156  |
'--------------------'------------------'------------------'

{1578} in the column, {239} in the box and 5 eliminations

[edit] Typos corrected. Thanks Mike.
Last edited by Obi-Wahn on Mon Apr 23, 2007 2:49 pm, edited 2 times in total.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

PreviousNext

Return to Advanced solving techniques