## Characterizing the hardest sudokus

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

### Characterizing the hardest sudokus

is long, but I found it difficult to gloss over details when putting it
to paper (screen).

The characterization is based on a solver model extrapolated from the
{ inferior superior superior-plus } threads. The premise of these
threads is a well-defined notion of solution steps. The sudoku constraints
Code: Select all
`  Tn  (naked) n-tuples, 1<=n<=4  Hn  hidden n-tuples, 1<=n<=4  Bn  box-line types 2 and 3  Wn  order n x-wing (2:xwing, 3:swordfish, 4:jellyfish)  X   simple coloring, single-valued X cycles  Y   multi coloring, conjugate pair Y cycles  *   your favorite non-propositional constraint technique here      (propositions are addressed below)`

are organized into ordered groups G1..Gg, where each Gi consists of one
or more constraints. The solver checks Gi in order from left to right.
For the first group that contains a move (a placement or elimination),
the solver identifies all of the moves (without applying them), then
commits all identified moves in one batch, and increments the step
count. It then repeats the process with the first group. This
continues until either the puzzle is solved or no more moves are
possible with the given constraints.

Let {...} denote grouping and : within a group denote "commit moves to
this point but don't count as a step". Then the inferior constraint
order is {T1H1}, the ulterior constraint order is {B2:H1}, and the
superior-plus constraint order is {T1H1B2B3T2H2W2T3H3}{W3T4H4W4},
where the first group is the superior constraints, and the second
group is the plus constraints.

The important property of this step model is that it is immune
to puzzle permutations and constraint application order. i.e.,
isomorphic copies of the same puzzle will produce the same step counts
for a given constraint order.

The step model also allows characterization of puzzles solvable by a
given constraint order, e.g., low/high steppers. In addition,
the number of steps per constraint group gives a measure of the
minimum number of moves from each group required to solve a
puzzle, e.g., "this superior plus puzzle requires at least p
plus moves".

hard puzzles are unsolvable with respect to a given constraint
order and require additional technique(s) to solve. For example,
error/forcing chains/nets, 3d medusa, trial and error, forward
checking, brute force backtracking. To avoid digressing into logic
vs guess
I'll lump all of these techniques into one
proposition technique that fits into the step model.

A proposition assigns a value to a cell with more than one
candidate value and determines the consequences of (discussed
below) that assignment:
(a) contradiction -- the cell cannot have the proposition value.
This produces a candidate elimination (and a placement if
only two candidates remain).
(b) solution -- the cell must have the proposition value.
This produces a placement.
(c) inconclusive -- no progress.

A proposition step consists of all propositions for all cells
with the same number of candidate values, e.g., 2*n
propositions for the n cells with 2 candidate values. As with
the basic step model, placement and elimination moves identified within
a step are committed as a batch at the end of the step. To mimic human
solvers and the time-honored tree search technique of testing the most
constrained cases first, proposition steps are applied in this order:
cells with the least number of candidates to cells with the most
number of candidates. When a proposition step produces a placement
or elimination the solver restarts with the basic constraints.

Note that step counting is slightly different from solving. A solution
is usually arrived at quicker when eliminations and placements are
committed as they are found. But, in order to compare the hardness
of two different puzzles, all of the propositions must be checked at
each step. e.g., a puzzle where all p propositions in the first
step produce a placement or elimination must be easier than a
puzzle where only 1 out of p propositions in the first step
produces a placement or elimination. This is the gist of proposition
step counting.

The details of determines the consequences of control how a
proposition proceeds. After each initial proposition some solvers
propagate naked singles, others naked and hidden singles, or maybe
singles to a given depth. Let proposition constraints denote
the constraint order for constraints propagated by each proposition.
Note that some posted (human) solutions even contain x-wings in the
proposition constraints.

The initial proposition may result in a cascade of moves that can be
determined by iterative application of the proposition constraints.
Define proposition girth to be the number of proposition
constraint iterations for a proposition, step girth to be the
maximum proposition girth for all propositions in a step, and
girth to be the maximum step girth for all steps.

So now we have a way to parameterize the constraints for solving hard
puzzles: the basic constraints C, the proposition constraints
P, and an optional girth limit G (0 for no limit). Let
cPg(p) denote the constraint order with
basic constraint order c, proposition constraint order p,
and girth limit g.

