The New Sudoku Players' Forum

[MadOverlord]

One of my Susser users clued me in that Dusoko's Top87n list has a puzzle in it that the Susser can't solve -- even with fully-aggressive tabling!

It's #2 in the list

Code: Select all

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

The Susser only solves one square (and does a bunch of reductions) before it curls up and starts whimpering. So clearly, either there's a bug or an omission in my tabling algorithm, or this is a new class of evil puzzle!

I am leaning towards a bug/omission, because after tabling fails, Bowman Bingo is able to make a bit of progress.

[Nick70]

Wow. My program cannot solve it either without guessing.

This is the first example I find of a puzzle that cannot be solved even by forcing nets. Since those are equivalent to tabling, there doesn't seem to be a bug in your algorithm.

[ronk]

One of my Susser users clued me in that Dusoko's Top87n list has a puzzle in it that the Susser can't solve -- even with fully-aggressive tabling!

That's the same as puzzle #2 in dukuso's top1465 that I'm unable to solve. Can you solve #77?

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|
 *-----------*


Also, do you have a link for the "Top87n"?

[Nick70]

That's the same as puzzle #2 in dukuso's top1465 that I'm unable to solve. Can you solve #77?

That's the only other puzzle in the top1465 that my program cannot solve.

[ronk]

That's the only other puzzle in the top1465 that my program cannot solve.

Same here ... after fixing a design deficiency to solve two others. After one fill, sticking point for #2 is ...

Code: Select all

 7       126     8       | 459     4569    4569    | 3       1456    125
 49      36      3469    | 2       3456    1       | 4679    4578    578
 5       1236    123469  | 78      346     78      | 2469    146     129
-------------------------+-------------------------+----------------------
 189     4       1579    | 3579    59      3579    | 178     2       6
 3       1267    1269    | 479     8       24679   | 147     1457    157
 268     2578    2567    | 1       2456    2467    | 478     9       3
-------------------------+-------------------------+----------------------
 128     9       1357    | 6       125     2358    | 127     1378    4
 12468   12368   12346   | 3489    7       23489   | 5       1368    1289
 12468   3578    1234567 | 34589   1249    234589  | 12679   13678   12789


Also after one fill, sticking point for #77 is ...

Code: Select all

 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     


[Ruud]

One of my Susser users clued me in that Dusoko's Top87n list has a puzzle in it that the Susser can't solve -- even with fully-aggressive tabling!

Same with Sudo Cue using aggressive tabling.

I did some manual checks. At some stage, it requires line-box interactions and subsets inside the tabling process. Only then will the implication trees grow large enough to reveal inconsistencies. I've seen these before, but never found a puzzle that actually depends on them to be solved.

We have a new winner here. I will post these in the programmers forum. I'm really curious if anyone has the remedy for these 2.

Ruud.

[MadOverlord]

That's the same as puzzle #2 in dukuso's top1465 that I'm unable to solve. Can you solve #77?

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|
 *-----------*


Yes, the Susser, using Aggressive Forces and Pins, nails it.

Also, do you have a link for the "Top87n"?

Sure: http://magictour.free.fr/topn87

[MadOverlord]

I did some manual checks. At some stage, it requires line-box interactions and subsets inside the tabling process. Only then will the implication trees grow large enough to reveal inconsistencies. I've seen these before, but never found a puzzle that actually depends on them to be solved.

Nice catch that you can table subsets/hidden sets/implications. I'm not looking forward to coding it, though...

[Lummox JR]

Wow, that's quite an amazing puzzle. My solver too fails on it.

I'm curious what constraint subsets could do to this one, but I suspect it isn't much.

[bennys]

I found a way to show that r7c5<>5 for some reason after that Susser manage to solve it I wonder why it makes such difference?

[Ruud]

I've done some tests on this little monster:

Code: Select all

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

With only singles and line-box interactions, no magic cells are available.

R1C9D5 followed by R4C3D7 does completely solve the puzzle. I have not fully tested for all other magic pairs, however, a few other combinations do seem to work.


With singles, line-box interactions & naked & hidden subsets, the magic cells are:

R4C3D7
R6C6D7

To prove any of these 2, at least 3 competing candidates must be eliminated:

R4 C3 D159 or
R6 C237 D7 or
R345 C6 D7 or
R4 C467 D7

