The New Sudoku Players' Forum

[Karlson]

Here are a few very hard sudokus - I would like to see how you (or your solvers) would solve it without guessing. Moreover I'm interested wether there are higher fishes (also the rotten sealife like Frankenfish') in there.

#1:

Code: Select all

6..9.5..79.......8.7..8..3...73.68.............317.5...9..5..2.2.......17..6.....

Code: Select all

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

#2:

Code: Select all

..8....5.7.562.83.1.....2.....1..6.....4.7......398.....3....7.6.7.3.12.8.....5..

Code: Select all

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

#3:

Code: Select all

.........5....836..2..9..5.96..2.13.87..435....21...............4..3.79.6....521.

Code: Select all

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

I already posted them in the programmers board, but I think not everybody is registered there ;)
Regards Karlson

[Havard]

Hi and welcome to the forum!

I pm'ed you with a solution for #1. It was so long that it was not suited for posting... (spam, spam, spam, spam etc...)

Havard

[Havard]

And since you have an interest for sealife... Here are three consecutive steps from #3:

Code: Select all

Swordfish in rows: 2 4 9
1347    1389    346789- | 234567- 1567    1246    | 489     478     124789-
5       19      479X    | 247X    17      8       | 3       6       12479X
1347    2       34678-  | 3467-   9       146     | 48      5       1478-
------------------------+-------------------------+------------------------
9       6       45X     | 58      2       7       | 1       3       48X
8       7       1       | 69      4       3       | 5       2       69
34      35      2       | 1       58      69      | 4689    478     46789-
------------------------+-------------------------+------------------------
1237    13589   35789   | 24789-  1678    12469   | 468     48      34568-
12      4       58      | 268     3       126     | 7       9       568
6       389     3789    | 4789X   78      5       | 2       1       348X

4  .  4- | 4- .  4  | 4  4  4-
.  .  4X | 4X .  .  | .  .  4X
4  .  4- | 4- .  4  | 4  .  4-
---------+----------+---------
.  .  4X | .  .  .  | .  .  4X
.  .  .  | .  4  .  | .  .  .
4  .  .  | .  .  .  | 4  4  4-
---------+----------+---------
.  .  .  | 4- .  4  | 4  4  4-
.  4  .  | .  .  .  | .  .  .
.  .  .  | 4X .  .  | .  .  4X


Frankenfish in columns: 5 7 8
1347  1389  36789 | 23567 1567  1246  | 489X  478X  12789
5     19    479   | 247   17    8     | 3     6     12479
1347  2     3678  | 367   9     146   | 48X   5     178
------------------+-------------------+------------------
9     6     45    | 58    2     7     | 1     3     48
8     7     1     | 69    4     3     | 5     2     69
34    35    2     | 1     58X   69    | 4689X 478X  6789
------------------+-------------------+------------------
1237  13589 35789 | 2789- 1678X 12469 | 468X  48X   3568
12    4     58    | 268   3     126   | 7     9     568
6     389   3789  | 4789  78X   5     | 2     1     348

.  8  8  | .  .  .  | 8X 8X 8
.  .  .  | .  .  8  | .  .  .
.  .  8  | .  .  .  | 8X .  8
---------+----------+---------
.  .  .  | 8  .  .  | .  .  8
8  .  .  | .  .  .  | .  .  .
.  .  .  | .  8X .  | 8X 8X 8
---------+----------+---------
.  8  8  | 8- 8X .  | 8X 8X 8
.  .  8  | 8  .  .  | .  .  8
.  8  8  | 8  8X .  | .  .  8


Finned Swordfish in rows: 3 4 8
1347   1389   36789  | 23567  1567   1246   | 489    478    12789-
5      19     479    | 247    17     8      | 3      6      12479
1347   2      3678X  | 367    9      146    | 48X    5      178X
---------------------+----------------------+---------------------
9      6      45     | 58X    2      7      | 1      3      48X
8      7      1      | 69     4      3      | 5      2      69
34     35     2      | 1      58     69     | 4689   478    6789
---------------------+----------------------+---------------------
1237   13589  35789  | 279    1678   12469  | 468    48     3568
12     4      58X    | 268X   3      126    | 7      9      568X
6      389    3789   | 4789   78     5      | 2      1      348