Note that a solver using the constraint order cP(c) (the
same basic and proposition constraints and no girth limit) is similar
to a brute force backtrack solver that propagates c constraints
at each search level. Differences would arise because of proposition
order and move batching.

Now to ocean's hardest. We can expose a puzzle hierarchy with a series
of constraint orders. I used these, but the combinations are only
limited by the constraints in scope:
Code: Select all
`  T1H1P4(T1H1)V(2)  T1H1P8(T1H1)V(3)  T1H1{B2B3}T2H2W2T3H3W3T4H4W4P(T1H1)V(4)  T1H1P(T1H1{B2B3})V(5)  T1H1P(T1H1{B2B3}T2)V(6)  T1H1P(T1H1{B2B3}T2H2)V(7)`

where V(n) labels the constraint order that produces a
Valid solution. I set up a search that applies the constraint
orders in order from V(2) (easiest) through V(7) (hardest) for each
puzzle and listed the constraint order label and number of proposition
steps for each puzzle, along with a puzzle rating in the range 1
(easiest) through 99999 (hardest) that incorporates the constraint
label, proposition steps, and girth:
Code: Select all
`99000 + label*100 + steps*10 + girth/2`

[edit: added girth and exact proposition rating formula]

There is a question of n steps constraint order A vs m
steps constraint order B, A harder than B but n < m, but
I ignored those for now. Also, its not clear whether constraint moves
within a proposition can be batched, since a contradiction may be
one of the proposition outcomes -- my solver doesn't batch these.

Here is the ranking of ocean's two hardest sudoku posts (ocean-01 ocean-02),
hardest to easiest, with the puzzle ordinal, proposition constraint index,
proposition steps, and 1..99999 rating.

Code: Select all
`ocean-02  3 7  2 99729ocean-01  1 6 10 99706ocean-01  2 6  9 99699ocean-01  8 6  9 99697ocean-02 12 6  6 99667ocean-01  3 6  5 99660ocean-01  5 6  4 99650ocean-01  4 5  9 99597ocean-01 15 5  6 99567ocean-02  1 5  5 99560ocean-02  9 5  5 99559ocean-02 11 5  5 99559ocean-02 18 5  5 99557ocean-02 17 5  5 99556ocean-01 30 5  4 99549ocean-02 13 5  4 99548ocean-02 14 5  4 99548ocean-02  7 5  3 99537ocean-02  8 5  3 99537ocean-02  2 5  3 99536ocean-01 32 5  2 99529ocean-01  6 5  2 99527ocean-02  4 5  2 99527ocean-01 13 5  1 99518ocean-02  5 5  1 99517ocean-01 18 4  7 99477ocean-02 21 4  7 99477ocean-01 14 4  7 99476ocean-01 17 4  6 99467ocean-01 28 4  5 99457ocean-01  7 4  4 99446ocean-01 10 4  4 99446ocean-01 11 4  4 99446ocean-01 27 4  4 99446ocean-02 23 4  4 99445ocean-02 22 4  4 99444ocean-01 12 4  3 99437ocean-01 25 4  3 99437ocean-01 19 4  3 99435ocean-01 24 4  2 99427ocean-02 20 4  2 99425ocean-02  6 4  1 99416ocean-02 10 4  1 99416ocean-02 15 4  1 99416ocean-02 16 4  1 99415ocean-01 22 3  8 99384ocean-01 26 3  8 99384ocean-01 29 3  8 99384ocean-02 19 3  8 99384ocean-01 23 3  7 99374ocean-01 20 3  5 99354ocean-01 31 3  5 99354ocean-01 16 3  3 99334ocean-01 21 3  3 99334ocean-01  9 3  1 99314`

[edit: corrected counting error when basic constraints weaker than proposition constraints]

options:

Code: Select all
`-B -f'%f:%j %16@%(V)x %2(P)x %5r' -q hardest`

or experiment with your own basic and proposition constraint orders:

Code: Select all
`-B -qT1H2B2-G -Z'T1H2P(T1H1)V(2)||T1H2BP(T1H1B)V(3)' -e'V'`

where -B means batch moves, -q specifies the basic constraint order
(and -G means no guessing), -Z specifies (multiple) constraint orders
with labeled proposition constraints (the first || group from the left
that solves the puzzle), and -e lists only valid puzzles (solvable by
the given constraints). The -T0x20 test option lists proposition
constraint application details.
Last edited by gsf on Tue Sep 12, 2006 2:43 am, edited 3 times in total.
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Characterizing the hardest sudokus

