The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections

Postby ravel » Mon Jan 08, 2007 4:13 pm

Great puzzles, dml !

With my current program they are rated 27, 19 and 25* points, where the * after 25 means, that the first time my program had a grid, where no candidate could be eliminated with subnets under the constraint, that only possible eliminations were used (both for nets and there subnets), that would bring a progress of at least 3 candidates (in other words, when you eliminate the number and continue with basics, at least 2 more numbers can be eliminated). So the limit was lowered to a progress of 2, what means, that the calculation is much deeper and needs about 3 times longer.
This is the grid:
Code: Select all
 *--------------------------------------------------------------------*
 | 12679  2579    3     | 4      257    157    | 567    8     569     |
 | 1467   4578    1568  | 137    3578   9      | 2      567   34      |
 | 2479   245789  2589  | 237    6      3578   | 34     579   1       |
 |----------------------+----------------------+----------------------|
 | 2349   23489   7     | 369    1      45     | 3568   2569  235689  |
 | 1349   6       189   | 379    45     2      | 13578  1579  3589    |
 | 5      239     129   | 8      379    367    | 1367   4     2369    |
 |----------------------+----------------------+----------------------|
 | 2367   1       256   | 2367   23478  34678  | 9      256   24568   |
 | 8      2579    2569  | 12679  2479   1467   | 1456   3     2456    |
 | 2369   239     4     | 5      2389   1368   | 168    126   7       |
 *--------------------------------------------------------------------*

I calculated over 2000 solutions (in more than 2 hours!), that only differ in the last 5 steps. This is the first one:
Code: Select all
r1c1<>6(r7c8<>2,r6c7<>1,r1c2<>2),r7c9<>6,r9c8<>1(r8c2<>5,r5c8<>5,r7c9<>8,r4c8<>6,r2c3<>6,r1c1<>1),
r4c8<>6,r1c6<>1,r2c5<>3,r7c8<>5,r1c2<>9,r4c4<>6,r1c6<>5

How should i rate that ? My first thought is 5 extra points, but when i add other techniques, this situation probably will not arise and a better comparison is possible.

So these are the top 3 in the moment:
Code: Select all
dml 3/07: 30 points, ER 10.8
 +-------+-------+-------+
 | . . 3 | 4 . . | . 8 . |
 | . . . | . . 9 | 2 . . |
 | . . . | . 6 . | . . 1 |
 +-------+-------+-------+
 | . . 7 | . 1 . | . . . |
 | . 6 . | . . 2 | . . . |
 | 5 . . | 8 . . | . 4 . |
 +-------+-------+-------+
 | . 1 . | . . . | 9 . . |
 | 8 . . | . . . | . 3 . |
 | . . 4 | 5 . . | . . 7 |
 +-------+-------+-------+
Ocean's New Year present for RW: 28 points, ER 11.2
 +-------+-------+-------+
 | . . . | . . 1 | . 2 . |
 | 3 . . | . 4 . | 5 . . |
 | . . . | 6 . . | . . 7 |
 +-------+-------+-------+
 | . . 2 | . . . | . . 1 |
 | . 8 . | . 9 . | . 3 . |
 | 4 . . | . . . | 8 . . |
 +-------+-------+-------+
 | 5 . . | . . 2 | . . . |
 | . 9 . | . 3 . | 4 . . |
 | . . 6 | 7 . . | . . . |
 +-------+-------+-------+
dml 1/07: 27 points, ER 11.2
 +-------+-------+-------+
 | . . 3 | . . . | . . 9 |
 | 4 . . | . . . | . 2 . |
 | . 8 . | 6 . . | 1 . . |
 +-------+-------+-------+
 | 2 . . | . . 4 | . . . |
 | . 9 . | 8 . . | . . 7 |
 | . . 5 | . 3 . | . . . |
 +-------+-------+-------+
 | . . . | 9 . . | 8 . . |
 | . . . | . . 5 | . 3 . |
 | . 7 . | . 1 . | . . 6 |
 +-------+-------+-------+