Building proof chains for these is extremely difficult, since I have to do this by hand

Interestingly, after placement of R1C9D5, this candidate list is formed:

Code: Select all

.------------------.------------------.------------------.
| 7     2     8    | 9     4     6    | 3     1     5    |
| 9     3     4    | 2     5     1    | 6     7     8    |
| 5     1     6    | 78    3     78   | 2     4     9    |
:------------------+------------------+------------------:
| 1     4     57   | 57    9     3    | 8     2     6    |
| 3     6     9    | 4     8     2    | 1     5     7    |
| 8     57    2    | 1     6     57   | 4     9     3    |
:------------------+------------------+------------------:
| 2     9     35   | 6     1     58   | 7     38    4    |
| 4     8     1    | 3     7     9    | 5     6     2    |
| 6     57    357  | 58    2     4    | 9     38    1    |
'------------------'------------------'------------------'

Does anyone spot a BUG here?


With all solving methods enabled, except tabling, these are magic cells:

R1C9D5
R2C5D5
R2C7D6
R2C8D7
R3C7D2
R4C3D7
R6C3D2
R6C6D7
R7C1D2
R7C7D7
R8C9D2


With tabling enabled, every cell is a magic cell, with the exception of:

R2C1D9
R2C2D3
R3C5D3
R6C9D3

Ruud.

[MadOverlord]

Does anyone spot a BUG here?

Yes, that's clearly a single-polysquare BUG.

[MadOverlord]

I updated the Susser so that Tabling now makes note of Intersections as well as Forces and Pins. This cracks the puzzle after generating 101960 implications! It requires Aggressive Forces and Pins.

As time permits, I'll add Naked and Hidden set implications to the Tabling code, to see if that eliminates the need for AF&P.

Kudos to Dukuso for finding it, and Ruud for realizing that intersections and sets were the path to nailing it.

[Darth Tater]

It's #2 in the list

Code: Select all

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

This one is pretty tough but I got it:

7 2 8 9 4 6 3 1 5
9 3 4 2 5 1 6 7 8
5 1 6 7 3 8 2 4 9
1 4 7 5 9 3 8 2 6
3 6 9 4 8 2 1 5 7
8 5 2 1 6 7 4 9 3
2 9 3 6 1 5 7 8 4
4 8 1 3 7 9 5 6 2
6 7 5 8 2 4 9 3 1


(*Oh by the way...first post here ever!*)

The other one...
7 9 8 6 3 5 4 2 1
1 2 6 9 7 4 5 8 3
4 5 3 2 1 8 6 7 9
9 7 2 5 8 6 3 1 4
5 6 4 1 2 3 8 9 7
3 8 1 4 9 7 2 5 6
6 1 7 3 5 2 9 4 8
8 3 5 7 4 9 1 6 2
2 4 9 8 6 1 7 3 5

[rubylips]

After one fill, sticking point for #2 is ...

Code: Select all

 7       126     8       | 459     4569    4569    | 3       1456    125
 49      36      3469    | 2       3456    1       | 4679    4578    578
 5       1236    123469  | 78      346     78      | 2469    146     129
-------------------------+-------------------------+----------------------
 189     4       1579    | 3579    59      3579    | 178     2       6
 3       1267    1269    | 479     8       24679   | 147     1457    157
 268     2578    2567    | 1       2456    2467    | 478     9       3
-------------------------+-------------------------+----------------------
 128     9       1357    | 6       125     2358    | 127     1378    4
 12468   12368   12346   | 3489    7       23489   | 5       1368    1289
 12468   3578    1234567 | 34589   1249    234589  | 12679   13678   12789


The Disjoint Subset link helps here.

Code: Select all

Consider the chain r2c1-9-r4c1~9~r4c5~5~r2c5+<5|7>+r2c7.
When the cell r2c7 contains the value 9, some other value must occupy the cell r2c1, which means that the value 7 must occupy the cell r2c7 - a contradiction.
Therefore, the cell r2c7 cannot contain the value 9.
- The move r2c7:=9 has been eliminated.


When r2c5 doesn't contain the value 5, the values 3, 4, 6 and 9 are shared between the cells r2c1, r2c2, r2c3 and r2c5, which means that r2c7 has to contain the value 7.