Interesting with a new characterization method for hard puzzles. Good job!
And of course flattering that you use my puzzles for "calibration".
Having a batch program available for evaluating puzzles should be quite useful and effective.
Think I need some time for study and experiments in order to fully understand the step count method and how it compares to other evaluation methods.
Ocean

Posts: 442
Joined: 29 August 2005

### Re: Characterizing the hardest sudokus

Ocean wrote:And of course flattering that you use my puzzles for "calibration".

thanks
challenge is a good motivator
I edited the original post to include the exact rating formula and
to correct a counting error in the posted ratings for cases where
the basic constraints are weaker than the proposition constraints
(the error ended up making additional proposition iterations even if
the solver executables were also reposted to correct the error
I also added V(n) expression labels to the -T0x20 proposition
trace so you can correlate proposition stats and V(n) supexpressions
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Characterizing the hardest sudokus

Excuse me gsf, how are these ocean-01 and ocean-02 puzzles? It seems that they are 32 and 23 respectively, but I don't succeed in founding any 32- or 23-Ocean's sudokus list. May you give a link?
Regards,

ptener
ptener

Posts: 1
Joined: 08 September 2006

### Re: Characterizing the hardest sudokus

ptener wrote:Excuse me gsf, how are these ocean-01 and ocean-02 puzzles? It seems that they are 32 and 23 respectively, but I don't succeed in founding any 32- or 23-Ocean's sudokus list. May you give a link?
Regards,

ocean-01
ocean-02
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Characterizing the hardest sudokus

here are the ratings for the 289 hardest puzzles posted here
(note that 241 and 244 are isomorphic, and 265 and 269 are identical)
the columns are puzzle index, constraint order index, proposition steps, and rating, highest to lowest
Code: Select all
`268 7  2 99729201 6 10 99706203 6  9 99699211 6  9 99697276 6  6 99667202 6  5 99660198 6  5 99657210 6  4 99650185 6  4 99647192 6  2 99628214 5  9 99597207 5  6 99567266 5  5 99560273 5  5 99559275 5  5 99559168 5  5 99558282 5  5 99557281 5  5 99556226 5  4 99549277 5  4 99548278 5  4 99548  2 5  3 99537157 5  3 99537272 5  3 99537246 5  3 99536267 5  3 99536219 5  2 99529  1 5  2 99528217 5  2 99527265 5  2 99527269 5  2 99527209 5  1 99518270 5  1 99517289 5  1 99517288 5  1 99516205 4  7 99477284 4  7 99477170 4  7 99476208 4  7 99476165 4  6 99468206 4  6 99467182 4  6 99466 46 4  6 99465231 4  5 99457173 4  5 99456 18 4  4 99448250 4  4 99447204 4  4 99446212 4  4 99446213 4  4 99446221 4  4 99446262 4  4 99446286 4  4 99445285 4  4 99444177 4  3 99437216 4  3 99437220 4  3 99437238 4  3 99437 70 4  3 99436223 4  3 99435143 4  2 99427227 4  2 99427 40 4  2 99426 11 4  2 99425 41 4  2 99425167 4  1 99416179 4  1 99416271 4  1 99416274 4  1 99416279 4  1 99416152 4  1 99415280 4  1 99415 15 3  9 99394 17 3  9 99394 45 3  9 99394 47 3  9 99394147 3  9 99394181 3  9 99394193 3  9 99394 14 3  8 99384 20 3  8 99384 52 3  8 99384 83 3  8 99384142 3  8 99384144 3  8 99384155 3  8 99384171 3  8 99384184 3  8 99384199 3  8 99384224 3  8 99384229 3  8 99384230 3  8 99384283 3  8 99384  5 3  7 99374 42 3  7 99374 53 3  7 99374 59 3  7 99374 91 3  7 99374110 3  7 99374136 3  7 99374150 3  7 99374151 3  7 99374183 3  7 99374228 3  7 99374245 3  7 99374261 3  7 99374  4 3  6 99364  6 3  6 99364  8 3  6 99364  9 3  6 99364 19 3  6 99364 21 3  6 99364 24 3  6 99364 43 3  6 99364 44 3  6 99364 64 3  6 99364107 3  6 99364123 3  6 99364138 3  6 99364141 3  6 99364154 3  6 99364161 3  6 99364163 3  6 99364166 3  6 99364169 3  6 99364175 3  6 99364176 3  6 99364200 3  6 99364239 3  6 99364249 3  6 99364257 3  6 99364263 3  6 99364  3 3  5 99354  7 3  5 99354 12 3  5 99354 13 3  5 99354 27 3  5 99354 48 3  5 99354 49 3  5 99354 50 3  5 99354 57 3  5 99354 58 3  5 99354 73 3  5 99354 74 3  5 99354100 3  5 99354125 3  5 99354127 3  5 99354140 3  5 99354145 3  5 99354156 3  5 99354222 3  5 99354225 3  5 99354236 3  5 99354254 3  5 99354259 3  5 99354264 3  5 99354287 3  5 99354 31 3  5 99353 23 3  4 99344 26 3  4 99344 28 3  4 99344 35 3  4 99344 36 3  4 99344 51 3  4 99344 62 3  4 99344 63 3  4 99344 67 3  4 99344 69 3  4 99344 75 3  4 99344 81 3  4 99344 89 3  4 99344 96 3  4 99344 97 3  4 99344105 3  4 99344106 3  4 99344117 3  4 99344131 3  4 99344139 3  4 99344153 3  4 99344162 3  4 99344172 3  4 99344180 3  4 99344260 3  4 99344 16 3  3 99334 25 3  3 99334 29 3  3 99334 33 3  3 99334 56 3  3 99334 82 3  3 99334114 3  3 99334126 3  3 99334128 3  3 99334130 3  3 99334135 3  3 99334148 3  3 99334149 3  3 99334158 3  3 99334160 3  3 99334164 3  3 99334174 3  3 99334178 3  3 99334189 3  3 99334195 3  3 99334197 3  3 99334215 3  3 99334232 3  3 99334251 3  3 99334 22 3  2 99324 86 3  2 99324 87 3  2 99324115 3  2 99324122 3  2 99324159 3  2 99324188 3  2 99324248 3  2 99324252 3  2 99324256 3  2 99324 10 3  1 99314112 3  1 99314124 3  1 99314146 3  1 99314218 3  1 99314243 3  1 99314 34 2  9 99292 39 2  9 99292 60 2  9 99292 72 2  9 99292 80 2  9 99292 92 2  9 99292 94 2  9 99292 95 2  9 99292 99 2  9 99292102 2  9 99292103 2  9 99292116 2  9 99292119 2  9 99292132 2  9 99292186 2  9 99292196 2  9 99292258 2  9 99292 68 2  8 99282 77 2  8 99282109 2  8 99282121 2  8 99282187 2  8 99282235 2  8 99282240 2  8 99282 37 2  7 99272 54 2  7 99272 55 2  7 99272 61 2  7 99272 79 2  7 99272 85 2  7 99272 93 2  7 99272 98 2  7 99272104 2  7 99272118 2  7 99272120 2  7 99272241 2  7 99272242 2  7 99272244 2  7 99272255 2  7 99272 30 2  6 99262 32 2  6 99262 65 2  6 99262 71 2  6 99262 76 2  6 99262 84 2  6 99262 88 2  6 99262111 2  6 99262113 2  6 99262190 2  6 99262247 2  6 99262 38 2  5 99252 78 2  5 99252 90 2  5 99252108 2  5 99252133 2  5 99252233 2  5 99252234 2  5 99252253 2  5 99252101 2  4 99242129 2  4 99242134 2  4 99242137 2  4 99242191 2  4 99242 66 2  3 99232237 2  3 99232194 2  2 99222`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Characterizing the hardest sudokus

gsf wrote:(note that 241 and 244 are isomorphic, and 265 and 269 are identical)

Thanks for pointing that out. 241 was a wrong copy and i did not notice, that the grid at the top of Oceans list was identical with the 4th puzzle in the list. To correct the latter, i had to renumber now 289 to 269.

This thread and your program are very interesting. I will study it, as soon as i can find some time.

[Added:] Since i noticed, that the highest rated puzzle here "only" had a 5-step rating from my program, i would be interested, how Maria or Carcul would rate it compared to those on top of my list:
Code: Select all
` +-------+-------+-------+ | 1 . . | . . . | . . 2 | | . 3 . | . 4 . | . 5 . | | . . 6 | . . . | 7 . . | +-------+-------+-------+ | . . . | 1 . 3 | . . . | | . 8 . | . 7 . | . 4 . | | . . . | 4 . 6 | . . . | +-------+-------+-------+ | . . 2 | . . . | 6 . . | | . 5 . | . 3 . | . 8 . | | 9 . . | . . . | . . 1 | +-------+-------+-------+`
ravel

Posts: 998
Joined: 21 February 2006

I have only looked at ratings during the last few weeks, but it seems like there could be four different approaches:
1. Number of steps -- minimum number of "difficult steps" (ravel's approach)
2. Peak difficulty -- the difficulty rating of the most difficult step (Sudoku Explainer's approach)
3. Average difficulty -- a method to distinguish, e.g., between a puzzle with a ten steps of difficulty 9 and a puzzle with ten steps with one of each difficulty 1, 2, ... 10
4. Overall difficulty -- a method to distinguish, e.g., between a puzzle with one step of difficulty 9 and ten steps of difficulty 9
Yikes I'm glad I'm not trying to implement puzzle ratings. (I was unsure where to place gsf's rating method.)

[edit: numbered the list, shortened names, and expanded descriptions]
Last edited by ronk on Sun Sep 24, 2006 2:57 pm, edited 1 time in total.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:Yikes I'm glad I'm not trying to implement puzzle ratings.

From gsf's man page :
gsf wrote:Its easier to solve than to generate,
and easier to generate than to rate.
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:
ronk wrote:Yikes I'm glad I'm not trying to implement puzzle ratings.

From gsf's man page :
gsf wrote:Its easier to solve than to generate,
and easier to generate than to rate.

I recently added "and easier to code than to document"
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

ronk wrote:(I was unsure where to place gsf's rating method.)

how about step_difficulty.number_of_steps with (an attempt at) a precise definition for step
for consistency across isomorphic puzzles
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf,

i now have tried to understand your rating system, but some things remained unclear. I think, they can be clarified best by looking at an example.
Most helpful for me would be a list of the steps, their moves and the changes in the rating for the leader in your list.

A typical situation for very hard puzzles after applying all possible basic constraints might be:
25 cells given or resolved
A sum of 250 candidates in the remaining 56 cells.
1 backdoor candidate (leads to a solution with propagation constraints)

If i understood it right, your program then applies all possible eliminations with candidates in bivalue cells (or solve with the backdoor candidate, if ther is only one more candidate) as one step.
What i dont quite understand is the girth limit here (which can be set as paramter and goes into the rating). Does it limit contraint iterations for each proposition (placement or elimination) ? What are typical numbers for this limit and how is it rated, when not set (unlimited) ?
Please can you also re-explain, what the outputted "proposition constraint index" and "proposition steps" mean ?
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:I think, they can be clarified best by looking at an example.

What i dont quite understand is the girth limit here (which can be set as paramter and goes into the rating). Does it limit contraint iterations for each proposition (placement or elimination) ? What are typical numbers for this limit and how is it rated, when not set (unlimited) ?
Please can you also re-explain, what the outputted "proposition constraint index" and "proposition steps" mean ?

for girth, consider naked singles
look at all the cells and identify the naked singles
then apply the naked singles
that's one iteration of the the naked singles constraint
applying those naked singles may have exposed some more
so you get those with another iteration of the naked singles constraint
girth simply counts the number of constraint iterations until no more eliminations or placements

limiting the girth limits the constraint iterations
a puzzle that solves with a proposition constraint girth of 2 is somehow
easier than one that solves only with girth 10

now I'll annotate the output for
Code: Select all
`sudoku -v -T0x30 -qhardest -f%Q ocean-02-03.dat`

where ocean-02-03.dat contains
Code: Select all
`1 . . | . . . | . . 2. 3 . | . 4 . | . 5 .. . 6 | . . . | 7 . .------+-------+------. . . | 1 . 3 | . . .. 8 . | . 7 . | . 4 .. . . | 4 . 6 | . . .------+-------+------. . 2 | . . . | 6 . .. 5 . | . 3 . | . 8 .9 . . | . . . | . . 1`

note that real output will have nice alignment
I didn't use [ code ] ... [ /code ] here so lines won't wrap

-T0x10 lists the constraints in scope
the "which" constraints are tried in order
these contain the propostion constraints and are labeled 2..7 via V(2) .. V(7)
easiest to hardest
so "proposition constraint index 4" is the constraint with label V(4)

constraint order which : FNP4(FN)E(P<=9)V(2) : FNP4(FN)E(P<=9)V(2)
constraint order : FN : FN
constraint order which : FNP8(FN)E(P<=9)V(3) : FNP8(FN)E(P<=9)V(3)
constraint order : FN : FN
constraint order which : -XY+P(FN)E(P<=9)V(4) : FN{B2B3}T2H2W2T3H3W3T4H4W4P(FN)E(P<=9)V(4)
constraint order : FN : FN
constraint order which : FNP(FNB)E(P<=9)V(5) : FNP(FNB)E(P<=9)V(5)
constraint order : FNB : FN{B2B3}
constraint order which : FNP(FNBT2)V(6) : FNP(FNBT2)V(6)
constraint order : FNBT2 : FN{B2B3}T2
constraint order which : FNP(FNBT2H2)V(7) : FNP(FNBT2H2)V(7)
constraint order : FNBT2H2 : FN{B2B3}T2H2
constraint order solve : FNBTHWXYG-G : FN{B2B3}T2H2W2T3H3W3T4H4W4XY
constraint order quick : FNG : FNG
constraint order magic : FNBTHW : FN{B2B3}T2H2W2T3H3W3T4H4W4

here is the trace for the basic constraints up to "---- subexpression 2 ----"
there is no "S" (solution) so the basic constraints don't solve the puzzle
the first step used box-line "B" to get "4" elimiations, etc.

1 3 [1] B4 [15][35][75][95]^8
2 5 H2 [71][93]={38}
3 6 W8 [63][36][76][67]^1 [41][14][94][49]^6

"---- subexpression 2 ----" starts the trace for the V(2) constraints
these did nothing, nor did the V(3) constraints

---- subexpression 2 ----
propositions 245 solutions 0 contradictions 0 iterations 461 girth 4
---- subexpression 3 ----
propositions 245 solutions 0 contradictions 0 iterations 463 girth 6
---- subexpression 4 ----
1 3 B4 [15][35][75][95]^8
2 5 H2 [71][93]={38}
3 6 W8 [63][36][76][67]^1 [41][14][94][49]^6
propositions 159 solutions 0 contradictions 1 iterations 294 girth 5
298 11 P1 [59]^5
propositions 228 solutions 0 contradictions 0 iterations 424 girth 5

V(4) made 159 propositions and got 1 elimination, 294 iterations total,
with 5 iterations max required per-proposition (girth)

---- subexpression 5 ----
propositions 142 solutions 0 contradictions 8 iterations 454 girth 12
455 3 P8 [95][75][15]^8 [93][71]^7 [71]^4 [59][51]^5
propositions 219 solutions 0 contradictions 3 iterations 642 girth 8
1098 3 P3 [57]^5 [57]^9 [35]^8
propositions 234 solutions 0 contradictions 0 iterations 547 girth 7
---- subexpression 6 ----
propositions 142 solutions 0 contradictions 9 iterations 494 girth 12
495 3 P9 [95][75][15]^8 [93][71]^4 [93][71]^7 [59][51]^5
propositions 133 solutions 0 contradictions 2 iterations 435 girth 9
931 3 P2 [39][17]^9
propositions 216 solutions 0 contradictions 4 iterations 699 girth 9
1631 3 P4 [94]^6 [57]^5 [57]^9 [35]^8
propositions 230 solutions 0 contradictions 1 iterations 608 girth 9
2240 3 P1 [76]^1
propositions 229 solutions 0 contradictions 0 iterations 605 girth 9

each "P" is a proposition step
try -v3 to see the details of each step (there's a lot!)

---- subexpression 7 ----
propositions 54 solutions 0 contradictions 4 iterations 320 girth 15
321 3 P4 [92][81]^4 [38]^3 [27]^8

for V(7) 54 propositions produced 4 eliminations

propositions 47 solutions 3 contradictions 8 iterations 462 girth 19
781 3 P11 [98]^3 [87][32]^4 [83][72]^7 [29][18]^9 [23]^8 [23]=9 [21]=7 [12]=4

another round of propositions produced 8 eliminations but also hit 3 solutions
the remainder of the trace leads to the solution using only the V(7) proposition constraints FNBT2H2

782 1 F4 [27][72]=1 [32]=2 [81]=6
783 1 F3 [38]=9 [83]=4 [92]=7
784 1 F2 [62]=9 [98]=2
785 1 F2 [42]=6 [87]=9
786 1 F2 [48][89]=7
787 1 F3 [43]=5 [78]=3 [84]=2
788 1 F5 [13][71]=8 [18]=6 [68][86]=1
789 1 F4 [17][93]=3 [29]=8 [31]=5
790 1 F7 [24]=6 [26]=2 [36]=8 [39]=4 [49]=9 [53]=1 [63]=7
791 1 F3 [34]=3 [35]=1 [79]=5
792 1 F3 [69]=3 [75]=9 [97]=4
793 1 F5 [15][96]=5 [59]=6 [61]=2 [74]=7
794 1 F7 [14][56]=9 [41][76]=4 [51]=3 [65][94]=8
795 1 F5 [16]=7 [45]=2 [54][67]=5 [95]=6
796 1 F2 [47]=8 [57]=2
S
99729 FNBTHP C21.M/S8.f/F180.471/N163.735/B188.624.179.38/T82.331.82/H95.198.95/P2.15.101.3.12.782.19/M1.2.8/V7

the rating is 99000 + 100*subexpressionindex (7 from V(7)) + #propositions*10 + girth
FNBTHP are the identifiers for the constraints required to solve
and the remaining /-separated info are the constraint stats
C21.M: 21 clues symmetric minimal
S8.f: symmetry class 8 - full symmetry
F180.471 180 naked single applications, 471 placements
N163.735 163 hidden single applications 163 placements
B188.624.179.38 188 box-line applications, 624 eliminations, 179 type-2, 38 type-3
T82.331.82 82 naked tuple applications, 331 eliminations, 82 pairs
H95.198.95 95 hidden tuple applications, 198 eliminations, 95 pairs
P2.15.101.3.12.782.19 2 proposition applications, 15 eliminations, 101 propositions, 3 solutions, 12 contradictions, 782 constraint iterations, girth 19
M1.2.8 2 backdoors of size 1
V7 constraint index/label 7

hope that helps
my program output and descriptions tend to be terse
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

I compared 2 puzzles, where our ratings differ very much:

178: Ocean #11/18 (ER 9.4) (15 BF steps) has "only" rating 99334 (a value i saw for many puzzles also, which needed less than 4 BF steps).
Gurths recent pearl (ER 9.1), which (in 2 ways) can be solved with 1 BF step only, has a higher rating of 99384.
The numbers of possible eliminations after the first stuck point are 21 out of 223 vs. 95/198, the numbers of backdoors (for my program) are 2 vs. 12.
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:I compared 2 puzzles, where our ratings differ very much:

178: Ocean #11/18 (ER 9.4) (15 BF steps) has "only" rating 99334 (a value i saw for many puzzles also, which needed less than 4 BF steps).
Gurths recent pearl (ER 9.1), which (in 2 ways) can be solved with 1 BF step only, has a higher rating of 99384.
The numbers of possible eliminations after the first stuck point are 21 out of 223 vs. 95/198, the numbers of backdoors (for my program) are 2 vs. 12.

Code: Select all
`# ocean..1.....2.3..4....5..6..3....4..7..1....8..3.9..2..6.......8..9.7..2..4.2..1..8..# gurth..63..4...3..6..2.1.......7..59......9..3..7......7..26....8..4.5..4..8...9...1.. `

the rating differences are due to the girth limits of 4 and 8 for the V(2) and V(3) constraints
and my omission of 'FNP(FN)',
try -q'FNP(FN)' and
ocean solves with 2 batched proposition steps girth 11
gurth solves with 1 batched proposition step girth 14

there's room for adjustment, especially with how girth fits in to the ratings
girth measure how deep each proposition must be applied to reach a placement or contradiction
e.g., FN with girth 11 means that at least one proposition required singles
to be re-applied 10 times (11 iterations) to reach a placement or contradiction
there is some connection between #proposition steps and girth, but
maybe for FN (singles) a girth of 8 vs. 11 doesn't matter that much

as for the # of backdoors of size 1, ocean:2 gurth:12 is for when all basic constraints are enabled,
the # FN backdoors of size 1 for gurth is 4 (ocean has FN backdoor size 2)
FNBT2 on ocean yields 2 backdoors of size 1
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next