The New Sudoku Players' Forum

[m_b_metcalf]

I can now generate about 1500 puzzles/hour/2.8Ghz with the pattern of dml/Ocean hard puzzles, ie, 3 diagonal boxes with one clue each and the other boxes with 3 clues each, 21 clues total. A week ago I would be happy if a generated one of those in 1 day or work. Ocean, dml, is that number (1500 puzzles/hour/2.8Ghz) close to yours? Or you have some kind of secret not revealed? Or are you are just smarter than I?

With a similar pattern as yours I found in 1 hour 4744 valid sudokus at 3.0Ghz
[snip]
Then this seems similar to what you can achieve

The best way to generate lot of hard grids is:
use a total 21 clues, if you try 20 clues you will see it is much harder to find some valid grids and the grids have similar density properties and ranking than 21-sudokus
use 1 or 3 clues per box , 7 clues per horizontal or vertical 3-boxes
If 1-clue the central square in a box offers generally the highest density, but some others positions give also some high density
If 3-clues, they should be put in different columns and rows inside a box, it does not seems the diagonal is optimal
The most important factor is that all 7 clues in the 3 horizontal or vertical boxes should be all different, this is that single property that create the extremely high density of very hard sudokus, for some specific patterns you can reach quasi 100% of hard grids!!!

Just for fun I programmed a similar pattern: 7 different clues per chute, 1 to 3 clues per box, with a bias to the diagonal. I produce 2100 of these per hour at 1.6GHz. Also comparable. Lots of hard ones but no gold nugget .

Regards,

Mike Metcalf

[dml]

Just for fun I programmed a similar pattern: 7 different clues per chute, 1 to 3 clues per box, with a bias to the diagonal. I produce 2100 of these per hour at 1.6GHz. Also comparable. Lots of hard ones but no gold nugget .
Mike Metcalf

The key for performance is the algorithm that test if your sudoku is valid with a single solution.
Should be less than 1ms to perform well.
You will have to test thousands of sudokus to find 1 valid.
After you rank with a fast ranking method : here gsfr is key component of the strategy (consume 10% of total)
I suppose you use this strategy
Patrick

[m_b_metcalf]

Should be less than 1ms to perform well.
You will have to test thousands of sudokus to find 1 valid.

No problem for 21 clues (millions per hour), but for 18 clues I'm up at 45ms per try, much too long to get anything but a lucky hit (like winning the Lotto ).

Regards,

Mike Metcalf

P.S. Not having gsfr installed I use my own crude filter to extract the promising ones.

[dml]

No problem for 21 clues (millions per hour), but for 18 clues I'm up at 45ms per try, much too long to get anything but a lucky hit (like winning the Lotto ).
P.S. Not having gsfr installed I use my own crude filter to extract the promising ones.

For me this is the inverse
I have never found 1 sudoku with 18 clues but thousands with 21 !!!!
When I build the sudokus I enforce the constraint that all the clues in a row or column are different
This is probably why I cannot find a 18-clue with such hard constraint
The advantage of this constraint is that almost all sudokus you find are hard and some of them very hard , then no need to filter the promising ones and 10% for final ranking is very cheap.
If I had to write my own code to filter or rank, what I have started I doubt I can do better than gsfr, in particular because I dont know to resolve the sudokus then I will have to study all manual strategies and code them, today I have only implement the simple ones.

There are many others tricks and strategies to increase the probability to find many hard sudokus, I have not finished this analysis yet but I have some good ideas, then I think that if I can find many ultra hard, some of them will be even much harder than the current ones
I have no idea where this will finish
I think it is more promising to study the patterns and constraints that permit to win the Lotto each time you play

[m_b_metcalf]

No problem for 21 clues (millions per hour), but for 18 clues I'm up at 45ms per try, much too long to get anything but a lucky hit (like winning the Lotto ).
P.S. Not having gsfr installed I use my own crude filter to extract the promising ones.

For me this is the inverse
I have never found 1 sudoku with 18 clues but thousands with 21 !!!!

Maybe I expressed myself poorly, but that is just the situation I'm in too: thousands of 21-clues and no 18s (I do have 3 19-clues though ).

Regards,

Mike Metcalf

[Ocean]

Very nice progress by dml and Mauricio lately!

First, thanks to StrmCkr, ravel, RW, tarek, gurth and coloin, for compliments, congratulations and comments after publication of the "New Year's present for RW".

ravel: Good job with the new rating software! Could you say if your new stepcounts are absolute minimums (based on complete search), or minimums from a limited/arbitrary search (where the absolute minimum might or might not have been found)?

A week ago I would be happy if a generated one of those in 1 day or work. Ocean, dml, is that number (1500 puzzles/hour/2.8Ghz) close to yours?

I do not have exact measures, but guess my numbers are about the same order of magnitude as yours and dml's. Your new ultra hard symmetric non-minimal puzzles with many clues are amazing. Have not yet figured out how you were able to find these. Very impressive! - The same can also be said about dml's new hardest.

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"

