How regular is to generate sudoku with difficulty 9+ SE?

Everything about Sudoku that doesn't fit in one of the other sections

Postby gsf » Thu Mar 29, 2007 8:12 am

ravel wrote:
coloin wrote:
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) ?

the lowest in my old files had ~10 singles backdoor pairs
the recent hardest have a few with 2 singles backdoors pairs
so this looks like the first one with only one singles backdoor pair
its a nice find
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Thu Mar 29, 2007 9:54 am

Thanks
All I am doing is making up a 16 clue subgrid like this one.
Typically the ones that I looked at have around 100000 - 400000 sols - a slight alteration increases this to 3 million !
Code: Select all
+---+---+---+
|1..|...|..9|
|.2.|.4.|.7.|
|..3|...|5..|
+---+---+---+
|...|...|...|
|.4.|...|.8.|
|...|...|...|
+---+---+---+
|..5|...|3..|
|.6.|.8.|.2.|
|9..|...|..1|
+---+---+---+ 629008 sol

by completing the central box - [amongst many others] there were found 32 isomorphic puzzles like this [SE a disappointing 10.5]
Code: Select all
rating:   1708 ,  1.......9.2..4..7...3...5.....872....4...6.8.....5......5...3...6..8..2.9.......1


I am relying on suexrat9 - given that mbm 11.4 is around 1300 - this only contributes to my haphazard search !

I think I see the rating dilemma here - these puzzles have a high value because it takes a "long" time to randomly forward track a solution which I believe is what suexrat9 does.

Sorting out the bivalue cells would be an improvement - but I dont see any in the above puzzle !

C
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby RW » Thu Mar 29, 2007 4:06 pm

Coloin, congrats on your new puzzle! Your techique is a lot better than any other I've seen so far. Just played around with your technique for about 30 minutes, manually, inserting the numbers by hand. Got lots of 9,2 puzzles and this 9,6:
Code: Select all
6....7..1.3.....9...2...4..8..6.........4..5....1.9..8..4...2...9.....3.1..7....6

Seems I'm a lot more effective than Morgoth's massive computer setup!:D

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Papy » Sun Apr 01, 2007 12:37 pm

Hi coloin

I think that using the actual disposition you will not found 16 clues grids
Why? Because if you study the Gordon file no 17 clues solution have 3 empty coluimns,rows, or boxes
So I think that four are not possible
But is nor prove!

M théory was false
You cannnot do a band with 17 clues or 16 but you cabn do a rids with 17 so thhe demonstration of the 16 cluyes onb a band is not correct

But if you want strange grids I can summit you this production:
Look welle. Very strnge.

Code: Select all
120406000000000060900000000035600000000000308000000000701000800050780000000000000
120406000000000060900000000035600000000000607000000000306000100040280000000000000
120406000000000060900000000035600000000000607000000000308000900040790000000000000
120406000000000060900000000035600000000000806000000000309000600040960000000000000
120406000000000060900000000036100000000000206000000000502000800040580000000000000
120406000000000060900000000036100000000000306000000000801000600040580000000000000
120406000000000060900000000036100000000000308000000000302000800070320000000000000
120406000000000060900000000036100000000000308000000000601000800050860000000000000
120406000000000060900000000036100000000000608000000000601000800090810000000000000
120406000000000060900000000036500000000000608000000000502000900010980000000000000

The grids are canonized and all have 123456789 for the first row.
But is't not the particularity...
Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Postby RW » Sun Apr 01, 2007 9:37 pm

Papy, I'm not sure if you've understood the purpose of coloin's post... it's not about finding 16 clue grids.

I did some more tries with the technique, started with this partial grid:
Code: Select all
1.......6
.2..7..5.
..3...4..
.........
.8.....7.
.........
..4...3..
.5..8..2.
6.......1

I made about 50 puzzles by adding clues only to the middle box. Only five of these had ER <9.0, the rest were 9.0-9.5. Haven't found any puzzle with ER <8.4, not even by filling in all of the middle box. I'm sure someone with enough computer power could find a lot harder puzzles this way.

Another potential approach I thought of - Create lots of valid puzzles like this:
Code: Select all
1.......6
.2..7..5.
..3...4..
...XXX...
.8.XXX.7.
...XXX...
..4...3..
.5..8..2.
6.......1

The 16 clue pattern + all of box 5 filled. Find the ones with the highest difficulty rating, then find all minimal puzzles in these grids. I found several 9.2 grids with all of the middle box filled, this means that all minimal puzzles in there will have at least ER 9.2, some will be harder. Just can't remember right now what program I should use to get all minimal puzzles out of these.