.  8  8  | .  .  .  | 8  8  8-
.  .  .  | .  .  8  | .  .  .
.  .  8X | .  .  .  | 8X .  8X
---------+----------+---------
.  .  .  | 8X .  .  | .  .  8X
8  .  .  | .  .  .  | .  .  .
.  .  .  | .  8  .  | 8  8  8
---------+----------+---------
.  8  8  | .  8  .  | 8  8  8
.  .  8X | 8X .  .  | .  .  8X
.  8  8  | 8  8  .  | .  .  8


enjoy!

Havard

[Karlson]

Thanks to everybody who send me a solution - I got some interesting things there.
... and thanks for welcoming me to the forum
Has anybody managed to solve #2 without guessing? If yes maybe it is possible to post the critical steps which are necessary (so the forum does not get flooded ;) )

Regards Karlson

[ravel]

Has anybody managed to solve #2 without guessing?

My program would solve it with one of the following orders of brute force eliminations (setting a cell to the number to eliminate leads to a contradiction - earlier or later - with basic methods):

Code: Select all

r1c1<>4, r7c7<>4, r6c2<>6
r2c9<>4, r7c7<>4, r6c2<>6
r9c8<>9, r7c7<>4, r6c2<>6
r3c8<>9, r1c2<>2, r1c7<>9
r6c3<>1, r1c2<>2, r1c7<>9
r1c1<>9, r7c1<>9, r6c3<>1
r9c3<>4, r3c3<>4, r3c3<>6
r9c3<>9, r7c1<>9, r1c2<>2

[Karlson]

What about this one:
#4

Code: Select all

23.........1.2...774....8..4...91....2.4.5..8...87.6...7..8..9.1.....3.5.9....7.1

Code: Select all

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

It took me quite a time to generate it - I hope it is hard ;)

Regards Karlson

[ravel]

#2 is harder for my program, for this one it needs 2 (long) steps:

Code: Select all

r2c1<>9, r2c7<>9
r2c7<>9, r3c6<>9

[Karlson]

Are these guessing/brute force - steps or very long chains? Would be nice to see the log for these implications.

[daj95376]

Not a very good reply, so I dropped it.

[ronk]

"brute force eliminations" <=> BFE

Is that another term for "elimination by contradiction?" If so, doesn't that mean either ...

• assert a candidate, or
• negate a candidate

... to see if a contradiction results?

If so, even though you could write multiple implication chains to express the contradition, it still seems like "guessing".

[daj95376]

Dropped this one, too.

[gsf]

I've seen a lot of arguments on where technique ends and guessing begins. I'm not going to get in the middle of it.

I'm not versed on the specific definitions of all the different techniques. However, my BFE overlaps both components of elimination by contradiction as you've described it.

you're in the middle of it

here's my take on the issue and also the basis for my interest in sudoku
(the intermingling of algorithms, graph theory and group theory)

{ chains, cycles, xwings, swordfish } are entities that exist outside of guessing
e.g., a swordfish in 1's, an x-cycle in 5's
these entities are typically characterized by some ordering of vertices (cells) and edges (relationships between vertices)

an algorithm that detects cycles etc. may look like guessing, but that would be
a property of the algorithm, not the entity under question

assigning a value to a cell and letting the solver loose, restricted to singles or not,
produces either a solution, a contradiction, or dontknowyet
the characterization is at best a cell, a value, and something that for all intents and purposes
is a trace of the algorithm used to propagate the singles (or whatever constraints are in effect)