Thanks for the update! Hope this did not interfere too much with other plans for christmas...

[gsf]

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"

Thanks for the update! Hope this did not interfere too much with other plans for christmas...

no, just plans for understanding what's going on

[ravel]

Could you say if your new stepcounts are absolute minimums (based on complete search), or minimums from a limited/arbitrary search (where the absolute minimum might or might not have been found)?

It is just a greedy search and the results vary with the parameters i take (when to look for subnets).
In the meantime i have added xy-wing.
When i search for subnets, if no eliminations can be found, that would bring a progress of at least one more elimination, i now get 22 points for dmls 3/07 (which still cannot be solved with a minimum progress of 2 additional eliminations) and 27 for Ocean's New Year present. The calculation time is about 5:1 (!).
So i still dont know, how to get a really good rating with this method.

[Mauricio]

Your new ultra hard symmetric non-minimal puzzles with many clues are amazing. Have not yet figured out how you were able to find these. Very impressive!

When I saw a technique (symmetry technique) of gurth, I decided to create some symmetric sudokus to apply the technique, many hard sudokus hide behind those patterns.

[dml]

Some news sudokus
One observation : when we have a specific pattern, we find extremely rapidly a long list of hard sudokus.
When we remove the canonical forms we get only a short list.
But if we extend for a very long period the research, we will ONLY find new canonical forms and no new solution.
I suppose this is logic, if so this means there is a potential strategy to find very rapidly all hard sudokus,
but this require to explore only the NON canonical forms that are extremely rare vs the others.
But it is probably extermelly hard to build an algorithm that construct only non canonical forms

000007080006100200000030004090040000300008070001600000002000090800005300040000006
003400000050009200700060000200000700090000010008005004000300008010002900000070060
020000600400000007009030010000005004060010020000800300005700000010020900800004000
100050009006000200080000040007600000500010300040008000300900005000020100000007060
000050700400009020000100006010600000008020000900003050070000800500040030002000001
000400080000009200700060005001030000090002000600800040030000006800500070002000100
003000009400000070080006500005001800060200000900070000000090040000800003010005200
003000600400009070080000001200070040000600800000003005060010000007500000900004020
003007000400100200080060000200000900060008050007000003000030004000005060900200100
003050000400009000080600010060001090000070500000300002002000700010000003900004060
003400000050009000700020006200070010000300008000005400001060007090000300800000020
003400000050009000700020010040300900000070020000005006002000008600000070090001500
020007000400080000009600050000500090300040700000002001500300040070000006001000800
020400000006009100700030000000070008000001050090600400040200600500000030008000007
020400009000080070000006500007000060300000800090001002004070000600005300010200000
100000009006000070080300400200010060000004005000700800030800000007060010900005000
100006000050080000009200040004500060030000900800000007000070001000004800002300050
100006000050700000009020040000008600040030020000500001300000800002000090070001005
100050009006000200080000040007006000500010300040800000300090007000200500000004010
100050080000009003000200400004000900030000007800600050002800060500010000070004000

[coloin]

I assume that when you say "canonical forms" you mean isomorphic forms
The fact that you are getting duplicates has implications for the number of puzzles of that particular pattern.

I calculated for this the most successful pattern

Code: Select all

+---+---+---+
|...|..1|5..|
|.3.|.4.|.2.|
|...|6..|..7|
+---+---+---+
|..2|...|..1|
|.4.|.9.|.3.|
|7..|...|8..|
+---+---+---+
|5..|..2|...|
|.9.|.3.|.4.|
|..6|8..|...|
+---+---+---+ note all different clues in all bands but SE only 8.4

that there were 6^7*9^3 ways to permute the boxes

Despite this I suspect that not many grids have one of these puzzles.

There are ways that one can reduce the occurance of isomorphic puzzles- but it depends if it fits in with your puzzle generation method.

On the topic of 18,19 and 20 clue patterns

Nick70 scaned the whole ether for grids of this [exact] pattern with 19 clues and found 851 puzzles, 8 of which could be reduced to 18 clues, but this did not include the central r5c5 clue

Code: Select all

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

Have we got hard sudokus for all the possible potential patterns with 21 clues and under.....

Code: Select all

21
a133    b322   c333   d333   e233   f132
 313     232    303    331    303    323
 331     223    033    302    331    232    and others

20
a133   b033
 303    322
 331    322

19
a222   b123
 232    321
 222    232

But with the 22 clue pattern there will be substancially more puzzles to generate ?

Code: Select all

133
323
331 [and others]

C

[ravel]

Thanks for the puzzles, dml,

my current ratings (and ER) are

Code: Select all

