The New Sudoku Players' Forum

[Morgoth]

I'm using two methods to generate puzzles - actually this is one method, but in the second case I have added a brute force method. I needed to find whether the brute force helps at all, so I just removed it and generated 500000 puzzles this weekend.

To generate a sudoku without brute force usually takes about 120 miliseconds - I want to keep this way, as it looks fast enough, but I'm not sure whether it can generate puzzles with difficulty 10+.

The result from the weekend is:
SE 9.2
000010060000300000043000700000000000289004050006927000400200500802000690030080000

SE 9.1
060010000005003470000007062400002910500061003007000000000800050000030800890000000
080000090000000400000060071000200019006009004009007053005400000970001000400302000
000040700800600000000000052000000506002700004010065090000004000073010200000070039
020190000010000000500720000000008061004050000060000402003570008006000700000000094

So, is this normal? Should I generate several milions to find one 10+?
I don't use any patterns and symetry - everything is random.

[m_b_metcalf]

I don't use any patterns and symetry - everything is random.

As you will see in the hardest sudokus thread, there is a lot of empirical evidence for the most difficult puzzles having a large fraction of their clues aligned on diagonals.

Regards,

Mike Metcalf

[ronk]

there is a lot of empirical evidence for the most difficult puzzles having a large fraction of their clues aligned on diagonals.

There is also empirical evidence that any permuted puzzle has approximately the same difficulty as the original -- suggesting the clues need not be on the diagonals. So I think it's just the preferred form.

[ravel]

So, is this normal? Should I generate several milions to find one 10+?
I don't use any patterns and symetry - everything is random.

