The New Sudoku Players' Forum

[ravel]

Hi Tarek,

My theory of 21-clue puzzles not having the hardest puzzles was rubbish...

This is, what it looks like now. But the last word is not spoken. Not long time ago it seemed, that only puzzles with diagonal pattern could make it.

Did I forget ravel to mention how splendid your work with these hardest puzzles is

Thanks again.

could you elaborate on how your new method works .... (what new techniques are implemented, and when subnets are used)........

The program is in progress. So far i have no new techniques implemented, but one less (UR1) But i want to add xy-wing, UR1,2,4 and turbot fish (and i am rather curious, what they will bring). New are the subnets and the way, how i calculate solutions.
For this i keep a list of "nodes", that are the grids, where the implemented techniques are stuck, with rating so far (one point for each elimination chain needed, 3 extra points for elimination that needs subnets). For "the next" node (in the moment by order of lowest ratings) i calculate, which eliminations are possible by trying all wrong candidates. When a number leads to a contradiction and the elimination of the number in the original grid would lead to at least k (k is set to 2 now) more eliminations using the basic techniques, this grid is added to the nodes with rating + 1. Here i keep a list that holds the minimum number of "allowed" candidates for each rating number (this is now the second best number found so far). Only grids with less or equal candidates are added. Also i check for duplicates, because often eliminations lead to the same grid.
If no such elimination could be found, i am looking for subnets, the most time consuming part. This is done the same way (again keeping a list of nodes), but i give up, whenever no direct elimination with enough progress can be found, and i stop with the first subnet, that leads to a contradiction. The grids resulting from subnet eliminations then also are added to the nodes with the extra points, if good enough.
The process is continued, until no better solution can be found from the nodes (none is left with less equal than the minimum number of candidates for the rating level).
So this rating now should be the same for all equivalent puzzles also.

Much can be improved, mainly the speed (needs about the same time as calculating the ER now) and - as mentioned - more techniques.
But i will need holidays from Sudoku now to have enough time for "real life" again (my friend says, there are also other things of worth out there)

[StrmCkr]

i have a question/idea

has any one attempted to identify polymorphic grids as one and the same? ie.

if changing of paired numbers on grid doesnt becomes a seperate puzzle.
[19] interchanges with [68] respectfully or can flip and be reorderd as {91}

where
all 9's become 1's and all 1's become 9's.

or even more of an
abstract idea

identifed reduced grids as the same puzzle as any specific simplified grid that solves easily now this example puzzle just happens to have even more reduced in clues and diffrent locations choosen thus maximizing the difficulty in solving.

where number pairings can be swaped/flip, to have the unknown grid match any puzzle that is simple and easy to solve.

Code: Select all

.....7.9.
5...2.3..
...8....1
..9.....7
.6..4..5.
2.....6..
3....9...
.4..5.2..
..81.....


take the above puzzle looks familar doesn't it?

now grab any solved grid. fliping pairs and swaping pairs will generate the same above pattern in a solved grid in 9 steps or less. except all the missing variables will be identified and solved}
and tada you now have the unknown puzzle solved.

or you can

say
sample puzzle is identical to any specific grid of lowing difficulty by polymorphing numberations, and down grade its difficulty very easily. from ultra hard through fully solved.

wouldn't it then be possible to say every given puzzle is polymorphic and = to any x puzzle identically even though given postion(solved poistions may vary)

and then use solved knowns variables found in the simpler puzzle to fill in the missing ones in the harder puzzle? or simply morph any soltution till filled in cluesin unknown puzzle match exactly to given solution.

also it it easy to postulate that there is truly only 1 solution to all sudokus as ploymorphing numials generates all the same solution. they just interchanging postions.