to date no one has posted a reliable technique for picking the BFE (or whatever) cell
or value to be assigned, other than maybe the cells with least number of candidates
put another way, given a BFE cell and value there is (currently) no way to predict
the outcome { solution contradiction dontknowyet } save propagating the constraints
a related issue is selecting cells with small ripple effects that still produce useful results

in contrast, given a swordfish or x-cycle or xy-cycle, the structure of the
entity determines the affected cells and values
basically the guesswork or conditional logic (if this cell has this value then that cell ...)
is a property of the structure itself

[daj95376]

Another inappropriate post.

[ravel]

Are these guessing/brute force - steps or very long chains? Would be nice to see the log for these implications.

My solvers output is not in a form, that i could post it here. But as an example my first step for #2 can be written this way (i left out some unnecessary steps and finished with an earlier contradiction than the solver found). It starts from this situation (after basics and the UR type 3 in r56c19 plus 49 in r4c3)

Code: Select all

249   23469   8     |  79     147    1349   |  479   5      14679     
7     49      5     |  6      2      149    |  8     3      149       
1     3469    469   |  5789   478    3459   |  2     469    4679       
-----------------------------------------------------------------
3     78      49    |  1      5      2      |  6     489    479       
259   1258    12    |  4      6      7      |  3     189    25         
245   12567   126   |  3      9      8      |  47    14     25         
-----------------------------------------------------------------
2459  12459   3     |  2589   148    14569  |  49    7      4689       
6     459     7     |  589    3      459    |  1     2      489       
8     1249    1249  |  279    147    1469   |  5     469    3         

r1c1=4 (=> r1c7<>4)
r1c1=4 => r4c3=4
r1c1=4 => r2c2=9 => r3c3=6 => r6c3=12 => r5c1=5 => r5c2=8 => r4c8=8
r5c2=8 => r4c2=7 => r6c7=7 (=> r6c7<>4) => r6c8=4 => r5c8=1 => r4c9=9
r3c3=6 => r1c9=6 => r9c8=6 => r7c7=9 => (r7c7<>4)
no 4 in column 7

The other 2 steps are even longer, but they lead to a contradiction in basically the same way.

If so, even though you could write multiple implication chains to express the contradition, it still seems like "guessing".

I thought, this discussion is eaten this forum. My opinion is simple:

Guessing means, that you set or eliminate a number without proof.
If you "try" a number and show that it leads to a contradiction, you have a proof, that it can be eliminated.

The process of proving this way is about the same as after guessing.
Hard puzzles cannot be solved without some similar process of trying, if some advanced technique is applicable.

Chains like the one from my solver output above are proofs (if i did not make a mistake), but no one is interested in them, because they are not elegant and too long. But the ultra tough puzzles in the moment seem to be not solvable without such long deductions.

[gsf]

Okay, I'm up for a good argument -- even when I'm pretty sure that I'm wrong.

there's plenty of wiggle room in this one

Remote Pairs is an accepted technique that involves selecting a cell with two candidates and chaining through identical cells to see if an elimination can be performed on a cell outside the chain. Elimination can only occur at points where the chain has an even number of cells in it.

Now, go ahead and explain to me how anyone starting such a chain has any guarantee that it's going to include an even number of cells AND an elimination is going to occur from it. This process is just as likely to return a contradiction or don't-know-yet state as my BFE.

remote pairs are handled by xy-cycles in my solver
so they fall out of the cycle code and are never identified as remote pairs

but you make a good point that there is a distinction for human solvers --
time spent on unproductive long chains is time wasted
and to be fair there may be some cycles ithat do not progress the solution

it turns out that sudoku lends itself to efficient global (breadth-first-like) cycle detection
unlike depth first search, which essentially makes a guess at the first cycle vertex
the global search just crunches and the cycles fall out

I guess my point is that "this cycle implies ..." is more satisfactory than
"this cell with this value implies ...", the former holds the possibility of
neat algorithms / pattern recognition, the latter offers brute force

PS: Thanks for posting a great backtracking solver to the Sudoku Programmers' Forum!!!

you're welcome