15 10.6 dml 4/07
20 10.7 dml 5/07
14 10.5 dml 6/07
23 10.7 dml 7/07
19 10.6 dml 8/07
19 10.4 dml 9/07
14 10.3 dml 10/07
17 10.5 dml 11/07
16 10.6 dml 12/07
20 10.7 dml 13/07
19 10.6 dml 14/07
16 10.5 dml 15/07
19 10.6 dml 16/07
20 10.6 dml 17/07
22 10.7 dml 18/07
15 10.5 dml 19/07
19 10.7 dml 20/07
22 10.6 dml 21/07
15 10.5 dml 22/07
23* 10.7 dml 23/07


So the last one (like dml 3/07) could not be solved, when subnets are only calculated for numbers with a minimum progress of 3 eliminations.

[ravel]

With adding xy-wing as proposition technique 22 puzzles fell out of the 20+ points list, so these 25 are remaining now. All have a gsf rating > 99900 except dml9 with 99839. The asterisk means, that a somewhat harder step was needed.
[Edit: i noticed, that dml 23/07 was identical to dml20]
[Edit2: and dml 17/07 is equivalent to dml4, 13/07 to dml15, 18/07 to dml12 - so only 21 puzzles are left here. ]
27 11.2 000001020300040500000600007002000001080090030400000800500002000090030400006700000 Ocean's New Year's present for RW
27 11.1 003000009400000020080600100200004000090800007005030000000900800000005030070010006 dml 1/07
23 10.7 100050080000009003000200400004000900030000007800600050002800060500010000070004000 dml20
23 10.7 100050009006000200080000040007600000500010300040008000300900005000020100000007060 dml 7/07
22* 10.8 003400080000009200000060001007010000060002000500800040010000900800000030004500007 dml 3/07
22 10.7 100050000006009000080200004040030008007000060900000100030800002000004050000010700 dml11
22 10.7 003900000040070001600002000800000002070050030009000400200001008000040050000600900 dml12
22 10.7 000001020300040500000600007002000006050030080400000900900002000080050400001700000 Ocean's Christmas present for gsf
22 10.6 100300000020090400005007000800000100040000020007060003000400800000020090006005007 dml161
22 10.6 100006000050700000009020040000008600040030020000500001300000800002000090070001005 dml 21/07
22 10.5 100007000020080000004300500005400001080000020900000300000005007000020060003100900 dml48
21 10.5 100007000040050020006800000005090003020000040700000100000003005090040060000100800 dml9
21 10.4 900004000050080070001200000002600009030000040700000500000009002080050030000700600 dml8
21 10.4 100007000020030500004900000008006001090000020700000300000001008030050060000400700 dml45
20 10.7 003400000050009200700060000200000700090000010008005004000300008010002900000070060 dml 5/07
20 10.7 003200000040090000600008010200000003010006040007000500000001002090040060000500700 dml15
20 10.7 000001020300040500000600001001000007050030040800000900400002000090050800006700000 Ocean's New Year's present for ravel #1
20 10.6 800003000070060090004500000002000004030001070500000800000009001060070030000200500 dml4
20 10.6 020400000006080100700003000000060300000200005090007040300000800001000090040500002 dml50
20 10.6 002600000030080000500009100006000002080000030700001400000004005010020080000700900 dml16
20 10.6 001002000030040050600700800008000007010000040900000500004001008020030010000600900 Ocean #6/gold list

[Mauricio]

For those interested about suexr, I have two sudokus with suexr>=1600, one of those has almost 1700:

Code: Select all

. . .|. . 7|. 2 .
. . .|8 . .|3 . .
. . 5|. 6 .|. . 7
-----+-----+-----
. 2 .|1 . .|. . .
. . 4|. 5 .|. 7 .
3 . .|. . 9|. . 4
-----+-----+-----
. 7 .|. . .|1 . .
8 . .|. 3 .|. 5 .
. . 3|. . 6|. . 9 suexr ~1600, gsfr 99950

Code: Select all

9 . .|5 . .|. . .
. . 3|. 9 .|. 2 .
. 5 .|. . 7|. . 4
-----+-----+-----
. 9 .|2 . .|. . 3
. . 6|. . .|4 . .
7 . .|. . 8|. 1 .
-----+-----+-----
6 . .|3 . .|. 5 .
. . .|. 1 .|7 . .
. . .|. . 5|. . 1 suexr ~1690, gsfr 99536, ER 9.9

Just random sudokus:
Almost 180 degree rotational symmetry

Code: Select all

. . 5|. 8 .|. 6 .
2 . .|. . .|. . 1
. 3 .|. . 9|4 . .
-----+-----+-----
. 5 .|3 . .|1 . .
. . .|. . .|. . 6
. . 9|. . 7|. 5 .
-----+-----+-----
. . 6|1 . .|. 7 .
. . .|. . 5|. . 8
. 4 .|. 2 .|. . . gsf 99975, ER 10.6

Code: Select all

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

Code: Select all

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

180 degrees symmetry

Code: Select all

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

[ravel]

Nice puzzles again, thanks. Here are the ratings:
11,14,11,12,11,13