Also noticed that a lot of these puzzles have similar size 48 or 50 unavoidables. This is mostly just an interesting fact, doesn't break any records but it's funny to see these popping up so frequently.
Code: Select all
1.......6.2..7..5...3...4.......4....8..62.7....5.......4...3...5..8..2.6.......1

Two solutions that differ in 50 cells. I believe the two solutions are isomorphs.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ravel » Mon Apr 02, 2007 7:48 am

RW wrote:Just can't remember right now what program I should use to get all minimal puzzles out of these.
You can use gsf's program wih the -m option.

My weekend's test:

Since i suspected that others will implement Coloins nice method, i followed dml's rule to generate hard puzzles: Different givens in all bands and stacks (and tso's rule of thumb, that each minirow/column has at most one given). I searched this (arbitrarily chosen) pattern for all such puzzles with a given in the X-cells plus one or 2 in the +-cells:
Code: Select all
X . . | . X . | . X .
. X . | . . X | X . .
. . X | + . . | . . +
----------------------
. . + | . . . | X . .
X . . | . X . | . X .
. X . | . . . | . . X
----------------------
. X . | X . . | . X .
X . . | . X . | X . .
. . + | . . X | . . +
Using dukusos 40 lines C code solver from suexg (for the public progams i used see here) the program was written in less than 2 hours. I ran it on an old 1.8 Gh computer.

I tested about 275 mio puzzles, 37 mio had no solution, 2.1 mio were unique, 0.95 mio without isophorphs. The generation took about 30 hours.
I canonicalized them with gsf's program, sorted them, eliminated isomorphs (unix comands sort and uniq) and calculated the gsf rating (in the linux version i cant use -qquick ?), this took 9 hours. For the hardest then i waited for the ER over night.
69% of the puzzles had gsfr > 99000, 59 (0.006%) sudokus have gsfr > 99500, and at least 30 an ER of 10.0 or higher. The 3rd column holds my current rating (the higher the harder).

Code: Select all
10.6 99760 10 .2...6..94......3...8...5....9.4..6..3...2..87.....1...6.9...7.....1......5..8..2
10.6 99727 10 ..34..7...5...9..6....2......4....1..9.6..3..8.......5.....8.9...1.3...2.7.5..4..
10.6 99721 10 ..34...8..5...9...6...7...12.........7..1..6...48....3....3.9....16...2......5..4
10.5 99834 10 1..........67...2..8..3.5....7.6..3....5....8.....49..3..8..6....2.9..7..4......1
10.5 99821 16 .2...6.8.4.......3..9...5.....7.....8....5.4..3..2.1......4...75..8..9...6...3.2.
10.5 99770 10 1....6..9..7.8..3....2..4.....5...7.3....1..2....9.6...6...3.5...4......9...2...1
10.5 99750 10 ..34......5..8.1..7....2.6..9..7..5.......2..6.......8.1..6..9.8..3..4....2..7...
10.5 99689 10 1....6.8..5.7....2....3.....9....4....7....1.8....5..6..2...9..6....1..7.3..4..5.
10.5 99540 12 ..3..6..94...8.2.....7...5.2...3.8....6.......9......15..2....7.....1.3...8.4.6..
10.4 99832 10 ..34..7...5..8...6.....2.1.2..7....4..8.9.3...6.....5......1..8....3......45..9..
10.4 99783 13 ..3......4.......2.8...1.6....8..9....7.2...3.1...4.5...2..8.7.....9.4...6.5....1
10.4 99728 13 .2.4...8...7..9...6...3.1......1...5.....84...3.6...2...9.7..6.5.........4.2..3..
10.4 99719 09 .2.4....9......1..7...3..6....9..3...8..7..4.6....1..23...2..7..4....5....5.....8

