## The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections
Dml wrote:if I made no mistake this sudoku called "dml1" is rated 99995

4....9....3..1..2...67.......1.....4.5.2...7.8.....6.......4..8.7..3..1....5..9..

Dml, let me congratulate you for this truly amazing Sudoku puzzle. Its remarkable how someone is able to generate such an hard puzzle.
I must confess that, until today, Dml1 Puzzle was the Sudoku that I most enjoyed solving. One of the things that surprised me is that Dml1 is considerably harder than Puzzle 77, as required be its higher rating. One of these days I will post the way I have solved it.
I also realized that Dml1 is precisely the type of puzzle I was waiting for. Is that possible for you, or others, to make harder puzzles? Thanks.

Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Carcul wrote:
Dml wrote:if I made no mistake this sudoku called "dml1" is rated 99995

4....9....3..1..2...67.......1.....4.5.2...7.8.....6.......4..8.7..3..1....5..9..

Dml, let me congratulate you for this truly amazing Sudoku puzzle. Its remarkable how someone is able to generate such an hard puzzle.

this puzzle joins 2 others (at the top) where the constraint propagation technique
requires multi-coloring
here are the puzzles with their stats
two "gsf" ratings, the first with -X on (propositions not allowed to discover backdoors),
the second normal (propositions allowed to discover backdoors)
dml1 requires 10 and 8 propositions respectively, and the previous in this
class 7/5 and 6/5 respectively (the P stat)

all 3 puzzles have multi-coloring backdoor size 2 (the M (magic) stat)

#100015:C21.m/F369.1179/N586.1360/B496.1260.468.41/T82.149.74.7.1/H113.205.112.1/W140.734.104.36/X260.395/Y118.284.12.34.5.2/P10.67.672.0.49.2772.31/M2.31.211/V9
##99995:C21.m/F224.497/N553.1195/B483.1227.456.42/T74.135.67.6.1/H109.201.108.1/W130.654.95.35/X254.387/Y99.232.6.24.5.2/P8.24.622.1.21.2500.31/M2.31.211/V9

Code: Select all
`4....9....3..1..2...67.......1.....4.5.2...7.8.....6.......4..8.7..3..1....5..9..`

##99980:C22.m/S4.da/F244.964/N268.830/B174.528.161.35/T55.160.43.9.3/H20.43.19.1/W12.42.3.9/X220.395/Y54.155.6.7.2/P7.39.240.0.31.1245.20/M2.28.234/V9
##99960:C22.m/S4.da/F120.422/N219.623/B141.427.136.17/T44.119.36.6.2/H16.35.16/W9.35.2.7/X204.375/Y37.108.4.3.1/P5.19.199.5.13.966.20/M2.28.234/V9

Code: Select all
`.6.9....35....4.2.....8.4..8......5...3...7...9......1..1.5.....7.3....99....2.4.`

##99970:C22.m/S4.da/F198.752/N135.340/B98.324.82.28/T36.113.28.8/H34.67.33.1/W16.67.10.6/X80.99/Y34.102.1.10.3/P6.41.135.0.28.721.21/M2.39.168/V9
##99960:C22.m/S4.da/F115.379/N125.295/B95.316.80.27/T31.88.23.8/H34.67.33.1/W15.64.9.6/X80.99/Y33.101.1.10.3/P5.19.111.3.12.606.21/M2.39.168/V9

Code: Select all
`..1..2....3..4..5.6..7..8....6.....7.1.....3.9.....6....7..1..8.4..3..2....5..9..`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf,

please can you update the windows executable on your site ? The version i downloaded today (2006-09-27) still does not rate the hardest with the '-q hardest' option.
There are 5 more puzzles now, dml #2,3,4,5,6, that seem to need multicoloring also (see top page).
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:The version i downloaded today (2006-09-27) still does not rate the hardest with the '-q hardest' option.
There are 5 more puzzles now, dml #2,3,4,5,6, that seem to need multicoloring also (see top page).

the -V option lists the version
could there be a browser cache that far out of date?
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf wrote:this puzzle joins 2 others (at the top) where the constraint propagation technique
requires multi-coloring
here are the puzzles with their stats
two "gsf" ratings, the first with -X on (propositions not allowed to discover backdoors),
the second normal (propositions allowed to discover backdoors)

using the -X option I report the list of non canonical forms that maximize the 2 notations: second with -X

99995 100017 100009000040030020005700000008000001060002090300000500000006007090040030000500800 dml1
99984 99984 100005000020090030006400000004000006030008020700000100000003005080070090000200400 dml2
99972 99984 800003000050020040009100000001000008040700020600000900000008003070050010000400600 dml3
99961 99971 800003000070060090004500000002000004030001070500000800000009001060070030000200500 dml4
99957 99987 400009000050010030006700000007000008030000010900002400000008007010050060000400200 dml5
99956 99966 100004000020070090003500000008000004090030060500000700000001005070080030000600200 dml6
99951 99951 800003000070060090004500000005000004060007080200000100000008002030090060000100500 dml7
99948 99958 900004000050080070001200000002600009030000040700000500000009002080050030000700600 dml8
99921 99953 100007000040050020006800000005090003020000040700000100000003005090040060000100800 dml9
dml

Posts: 34
Joined: 12 November 2006

Thanks, my mistake, i had not noticed, that my downloader renamed it to sudodu-1, because i already had the older version in that directory. I updated my description how to get ratings there.

For some puzzles there is a significant difference in the 2 ways of rating:
99325 3 2 / 99985 9 7 Ocean's Anemone
99527 5 2 / 99963 9 5 Ocean #3/gold list
99851 8 4 / 99984 9 7 Ocean #4/gold list
99687 6 8 / 99859 8 5 Ocean #1/gold list