so we can say that the above puzzle (ocean's new years presant polymorphed by my self)

is identicaly to this grid. of easy rating.

Code: Select all

 *-----------*
 |97.|3.4|.65|
 |.2.|5.6|.8.|
 |...|...|...|
 |---+---+---|
 |..5|8.2|9..|
 |..2|.4.|3..|
 |..8|7.5|1..|
 |---+---+---|
 |...|...|...|
 |.6.|2.8|.3.|
 |84.|1.9|.27|
 *-----------*


and has the same solution just polmorphed. (in a specific order)

971384265324516789586927413415832976792641358638795142257463891169278534843159627

[RW]

now grab any solved grid. fliping pairs and swaping pairs will generate the same above pattern in a solved grid in 9 steps or less.

I'm afraid not. There's 5,472,730,538 essentially different sudoku solutions that are not isomorphic in any way. Even if you had an isomorphic solution to the problem puzzle, 9 steps would not be enough as you can also rotate the grid or swap columns, rows (within chutes) or chutes.

so we can say that the above puzzle (ocean's new years presant polymorphed by my self)

is identicaly to this grid.

The solutions are identical, but you cannot say that the puzzles are identical.

RW

[Edit: just saw that you posted the exact same message in the "advanced solving techniques" section. Please, do not double post!]

[coloin]

Isomorphic puzzles are identical I think you will find.
Are you confusing puzzles[sub-grids] and completed grids ?
Each complete non isomorphic grid has a large number [at least 10^15] of different minimal puzzles.
You cant compare puzzles as the same just because they have the same grid solution !

Ah RW has already answered.........

So.....

I have tried to generate difficult puzzles with specific patterns - and have got nowhere near the "hardest" puzzles posted here. [best E.R 9.4]. Some puzzles are at a complete varience in rating terms [SE vvs Suexrat]


Can someone please comment on the patterns of these puzzles...

Does it really matter if the 6 different "orientations " of these patterns are different -
like

Code: Select all

xoo  xoo   oxo   oxo   oox   oox
oxo  oox   xoo   oox   oxo   xoo
oox  oxo   oox   xoo   xoo   oxo

I am tending to think that they are equivalent

Is there a trick to produce hard puzzles ? I produced more puzzles by finding mutable clues. My program searches over a fixed mask - i havnt been able to reduce the duplicate searches [sol>1]so is therefore very inefficient. Having said that the difference betwwen an easy puzzle and a very difficult one can be one mutable clue......

Or is it just down to generating as many valid puzzles with this sort of pattern as possible and getting lucky ?

How many valid puzzles [per grid] are there of Ocean's pattern [and presumed equivalent patterns] ?

Code: Select all

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

Are there 6^7*9^3 = 204073344 equivalents to this pattern then ?

Taking the analysis furthur........

The one clue in box clues can have 5,6 or 7 options
The three in box clues can have 3,4,5,6, or rarely 7 options.....

Ah...........maybe hard sudokus are different in this count........

C

[Mauricio]

Can someone please comment on the patterns of these puzzles...

Does it really matter if the 6 different "orientations " of these patterns are different -
like

Code: Select all

xoo  xoo   oxo   oxo   oox   oox
oxo  oox   xoo   oox   oxo   xoo
oox  oxo   oox   xoo   xoo   oxo

I am tending to think that they are equivalent

Any box in a given sudoku that has a a configuration of the above can be transformed to any other configuration of the above, the same box (edit: changing the rest of the puzzle, of course).

Having said that the difference betwwen an easy puzzle and a very difficult one can be one mutable clue......

According to personal experience, the probability that a sudoku is hard GIVEN that has a mutable clue is lower than the probability that a sudoku is hard, so looking for mutable clues is not the best option. I had the same idea of looking for mutables and I found about 8 times more sudokus with a given pattern (diagonal), but I found about two times the numbers of hard puzzles, not 8 times.

Or is it just down to generating as many valid puzzles with this sort of pattern as possible and getting lucky ?

That and increasing the probability of finding that kind of puzzles. 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?

Enough of talking, I want to enter the elite group of hard sudoku creators (dml, Ocean, tarek, anyone else I forget?), so here is my contribution:

Code: Select all

. . .|5 . .|. . 1
. 4 .|. 7 .|. 2 .
. . .|. . 8|3 . .
-----+-----+-----
1 . .|. . .|6 . .
. 2 .|. 5 .|. 9 .
. . 3|. . .|. . 8
-----+-----+-----
. . 6|3 . .|. . .
. 9 .|. 2 .|. 4 .
7 . .|. . 5|. . . gsfr 99962, gsfr-X 99982

My next goal is a sudoku not rated by gsfr, I hope luck will be on my side.

[merallas]

contribution of Mauricio:

Code: Select all

. . .|5 . .|. . 1
. 4 .|. 7 .|. 2 .
. . .|. . 8|3 . .
-----+-----+-----
1 . .|. . .|6 . .
. 2 .|. 5 .|. 9 .
. . 3|. . .|. . 8
-----+-----+-----
. . 6|3 . .|. . .
. 9 .|. 2 .|. 4 .
7 . .|. . 5|. . . gsfr 99962, gsfr-X 99982

My next goal is a sudoku not rated by gsfr, I hope luck will be on my side.[/quote]

Is this a very hard sudoku?

I can still solve it easily with my program

merallas

[r.e.s.]

Code: Select all

. . .|5 . .|. . 1
. 4 .|. 7 .|. 2 .
. . .|. . 8|3 . .
-----+-----+-----
1 . .|. . .|6 . .
. 2 .|. 5 .|. 9 .
. . 3|. . .|. . 8
-----+-----+-----
. . 6|3 . .|. . .
. 9 .|. 2 .|. 4 .
7 . .|. . 5|. . . gsfr 99962, gsfr-X 99982

BTW, it has ER = 10.6

[dml]

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?

To be clear I call "hard sudoku" a sudoku that gsfr rate above 99000

With a similar pattern as yours I found in 1 hour 4744 valid sudokus at 3.0Ghz
4734 have gsfr > 99000
55 >99500
6 >99900 : highest is 99955
This is in agreement with my previous comments on statistical density with gsfr
2074 are non isomorphic
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!!!

Now you construct lot of grids
then check they are valid grid "only 1 solution" (probably 1 every 1000 is valid)
then rate it with gsfr

If you have chance and have lot of CPUs or are patient you can compute millions of grids and break the current record

I am confident this is optimal strategy to get lot of hard grids but I suspect the hardest sudokus should have less clues, but now the problem to find 1 is probably many orders of magnitude harder

For now I try to explore 18-sudokus with 2 clues per box organized in a way that I have only 2 clues per horizontal row and vertical row with same property that none of the 6 clues in 3 horizontal or vertical boxes are identical. I have the feeling this is where we will find the hardest but very rare ultra hard sudokus

[ravel]

Thanks dml,

very interesting analysis. I am looking forward to your new toughies.
Personally i dont believe that the hardest could have less than 21 clues. The 17 and 18 clues found so far are not hard enough, so i think is impossible to have a puzzle with few clues, that is both unique and hard. But i like to get surprised.

Mauricio,

your puzzle has 20 points from my current program, so would be number 23 for this rating (thanks r.e.s. for the ER).

[coloin]

Thankyou Mauricio and dml for that update

I am just wondering how many [easy and hard ] sudokus of the 21 clue pattern there are per grid - it cant be many....is it < than 1 ?

Code: Select all

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

I only got four 22-sudokus with this equivalent pattern out of a projected 324 million random grids.
I think there are 36/3 more equivalent ways in a grid than the 21 clue option [204073344]
That works out ataround 29 of this 22-sudoku pattern per individual grid ! [ Error anticipated ]

I dont think going to 18 will be very fruitful however.

As luck would have it the ony exaustive search ever done with one pattern Nick70 only found 851 [in total] 19-sudokus with this pattern - it took a least a month !

Code: Select all

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

Only 8 were non minimal - and I dont think that the clue was r5c5 -I would be surprised then if you found one !

C

[Mauricio]

6 sudokus not rated by gsfr

Code: Select all

100060800006002004040300000007500002400000030080000700200003900000070010060800005 ER: 10.6
100400008000070040009008700600100070030050800002009003003020900060300000200007005 ER: 10.6
100040030000007004005800700002500080600090002030000400003006000700200000060080001 ER: Not tested
100040060090000003000700200003900600600010007000005080008400500400002006070030040 ER: Not tested
100007020090400008000030400060100004007000200300005060006080900800004000020600005 ER 10.6
100300007000006080005020300700900200008050000040001008007800900020000004300002060 ER: Not tested

I did not test them because there exists a new technique that renders them defenseless. What do these sudokus have
in common? Visit Gurth puzzles thread to see the new technique.

[ravel]

Oh, i wanted to go to sleep more than an hour ago, just a glimpse into the forum ...

But that looked too weird - new ultras not rated by gsf with extremely high ER, accompanied by a solution technique, that would make them more or less easy ?

What are my ratings then ? Not that sensational: 17, 17, 15, 14, 13, 18
So in the moment i dont see the urgent necessity to implement the generalized symmetry technique.

But i am very surprised, thank you

Finally i also got the rest of the ER's (this time my program was much faster). Here they all are: 10.6, 10.6, 10.8, 10.7, 10.6 and 10.6.

[dml]

I did not test them because there exists a new technique that renders them defenseless. .

Why you dont give also the high ranks that gsfr can rates?
I suppose you have many sudokus why gsfr >99990
I dont understand why all my sudokus are all ranked by gsfr, apparently I do something specific that avoid this situation, but it seems now that we all use the same technics
Could you give me the exact options you are using with gsfr to recognize that it does not find a solution ?

[ravel]

You can find options here. Be sure to have the right version (sudoku -V should give 2006-12-04). This is the output for the first of Mauricio's puzzles:

Code: Select all

    0  0  0 1...6.8....6..2..4.4.3.......75....24......3..8....7..2....39......7..1..6.8....5

[dml]

You can find options here. Be sure to have the right version (sudoku -V should give 2006-12-04). This is the output for the first of Mauricio's puzzles:

Code: Select all

    0  0  0 1...6.8....6..2..4.4.3.......75....24......3..8....7..2....39......7..1..6.8....5

I have 2006-12-15
And I reproduce the "0 0 0 " with your example but the 6 puzzles of Mauricio have a value in column 1 , they have 0 in columns 2 and 3
Is it what is searched because I have thousands of that !!!!

check if those 3 are what is searched , at least the first one should have ER >=11.1
003000009400000020080600100200004000090800007005030000000900800000005030070010006 ER=11.2 003000600400009020080000005200500008000030700000001040001070090500004000060800000 ER=10.6
003400080000009200000060001007010000060002000500800040010000900800000030004500007 ER=10.8

In fact I was only looking at highest scores with gsfr then missing some interesting sudokus , I need to parse my logs