The New Sudoku Players' Forum

[Carcul]

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.

Keep your good work Dml.

Carcul

[gsf]

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

[ravel]

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).

[gsf]

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 latest version is 2006-12-04
the -V option lists the version
could there be a browser cache that far out of date?
or maybe a subsequent download went to a permuted file name?

[dml]

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

[ravel]

the latest version is 2006-12-04

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.

[gsf]

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

you can use that to post one line answers on the twin thread from your "friend"

[ravel]

...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/99700
1.....9......4..6..5.8....2.8.7....96...3..1......92...4.........2..57..3...6...8
16/9.9/99760/99790
2....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).

[Mauricio]

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.

[dml]

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?

[ravel]

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.

[dml]

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.

[ravel]

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]

Mauricio,

thanks for your pearl, i inserted it with 9 steps.
[Added:] I also added the ER 10.0 puzzle from the Gurths puzzles thread (8 steps only!).
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.

[JPF]

ravel,
I’m always fascinated by the work you are doing for this thread.
Thanks.

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

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

Size of the thread :
It’s getting hard to surf on the thread with more than 33 pages...
What about starting a new thread (The hardest.. II) ?

JPF