So i added another top list in the first post of this thread.
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:For some puzzles there is a significant difference in the 2 ways of rating:

yeah, there was enough consternation about using backdoors, even when all
possibilities are checked, for me to add -X

this version also has a -P option that reads pairs of input puzzles
if an odd-even pair has the same canonical solution then the
value/row/col permutations that map the odd (first) puzzle to the even (second)
puzzle are listed -- I can't think of anything (sudoku related) more tedious
than figuring out permutations by hand

gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

tso wrote:...rule of thumb:
"Puzzles in which no two clues are in two groups are more likely to be very difficult others."

Made another test now. The first time i had generated 1 mio random puzzles and with some luck i found one, which qualified at the end of my list. This time i used a modified version of dukusos suexg to generate 300000 puzzles with this arbitrary chosen pattern, which follows tso's rule of thumb (the generation took some days like for the mio):
Code: Select all
` +-------+-------+-------+ | x . . | . . x | x . . | | . . . | . x . | . x . | | . x . | x . . | . . x | +-------+-------+-------+ | . x . | x . . | . . x | | x . . | . x . | . x . | | . . . | . . x | x . . | +-------+-------+-------+ | . x . | . . . | . . . | | . . x | . . x | x . . | | x . . | . x . | . . x | +-------+-------+-------+`
Not surprising the puzzles were much harder in average (40% have gsf rating > 99000, 0.7% > 99300, 7 puzzles > 99500). Those are the 2 hardest i found (RMS/ER/gsfr/gsfr-X), both in the current top 40 (5 months ago i would have been leader )
In the first one the minimal version did not need the clue in r1c6. Note that in the second r1c5=1 is a hidden single, so in some sense it does not even follow the thumb rule.
Code: Select all
`19/9.9/99619/997001.....9......4..6..5.8....2.8.7....96...3..1......92...4.........2..57..3...6...816/9.9/99760/997902....58......4..3..1.7....5.5.1....94...8..6......93...6.........7..19..8...2...3`

So i think, i can confirm tso's rule, but the question is open, if certain patterns according to this rule are more fruitful than others.

Above 13 steps i only found 2 puzzles not following this rule: Ocean 1#vert.symm. (20/9.4) and Ocean's BB (15/9.8).
ravel

Posts: 998
Joined: 21 February 2006

I searched puzzles with no more than 3 clues in every column, row and box, and found this very large pearl.

Code: Select all
`1..9...7..5...7..9....4.6.......38..2..6....5..4.5..6...1..8..6.9.1..7..8...2..1.`

It is not as hard as Ocean Pearl. My pearl starts with a SE 9.4 chain, final rating 9.8.
Mauricio

Posts: 1174
Joined: 22 March 2006

ravel wrote:So i think, i can confirm tso's rule, but the question is open, if certain patterns according to this rule are more fruitful than others.

Above 13 steps i only found 2 puzzles not following this rule: Ocean 1#vert.symm. (20/9.4) and Ocean's BB (15/9.8).

Yes the pattern is one KEY to get very high sudokus
I found that some patterns generate 99+% of >99200 But 100% <99300 !!!

Then statistical studies will discover optimal patterns with high density of high ranked sudoku
But not sure the highest sudokus will not be found in a low density pattern
The problem is compute time

Then the best strategy seems to explore all patterns and make statistics over a period of time and search extensivelly only the richest patterns

some have 90+% of 99000+ and 30% of 99300+
Probably this is the only place where you have a chance to find top ranking because after the percentages drop rapidly
99400 are always very rare
You will find much more 99500 that 99400
After this is more logic

Is it just for my patterns or more generic?
dml

Posts: 34
Joined: 12 November 2006

dml wrote:I found that some patterns generate 99+% of >99200 But 100% <99300 !!!
I suppose with few clues (19-21)?
Then statistical studies will discover optimal patterns with high density of high ranked sudoku
But not sure the highest sudokus will not be found in a low density pattern
The problem is compute time
Then the best strategy seems to explore all patterns and make statistics over a period of time and search extensivelly only the richest patterns

I hope the hardest will be found with better strategies than computer power and simple programs, but who knows ?
You will find much more 99500 that 99400
This seems to be rating specific, also i had more.
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:I suppose with few clues (19-21)?

21 , when I use 20 clues this make the valid sudokus very rare and in fact this does not increase the ranking , but maybe this need to be explored more
I hope the hardest will be found with better strategies than computer power and simple programs, but who knows ?

Seems to me difficult to imagine we can avoid computer to explore millions of grids. The ranking seems unpredictable
The winning strategy will be the one that maximize the probability of finding high ranks, here lot of strategies can be used.
dml

Posts: 34
Joined: 12 November 2006

dml wrote:The winning strategy will be the one that maximize the probability of finding high ranks, here lot of strategies can be used.
Maybe there is more. The winning strategy for finding 17-clues for a long tiime was to search for them in "promising" grids. But G.F.Royle found more than 90% in about a year by constructing 18-clues directly and looking for 17-clues "in the near". This is still somewhat incredibly effective for me.
ravel

Posts: 998
Joined: 21 February 2006

Mauricio,

thanks for your pearl, i inserted it with 9 steps.
And i corrected an error in the list, where a puzzle by JPF was missing and another duplicated. Also 7 JPF puzzles (49-55) were not listed in the steps sections.
ravel

Posts: 998
Joined: 21 February 2006

ravel,
I’m always fascinated by the work you are doing for this thread.
Thanks.
ravel wrote:I hope the hardest will be found with better strategies than computer power and simple programs, but who knows ?

I agree with you on this general idea.
Too much computer power, not enough thought...
... as far as I’m concerned

Ocean wrote:How can we find new hard ones? Is it possible to "learn" how to solve hard puzzles?

It’s getting hard to surf on the thread with more than 33 pages...