Concerning the gsf rating, i was not aware of this kind of output for puzzles, that could not be rated (i saw the same now, when i scanned Ocean's puzzles), an older version wrote out "no solution". Maybe others can help you with the options.
Anyway, it seems that all your (and others') puzzles with a rating of 0 as the second number are non-rated.
If you have thousands of them, in the moment i would need a month to get a rating:( (I thought i would be safe with my performance for a while, because those puzzles are really hard to find).

But it would be nice, if you could post say 50 of them, this would help me to improve my program.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Mon Jan 08, 2007 6:18 pm

ravel wrote:Concerning the gsf rating, i was not aware of this kind of output for puzzles, that could not be rated (i saw the same now, when i scanned Ocean's puzzles), an older version wrote out "no solution". Maybe others can help you with the options.
Anyway, it seems that all your (and others') puzzles with a rating of 0 as the second number are non-rated.

I just posted a solver update that allows nested propositions
i.e., two concurrent guesses, which should be sufficient (or the backdoor conjecture is false)
and where sufficient means "no more no-solution for -qhardest"

the 3 puzzles should rate 99993 99992 99992
if you look at the rating formula it means 3, 2, and 2 guesses (which translates to 3, 2, and 2 nested propositions)

I don't view propositions and nested propositions as satisfactory solution techniques,
they are basically a tool for fleshing out puzzle difficulty
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Mauricio » Mon Jan 08, 2007 9:49 pm

Looking for sudokus with a symmetry property, I found several interesting sudokus and I'll introduce you 6 more not rated by gsfr (2006 version). They all have a 90 degree symmetry (after singles) (I have yet to find a move here that uses the symmetry technique).

This is a non minimal sudoku with 37 clues not rated by gsfr (2006 version).
Code: Select all
First SE step rating=11.0, 1 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains) with 34 views.
6 . .|. . 2|. 5 9
5 2 .|. 4 .|. 1 .
. . 3|5 . .|2 . .
-----+-----+-----
3 . .|1 9 4|5 . .
. 1 .|6 5 8|. 3 .
. . 5|2 7 3|. . 1
-----+-----+-----
. . 4|. . 5|1 . .
. 3 .|. 2 .|. 4 5
7 5 .|4 . .|. . 8 ER 11.0

So any minimal sudoku of it will have ER>=11.0 and not rated by gsfr (2006 version).

Two minimal versions of it,
Code: Select all
SE used 1 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains) with 34 views.
6 . .|. . 2|. . 9
. 2 .|. 4 .|. 1 .
. . 3|5 . .|2 . .
-----+-----+-----
. . .|1 9 4|5 . .
. 1 .|6 . .|. 3 .
. . 5|. 7 .|. . .
-----+-----+-----
. . 4|. . 5|1 . .
. 3 .|. 2 .|. 4 .
7 . .|. . .|. . 8 ER=11.0, it starts with 7 singles.


Code: Select all
First non trivial SE step is a Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains) with 34 views
6 . .|. . .|. . 9
. 2 .|. 4 .|. 1 .
. . 3|5 . .|2 . .
-----+-----+-----
. . .|. 9 .|5 . .
. 1 .|. . 8|. 3 .
. . 5|2 7 3|. . .
-----+-----+-----
. . 4|. . .|1 . .
. 3 .|. 2 .|. 4 5
7 5 .|4 . .|. . 8 ER=11.0, it starts with 10 singles, then a SE step of rating 11.0

SE took only 15 minutes to solve this puzzle! I have a P4 2.8Ghz running on windows xp. Note than when SE used the multiple
forcing chain, we have 37 cells given, a box (the central one) solved and a digit (5) solved.

4 more minimal not rated by gsfr, they are similar (but not isomorph) to the previous sudokus, they all start with 7 singles.
Code: Select all
300005002040010030009000800500090000020608040004200005006001700010030020400500001 ER=10.9
100005004040020030008000700500100000030608010000073005009002600010040020200500003 ER=10.9
700000006020030010001500400000190500040600020005273000002005300030010040800000009 ER=10.9
100500004070000060002030100020190005004008200500073000003010400080000090200005003 ER=10.9


We see that the last 6 puzzles don't follow tso's rule of thumb, the second minimal sudoku even has 1 box with 5 clues and 2 boxes with 4 each!
I would think that almost every reasonable pattern has a hard sudoku.

I'll check later the rating with the new gsf program.
Last edited by Mauricio on Fri Jan 12, 2007 4:18 pm, edited 1 time in total.
Mauricio
 
Posts: 1175
Joined: 22 March 2006

Postby ravel » Mon Jan 08, 2007 11:45 pm

From my programs point of view there is an essential difference between the 2 leader puzzles by dml and Ocean.
In Ocean's puzzle all the peaks (difficult grids) you have to get over only give you a few choices and are of about the same height for a long time. After getting over any one of them you have good chances to be on the right way to a short solution.
dml's puzzle has an extremely high peak at the beginning, and then leaves a lot of possibilities. Though it has a "shorter" solution at the end, the chances to find it quickly are worse.

But all this depends on the arsenal of techniques and strategies you put in. For SE, which has a lot of more implemented - and only uses one of them for a subnet - the peaks [edit] are different: 11.2 for Ocean's and 10.8 for dml's.

So i am curious about gsf's new approach - and Mauricio's nice puzzles.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Tue Jan 09, 2007 2:13 am

What a new development of puzzles by mauricio
The possible mechanism of the difficulty can be seen in the clue pattern in Boxes 2456&8

These are the possible minimal clues from the subgrid
Code: Select all
lines:240
   26  24
   27  120
   28  96


Here are the 26s, with suexrat9 rating [for what its worth]
580 , 6....2..9.2..4..1...35..2.....1945...1.6...3...5.7......4..51...3..2..4.7.......8
581 , 6.......9.2..4..1...35..2......9.5...1...8.3...5273.....4..51...3..2..4.7..4....8
585 , 6....2..9.2..4..1...35..2.....19.5...1.6.8.3...5..3.....4..51...3..2..4.7.......8
586 , 6.......9.2..4..1...35..2..3...945...1.6...3...527......4..51...3..2..4.7.......8
586 , 6....2..9.2..4..1...35..2.....1..5...1.6.8.3...5.73.....4..51...3..2..4.7.......8
587 , 6.......9.2..4..1...35..2......945...1.6...3...5273.....4..51...3..2..4.7.......8
587 , 6.......9.2..4..1...35..2......945...1.6.8.3...5..3..1..4..51...3..2..4.7.......8
587 , 6.......9.2..4..1...35..2..3..1..5...1.6.8.3...527......4..51...3..2..4.7.......8
587 , 6....2..9.2..4..1...35..2......945...1.6...3...5.7...1..4..51...3..2..4.7.......8
588 , 6.......9.2..4..1...35..2......9.5...1.6.8.3...5..3..1..4..51...3..2..4.7..4....8
588 , 6.......9.2..4..1...35..2......945...1.6...3...527...1..4..51...3..2..4.7.......8
588 , 6.......9.2..4..1...35..2.....19.5...1.6.8.3...52.3.....4..51...3..2..4.7.......8
588 , 6.......9.2..4..1...35..2.....1945...1...8.3...527......4..51...3..2..4.7.......8
589 , 6.......9.2..4..1...35..2.....19.5...1.6.8.3...5..3.....4..51...3..2..4.7..4....8
592 , 6.......9.2..4..1...35..2.....1..5...1.6.8.3...5.73.....4..51...3..2..4.7..4....8
592 , 6.......9.2..4..1...35..2.....1945...1.6...3...527......4..51...3..2..4.7.......8
593 , 6.......9.2..4..1...35..2......945...1...8.3...527...1..4..51...3..2..4.7.......8
593 , 6.......9.2..4..1...35..2.....1945...1.6.8.3...5..3.....4..51...3..2..4.7.......8
593 , 6....2..9.2..4..1...35..2..3..1..5...1.6.8.3...5.7......4..51...3..2..4.7.......8
594 , 6.......9.2..4..1...35..2......945...1...8.3...5273.....4..51...3..2..4.7.......8
594 , 6.......9.2..4..1...35..2.....1..5...1.6.8.3...5273.....4..51...3..2..4.7.......8
594 , 6.......9.2..4..1...35..2.....1.45...1.6.8.3...5.73.....4..51...3..2..4.7.......8
596 , 6.......9.2..4..1...35..2..3...9.5...1...8.3...527......4..51...3..2..4.7..4....8
598 , 6.......9.2..4..1...35..2..3...945...1...8.3...527......4..51...3..2..4.7.......8


I cant help feeling sympathy for the guys who are trying to write the rating software - moving goalposts come to mind !

Please could I ask how does the program decide which clues are envolved in the nested proposition technique. If it takes 3 guesses to get on the solving path - is this the minimum number found ie all combinations of 2 guesses didnt deliver ?

C
coloin
 
Posts: 2494
Joined: 05 May 2005
Location: Devon

Postby gsf » Tue Jan 09, 2007 2:32 am

coloin wrote:I cant help feeling sympathy for the guys who are trying to write the rating software - moving goalposts come to mind !

Please could I ask how does the program decide which clues are envolved in the nested proposition technique. If it takes 3 guesses to get on the solving path - is this the minimum number found ie all combinations of 2 guesses didnt deliver ?

there are only 6 puzzles up to isomorphism in the 26's
Code: Select all
6.......9.2..4..1...35..2......945...1...8.3...5273.....4..51...3..2..4.7.......8
6.......9.2..4..1...35..2......945...1.6...3...5273.....4..51...3..2..4.7.......8
6.......9.2..4..1...35..2......9.5...1.6.8.3...5..3..1..4..51...3..2..4.7..4....8
6.......9.2..4..1...35..2......9.5...1...8.3...5273.....4..51...3..2..4.7..4....8
6.......9.2..4..1...35..2......945...1...8.3...527...1..4..51...3..2..4.7.......8
6.......9.2..4..1...35..2......945...1.6...3...527...1..4..51...3..2..4.7.......8

the backdoor conjecture claims that the maximum minimal singles backdoor size is 2
or equivalently
each 9x9 sudoku has a backdoor of size at most 2 that when solved renders the puzzle solveable by singles only

even the hardest puzzles fall to the conjecture

the neat thing about the 6 puzzles above is that the singles backdoors (of size 2) are the same for all of the puzzles
Code: Select all
[13]8[86]6 [13]8[87]7 [23]9[97]6 [24]8[97]6 [38]8[71]9 [39]7[62]9 [39]7[72]6 [48]7[71]9

so 2 cells can deliver -- they just need to be one of the backdoors

the backdoor conjecture can be used to prune 9x9 backtrack tree search
using singles only every 9x9 sudoku can be solved with a maximal depth 2 tree search
(or the conjecture is disproved)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Tue Jan 09, 2007 3:30 am

Yes - i missed the symmetry that mauricio mentioned
and these are the bands
Code: Select all
C:\suxx>index416 mauricio2.txt
194 112 194  , 194 112 194

Thanks for the update on the backdoor clues
gsf wrote:the 3 puzzles should rate 99993 99992 99992
if you look at the rating formula it means 3, 2, and 2 guesses (which translates to 3, 2, and 2 nested propositions)

99993 - This cant mean 3 backdoor clues needed ?

C
coloin
 
Posts: 2494
Joined: 05 May 2005
Location: Devon

Postby gsf » Tue Jan 09, 2007 6:08 am

coloin wrote:Yes - i missed the symmetry that mauricio mentioned
and these are the bands
Code: Select all
C:\suxx>index416 mauricio2.txt
194 112 194  , 194 112 194

Thanks for the update on the backdoor clues
gsf wrote:the 3 puzzles should rate 99993 99992 99992
if you look at the rating formula it means 3, 2, and 2 guesses (which translates to 3, 2, and 2 nested propositions)

99993 - This cant mean 3 backdoor clues needed ?

the guesses could be in sequence or nested -- its just a total count for the solution
nested 3 deep only blows the conjecture if there exists no size 2 1 "0" backdoor
i.e., nested > 2 deep means some unlucky (non-backdoor) guesses
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Tue Jan 09, 2007 1:54 pm

good job everyone.......

it seems that -as coloin mentioned- the goalposts need shifting.......

that single nesting in SE will also be inadequate at some stage:D

as more programmers take on the challenge ..... I'm sure that moment is not far away......

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

Postby dml » Tue Jan 09, 2007 8:54 pm

gsf wrote:
the 3 puzzles should rate 99993 99992 99992
if you look at the rating formula it means 3, 2, and 2 guesses (which translates to 3, 2, and 2 nested propositions)


This one rates 99998 , what does it mean ?
006300000040070000100008200300900100070000040005000006900200008000060050000001300
This is in fact a canonical form of:
003000009400000020080600100200004000090800007005030000000900800000005030070010006
dml
 
Posts: 34
Joined: 12 November 2006

Postby Mauricio » Tue Jan 09, 2007 9:30 pm

Mauricio wrote:So any minimal sudoku of it will have ER>=11.0 and not rated by gsfr (2006 version).

The same thing can be said of this 4 non minimal sudokus (extracted from the examples I gave yesterday), though with ER>=10.9
Code: Select all
3 . .|. . 5|. . 2
. 4 .|. 1 .|5 3 .
. 5 9|3 . .|8 . .
-----+-----+-----
5 . .|1 9 4|2 . .
. 2 .|6 5 8|. 4 .
. . 4|2 7 3|. . 5
-----+-----+-----
. . 6|. . 1|7 5 .
. 1 5|. 3 .|. 2 .
4 . .|5 . .|. . 1


Code: Select all
1 . .|. . 5|. . 4
. 4 5|. 2 .|. 3 .
. . 8|4 . .|7 5 .
-----+-----+-----
5 . .|1 9 4|3 . .
. 3 .|6 5 8|. 1 .
. . 1|2 7 3|. . 5
-----+-----+-----
. 5 9|. . 2|6 . .
. 1 .|. 4 .|5 2 .
2 . .|5 . .|. . 3


Code: Select all
7 5 .|. . 1|. . 6
. 2 .|. 3 .|. 1 5
. . 1|5 . .|4 . .
-----+-----+-----
2 . .|1 9 4|5 . .
. 4 .|6 5 8|. 2 .
. . 5|2 7 3|. . 4
-----+-----+-----
. . 2|. . 5|3 . .
5 3 .|. 1 .|. 4 .
8 . .|3 . .|. 5 9


Code: Select all
1 . .|5 . .|. . 4
. 7 5|. . 1|. 6 .
. . 2|. 3 .|1 5 .
-----+-----+-----
. 2 .|1 9 4|. . 5
. . 4|6 5 8|2 . .
5 . .|2 7 3|. 4 .
-----+-----+-----
. 5 3|. 1 .|4 . .
. 8 .|3 . .|5 9 .
2 . .|. . 5|. . 3

Are they isomorph?

So one more method to produce sudokus with high ER is to select a difficult sudoku and solve it until the point which uses the hardest step, and then minimalize it (the majority of the sudokus given by Ocean and dml use their hardest step before solving a single cell, this does not help).
Mauricio
 
Posts: 1175
Joined: 22 March 2006

Postby dml » Tue Jan 09, 2007 11:42 pm

Mauricio wrote:
So one more method to produce sudokus with high ER is to select a difficult sudoku and solve it until the point which uses the hardest step, and then minimalize it (the majority of the sudokus given by Ocean and dml use their hardest step before solving a single cell, this does not help).


What difference does it make that the difficult steps are in beginning or middle or end of resolution?
Since we search some ultra hard sudokus we need just to find lot of hard steps
It seems to me the ranking favorize too much the hardest steps, notably ER since this is the single element of ranking
For me a sudoku with 12 steps rated at 10.0 can be for a human much harder than 1 sudoku that just require 1 single step at 10.2
But I should recognize I cannot clearly explain the difference in difficulty between 10.0 and 10.2 and I have not yet completed a ranking program then I am not in the position to argue too far, just a feeling
Also we should take into account the length of contradiction chains, do we?
Would be interesting to find the longuest chains:)
dml
 
Posts: 34
Joined: 12 November 2006

Postby gsf » Wed Jan 10, 2007 9:04 am

Mauricio wrote:Are they isomorph?

the 4 puzzles are the same up to isomorphism
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Wed Jan 10, 2007 12:33 pm

dml wrote:This one rates 99998 , what does it mean ?
006300000040070000100008200300900100070000040005000006900200008000060050000001300

It should mean lots of nested propositions. Let's see... pasting into SE 1.2... F9... wait... wait... make some coffee... wait... compose a short ambient piece for theremin and percussion... make some more coffee... have a shower... go to the shop... ah, finally!

ER 11.1,
11 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)
13 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)

That was 2½ hours for a Pentium M 1.7GHz, I wonder how long it would take a Carcul...:)

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

Postby JPF » Wed Jan 10, 2007 1:58 pm

RW wrote:
dml wrote:This one rates 99998 , what does it mean ?
006300000040070000100008200300900100070000040005000006900200008000060050000001300

ER 11.1
That was 2½ hours for a Pentium M 1.7GHz, I wonder how long it would take a Carcul...:)

Just make the mutation r2c2 : 4->5 : you will drink less coffee:D

JPF
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

PreviousNext

Return to General