You can see, that it is rather simple to generate 10+ puzzles. But these are a class easier than the hardest known (at least with gsfr > 99990 and ER > 11.0). To generate those you will need a better strategy (see Coloin's above).

Also note, that Ocean's present for RW, which for me still is the hardest, neither shows much symmetry in the numbers (maybe 234) nor follows dml's rule strictly:
Code: Select all
 +-------+-------+-------+
 | . . . | . . 1 | . 2 . |
 | 3 . . | . 4 . | 5 . . |
 | . . . | 6 . . | . . 7 |
 +-------+-------+-------+
 | . . 2 | . . . | . . 1 |
 | . 8 . | . 9 . | . 3 . |
 | 4 . . | . . . | 8 . . |
 +-------+-------+-------+
 | 5 . . | . . 2 | . . . |
 | . 9 . | . 3 . | 4 . . |
 | . . 6 | 7 . . | . . . |
 +-------+-------+-------+
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Papy » Mon Apr 02, 2007 8:17 am

Sorry...

Papy

PS You can look any where to my puzzles
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Mon Apr 02, 2007 9:50 am

Hi Papy good to hear from you

Congratulations on your 17s !

I cant see whats so special about your subgrids - except the first one has over 20 million grid solutions.....!

What is the answer ?

papy wrote:you cannnot do a band with 17 clues

I think you can !

Cheers
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby coloin » Mon Apr 02, 2007 10:01 am

RW you have sussed it ......

Code: Select all
+---+---+---+
|1..|...|..9|
|.2.|.4.|.7.|
|..3|...|5..|
+---+---+---+
|...|...|...|
|.4.|...|.8.|
|...|...|...|
+---+---+---+
|..5|...|3..|
|.6.|.8.|.2.|
|9..|...|..1|
+---+---+---+  629008 grid sol

+---+---+---+
|1..|...|..9|
|.2.|.4.|.7.|
|..3|...|5..|
+---+---+---+
|...|827|...|
|.4.|639|.8.|
|...|451|...|
+---+---+---+
|..5|...|3..|
|.6.|.8.|.2.|
|9..|...|..1|
+---+---+---+  [SE 9.0]

+---+---+---+
|1..|...|..9|
|.2.|.4.|.7.|
|..3|...|5..|
+---+---+---+
|...|827|...|
|.4.|63.|.8.|
|...|4..|...|
+---+---+---+
|..5|...|3..|
|.6.|.8.|.2.|
|9..|...|..1|
+---+---+---+ SE 10.9 [Edit]


The reason I have found the hard puzzles is that I have looked at all the possible grid solutions of the 16 clue subgrid, all the possible ways to complete the grid with a full box 5 and all the possible ways to remove clues from box 5 !

The above puzzle sequence demonstrates this !

I am rather thinking that there might be mileage in the pattern - but its a bit more complicated
Code: Select all
412
142
223
which is trending towards a "slash"

Incidently why does the 16 clue subgrid have so few grid solutions - as it doesnt fill the grid with other clues........I feel it is the 30-40 clue unavoidables..........

The nuber of grid solutions with a varient 16 clue pattern [100000 - 600000] is critical -
- too many and you get fewer box 5s and less clues to remove
- too few and it becomes too easy to remove clues from box 5 and the resultant puzzles arnt difficult. I got one easy 19 clue this way - unfortnuatly it wasnt a diagonal !

How many "different" 16 clue patterns are there ?

C
Last edited by coloin on Mon Apr 02, 2007 11:26 am, edited 1 time in total.
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby tarek » Mon Apr 02, 2007 10:20 am

Intersting guys.......

& what a nice way to do it coloin........ There were a couple of puzzles posted by Mauricio which probably followed your same strategy (after looking at his filled centre box puzzles) - clever indeed......

I would recommend a revisit to the current hardest using the same method.........

Strip one of the boxes empty ........ fill them & remove extras.........:D

tarek
User avatar
tarek
 
Posts: 2697
Joined: 05 January 2006

Postby coloin » Mon Apr 02, 2007 10:36 am

Thanks Tarek

We should indeed get back to the other thread.

To give the puzzle a reference name - based on the 16 clue subgrid
Code: Select all
+---+---+---+
|1..|...|..9|
|.2.|.4.|.7.|
|..3|...|5..|
+---+---+---+
|...|827|...|
|.4.|63.|.8.|
|...|4..|...|
+---+---+---+
|..5|...|3..|
|.6.|.8.|.2.|
|9..|...|..1|
+---+---+---+ SE 10.9   [Eleanor6]

C
Last edited by coloin on Mon Apr 02, 2007 1:07 pm, edited 1 time in total.
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby ravel » Mon Apr 02, 2007 2:24 pm

RW,

in your pattern i found 131880 puzzles - 5226 of them non isomorphic - with 4-7 givens in the middle box. The generation took about 35 minutes. All have a gsfr > 99212. These are the hardest (canonicalized):
Code: Select all
99809 1...5......67......8...34....76.....5...1.....3...82........9.2.4...2.37......54.
99792 .2.4...8...7..9...6...3...................148.8.5...233...6......9..7....4.2...5.
99757 1...5......67......8...3.4..3...8.9.5...1......76...........968......4.3.9...42.1
99757 1...5......67......8...3.4..3...8.9.5...1......76...........968........3.9...42.1
99757 1...5......67......8...3.4..3...8.9.5...1......76............68......4.3.9...42.1
99753 1....67...5......3..9....4...4....9.7....81...3......5...865......2.....8...176..
They all are rated 9 points by my program, Coloins new puzzle 13 points again.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Mon Apr 02, 2007 2:53 pm

a brilliant way to look at this problem coloin

with a small tweak to my template code (fill the template, not rookeries) my solver can
handle the grunge work -- the inspiration is in determining the template(s) that lead to hard puzzles

the tweak is to treat template clue cells as fixed values
X cells as values to be filled in
and O cells also as values to be filled in

if -m (determine all minimal puzzles) is enabled and any O template cells are present then only
O cells are considered for minimization

I posted a solver update with the template changes
(this update also includes minlex canonical grid generation, but I'm not happy with its speed, see -gbNNN)

the solver also has -q1 and -q2 shorthand options for quick1 and quick2 ratings
-q1 uses nested singles proposition logic
-q2 uses nested singles and pairs (naked, hidden, box-line, x-wing) proposition logic
the ratings are scaled to approximate SE rating 11.4 X 10
i.e., Q2 (-q2) rating 114 approximates SE 11.4 (no floating point expression in my solver)
the approximation is not 100% but computing Q1 Q2 is much much much faster than SE

here is the eleanor6 template
Code: Select all
+---+---+---+
|1..|...|..9|
|.2.|.4.|.7.|
|..3|...|5..|
+---+---+---+
|...|OOO|...|
|.4.|OOO|.8.|
|...|OOO|...|
+---+---+---+
|..5|...|3..|
|.6.|.8.|.2.|
|9..|...|..1|
+---+---+---+

run with this (mouthful of a) command line
Code: Select all
sudoku -gt -m -q2 -e 'max(R)' -f'%v # %3r %10n %8e %(CSM)#c#/q' -Ff'%a/%n %e' eleanor6.tmp

-gt: treat input files as templates
-m: determine minimal puzzles from the generated puzzles
-q2: Q2 rating options
-e'max(R)': only list generated puzzles whose Q2 rating (R) is greater than puzzles already listed
-f: format for each puzzle with comment: rating generated puzzle ordinal, elapsed time, and {clues symmetry backdoor} properties
-Ff: final format listsing #selected puzzles / #generated puzzles and elapsed time

since the rating is (theoretically) the same up to isomorphism and only an increasing
sequence of ratings is selected, there is no need to canonicalize to filter out dup puzzles

a 3Ghz pentium produced this output

1.......9.2..4..7...3...5.....62.....4.5.1.8....874.....5...3...6..8..2.9.......1 # 1 8 4.07052s C23.m/S2.d/M2.235.27
1.......9.2..4..7...3...5.......9....4.57..8....8.2.....5...3...6..8..2.9.......1 # 105 575 17.74s C21.m/M2.116.56
1.......9.2..4..7...3...5.....4......4.7.9.8....26......5...3...6..8..2.9.......1 # 112 4504 1m26.89s C21.m/M2.80.82
1.......9.2..4..7...3...5.....4.8....4.76..8....25......5...3...6..8..2.9.......1 # 114 4544 1m30.02s C22.m/M2.109.60
1.......9.2..4..7...3...5.......8....4.97..8....462.....5...3...6..8..2.9.......1 # 119 4735 1m34.85s C22.m/M2.83.79
1.......9.2..4..7...3...5.....468....4.21..8....7.......5...3...6..8..2.9.......1 # 125 6026 2m00.46s C22.m/S2.a/M2.114.57
6/137460 40m09s

a post-processing script converts to CSV records and adds in ER and Q1 ratings, along with the SE rating time
(this file can be input back into my solver)
Code: Select all
#!sudoku -c5,ER,Q1,Q2,mingirth,puzzle,title,ERtime
096,108,105,3,1.......9.2..4..7...3...5.......9....4.57..8....8.2.....5...3...6..8..2.9.......1,eleanor6,1m28s
105,118,112,7,1.......9.2..4..7...3...5.....4......4.7.9.8....26......5...3...6..8..2.9.......1,eleanor6,8m28s
106,124,114,6,1.......9.2..4..7...3...5.....4.8....4.76..8....25......5...3...6..8..2.9.......1,eleanor6,26m34s
106,126,119,8,1.......9.2..4..7...3...5.......8....4.97..8....462.....5...3...6..8..2.9.......1,eleanor6,18m55s
109,122,125,7,1.......9.2..4..7...3...5.....468....4.21..8....7.......5...3...6..8..2.9.......1,eleanor6,18m55s

girth is an attempt to characterize the hardest puzzles
it measures how many times the constraint methods in scope (e.g. singles) are applied
to propagate changes after a proposition (a guess of one cell value)
e.g., guess [rc]=v, and use singles to determine any other cells that change (girth 1)
make the cell assignments from girth=1 (girth 2), and so on until no more changes due to singles
the number of rounds is the girth

propositions can be done with girth limited to a max value
i.e., only apply the constraints maxgirth times after a guess

for any given puzzle there is minimum maxgirth (mingirth) where the puzzle cannot be
solved with nested propositions for the constraints in scope with maxgirth less than mingirth
(the script determines mingirth by running the solver multiple times)

40m to search 130K puzzles generated by the template
20s to compute { Q1 Q2 mingirth }
>1h to determine ER for 5 puzzles

its possible that the search missed some higher ER puzzles
but that could only be verified by running SE possibly 130K times (70 days @ 1min per puzzle)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Mon Apr 02, 2007 3:01 pm

Using Coloin's methodology :
Code: Select all
1.......2.3..4..5...6...7.....538....4.96..8....4.......2...6...9..8..3.7.......1  SE=11.0
1.......2.3..4..5...6...7.....438....4.56..9....9.......7...6...8..9..3.2.......1  SE=10.9

gsfr=99992

but it took a while to get the SE ratings...

Some more with gsfr>99800 :
Code: Select all
1.......2.3..4..5...6...7.....895....9.46..8....3.......7...6...5..8..3.2.......1  # 99893 # SE=10.9
1.......2.3..4..5...6...7.....839....8.56..9....4.......7...6...5..9..3.2.......1  # 99881
1.......2.3..4..5...6...7.....853....4..92.8....4.......7...6...9..8..3.2.......1  # 99876
1.......2.3..4..5...6...7......89....8.46..3....5.......7...6...5..3..8.2.......1  # 99834
1.......2.3..4..5...6...7.....438....4.5...9....97......7...6...8..9..3.2.......1  # 99832
1.......2.3..4..5...6...7.....85.....5.4...9....3.1.....7...6...4..8..3.2.......1  # 99824
1.......2.3..4..5...6...7.....83.....4.9.2.8....47......7...1...9..8..3.2.......6  # 99823
1.......2.3..4..5...6...7......3.....4.8...3....4.1.....7...6...5..9..4.2.......1  # 99822


Code: Select all
548032 solutions
629008
360152
360152
629008
216240
629008
278912
528496
216240

*btw, I got SE=10.9 for Eleanor 6:?:

JPF
Last edited by JPF on Mon Apr 02, 2007 3:25 pm, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Mon Apr 02, 2007 3:37 pm

Yes the SE was 10.9 for Eleanor6
A relief to see gsf on the case !

The best I did was a few 11.2s.....[St patrick1]
Code: Select all
|---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+
|.4.|7.2|...|   
|...|.9.|...|     
|...|46.|.1.|   
+---+---+---+
|3..|...|8..|   
|.6.|..4|.2.|
|..9|...|..5|
+---+---+---+  St.Patrick 1 SE 11.2


This has this 16 clue base
Code: Select all
5.......9.2.1...7...8...3...4.......................1.3.....8...6...4.2...9.....5  414054 sol.

partner
Code: Select all
5.......9.2.1...7...8...3...4.......................1...3...8...6...4.2.9.......5  295376 sol.

There were many [with an inferior suexrat9] that I didnt even analyse even !

I think gsf will/could get all the 16 clue patterns with 100000 - 800000 sols. I think its too much for me !

I have searched through only "several" different ones

Code: Select all
1.......9.2..4..7...3...5............4.....8............5...3...7..8..2.9.......1
1.......9.2..4..7...3...5............4.....8............6...3...7..8..2.9.......1
1.......9.2..4..7...3...5............4.....8............5...3...6..8..2.9.......1
1.......9.2..4..7...3...5............4.....8............9...3...7..8..2.5.......1
1.......9.2..4..7...3...5............4.....8............5...3...8..7..2.9.......1
1.......9.2..4..7...3...5............4.....8............5...3...8..7..2.6.......1
1.......9.2..4..7...3...5............4.....8............9...3...8..7..2.5.......1

259392 sol.
279152 sol.
629008 sol.
228992 sol.
183472 sol.
252504 sol.
202752 sol.


I got several with less than 120000 but there were no hard puzzles

This pattern is strange...... normally there should be more than 3000000 solutions. There are no generated clues - so why so few solutions ?

C
coloin
 
Posts: 1733
Joined: 05 May 2005

PreviousNext

Return to General