I made a similar test last year, when i created a million random sudokus. The hardest i found there had ER 9.1. It is very unprobable, that you will find a 10+ puzzle in some (maybe 100's of) millions of randomly generated sudokus.

The hardest puzzles dml and Ocean found (see here) all follow tso's rule of thumb, i.e. (in my words) no box contains more than one given in each minirow and minicolumn (with an arbitrarily chosen pattern following this rule i found two 9.9 puzzles out of 300000). Additionally they have 21 givens and at most one number is repeated in the bands or stacks (3 boxes in a line).

On the other hand Mauricio and Mike Metcalf found extremely hard puzzles, that are highly symmetrical. This symmetry can be diagonal or rotational (with full symmetry each number then always has the same "partner" number in the mirrored cell). You can find them here.

You might always try a rule like this: no empty cell should "see" more than 6 givens.

[Morgoth]

Mike, empirically you can prove only that something exists, but not that something doesn't
It is completely possible that some day, somebody with enough computer power will generate several billions random puzzles and one of them will break all records.

ravel, 10x a lot - that was I need. I had some doubts whether my algorithm is not technically restricted, as it doesn't use brute force.
I don't like the idea for symmetry, but the rule "no empty cell should "see" more than 6 givens" looks interesting - I may try it.

Besides, I really think about the idea to generate 100 millions - we have several multi-CPU test systems, which are usually free during the weekends.

[wapati]

Besides, I really think about the idea to generate 100 millions - we have several multi-CPU test systems, which are usually free during the weekends.

You might take a puzzle that has a high rating and put the "shape" into a generator and run it a while. It may not produce many puzzles per hour but they might be hard ones?

[m_b_metcalf]

Mike, empirically you can prove only that something exists, but not that something doesn't
It is completely possible that some day, somebody with enough computer power will generate several billions random puzzles and one of them will break all records.

Right, but in the absence of formal proofs we have only empiricism to help us. As ronk pointed out, an isomorph of a diagonal puzzle will have a similar difficulty rating -- it's just easier to program a diagonal pattern than a non-diagonal pattern that can be morphed into one. They look nicer too.

I use a similar rule to tso's too, quite successfully (I have only a little PC so billions of tries are out of the question for me ).

Regards,

Mike Metcalf

[Morgoth]

I tried the diagonal pattern for the weekend. I generate approximately 1 milion puzzles and there are 12 with 9.2 and more then 100 with 9.1
Nothing more! I think I should change the generation method.

[RW]

I believe the most effective way to generate hard puzzles has been using the diagonal pattern minus some clues, so that no given value may exist twice in the same band/stack.

Don't get discouraged just because you can't find any ER 10+ puzzles immediately. The diagonal property was explained in the hardest thread in late May 2006, the first ER 10.0 puzzle was found by Ocean 2½ months later. Several million diagonals must have been generated before that. When ArtoI found his "Escargot" (the first puzzle to beat SE 1.1), he created over a billion puzzles, most likely all diagonal. The supertough puzzles are very rare, to find them you need a very fast generator and a good pattern.

RW

[Morgoth]

Hi RW,

The problem is that I’m trying to prove my algorithm empirically even I’m not sure it works.

What I’m doing is:
1. Generate 16 hits (this is optimistic, especially I haven’t generated puzzle with less then 19 hints, it can be a little bit faster if I generate 20 or 24)
2. Check whether my solver can solve the puzzle, if not - add one more hint and try again – there are 3 ways to stop
– puzzle already has 0 decisions, then restart
– puzzle has one decision, then continue
– there are no more free cells in the used pattern, then restart
As this is not looking for minimal puzzle the used methods in the solver should be only fastest – in fact I use the most of them as I have proved that removing one of them the generator is going slower.
3. Try to remove a hint (I’m using random order, otherwise the first row is usually empty) and substitute it with all other possible candidates for the cell. If there is at least one of the new puzzles which can be solved, so the hint can not be removed.

The last step is doubtful – I can not prove it is wrong, I just have bad feeling about it. It surely works (otherwise it sometimes would produce impossible puzzles), but I’m not sure whether it can produce 10+ or even 9.2+.

Best regards,
Morgoth

p.s. is 120 miliseconds per puzzle fast enough? it is faster with diagonal pattern as the wrong puzzles are more, but in fact this makes it slower - 2 puzzles per second ... and SE analyse, which is a lot slower.

[coloin]

Hi Morgoth
I believe I can help you - and you can help me !

I like you struggled to generate many SE 9.1 + puzzles.......

Until I hit on a way to generate them which by passed the normal methods that I used to employ.

Heres an example - Ive not posted on the hardest sudoku thread - as its I think only a SE 11.1 !

It is the one with the highest suexrat9 value that Ive seen

Code: Select all

rating:   1728 ,  1.......6.2.5...4...3...7...4.8.2.......6........45.8.7.....3...5...9.2...6.....1
rating:   1805 ,  1.......6.2.5...4...3...7...4.8.2.......6........45.8.7.....3...5...9.2...6.....1
rating:   1859 ,  1.......6.2.5...4...3...7...4.8.2.......6........45.8.7.....3...5...9.2...6.....1
rating:   1732 ,  1.......6.2.5...4...3...7...4.8.2.......6........45.8.7.....3...5...9.2...6.....1   coffee1

perhas your computor power can search the limits of my method - as I keep finding them !!!!!

Regards

[Morgoth]

Hi coloin,

I'm intereseted not to generate many SE9.1+, but to prove that my generator can do it.

The computer power is one xeon 4CPU and 3 xeons 2CPU - it is not so much and I can waste it only during weekends, when nobody uses it for work. I think you need something more then 2-3 weekends to break the current record.

I saw you also use the diagonal pattern. How regular you have SE10+? Is it at least one per 10 milions?

[coloin]

I think you have to direct your search a bit

Take this made up 18 clue subgrid

Code: Select all

+---+---+---+
|1..|.9.|..6|
|.2.|5..|.4.|
|..3|...|7..|
+---+---+---+
|.4.|...|...|
|9..|...|...|
|...|...|.8.|
+---+---+---+
|..7|...|3..|
|.5.|..8|.2.|
|6..|...|..1|
+---+---+---+ It has 7518 solutions

By filling the central box with 3 clues three non-isomorphic sudokus can be found amongst [many] others.

Code: Select all

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

Rating with suexrat9 and SE

Code: Select all

rating:    375 ,  1...9...6.2.5...4...3...7...4.3.....9...1.........4.8...7...3...5...8.2.6.......1  SE 9.4
rating:    376 ,  1...9...6.2.5...4...3...7...4.7.....9...6.........4.8...7...3...5...8.2.6.......1  SE 9.4
rating:    325 ,  1...9...6.2.5...4...3...7...4.2.....9...3.........4.8...7...3...5...8.2.6.......1  SE 9.4 

As has been said the diagonal pattern is the same as a "morphed" one

Code: Select all

x..       x..
.x.   =   ..x 
..x       .x.

2 clues and 1 clues in a box is also desirable.

The symmetry feature tends to give hard puzzles.

Also filling in the central box with 4 clues or 5 clues can paradoxically give harder puzzles ! I think because more puzzles are generated and you have more puzzles to rate.!

I hope this helps

C

[wapati]

Also filling in the central box with 4 clues or 5 clues can paradoxically give harder puzzles ! I think because more puzzles are generated and you have more puzzles to rate.!

I hope this helps

C

I think it does! I had been leaving the center for last, creating by "hand".

I'll try the opposite, thanks.

[ravel]

Code: Select all

1.......6.2.5...4...3...7...4.8.2.......6........45.8.7.....3...5...9.2...6.....1

Congrats for that puzzle, Coloin.
Though my own program only rates it with 13 points (using a step with 5 subnets), ER 11.1 is impressing AND
gsf, can you confirm, that this is the first known puzzle that has only one singles backdoor pair [36]8[87]8 (knocking on the backdoor conjecture) ?