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)
