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 99729`

ocean-01 1 6 10 99706

ocean-01 2 6 9 99699

ocean-01 8 6 9 99697

ocean-02 12 6 6 99667

ocean-01 3 6 5 99660

ocean-01 5 6 4 99650

ocean-01 4 5 9 99597

ocean-01 15 5 6 99567

ocean-02 1 5 5 99560

ocean-02 9 5 5 99559

ocean-02 11 5 5 99559

ocean-02 18 5 5 99557

ocean-02 17 5 5 99556

ocean-01 30 5 4 99549

ocean-02 13 5 4 99548

ocean-02 14 5 4 99548

ocean-02 7 5 3 99537

ocean-02 8 5 3 99537

ocean-02 2 5 3 99536

ocean-01 32 5 2 99529

ocean-01 6 5 2 99527

ocean-02 4 5 2 99527

ocean-01 13 5 1 99518

ocean-02 5 5 1 99517

ocean-01 18 4 7 99477

ocean-02 21 4 7 99477

ocean-01 14 4 7 99476

ocean-01 17 4 6 99467

ocean-01 28 4 5 99457

ocean-01 7 4 4 99446

ocean-01 10 4 4 99446

ocean-01 11 4 4 99446

ocean-01 27 4 4 99446

ocean-02 23 4 4 99445

ocean-02 22 4 4 99444

ocean-01 12 4 3 99437

ocean-01 25 4 3 99437

ocean-01 19 4 3 99435

ocean-01 24 4 2 99427

ocean-02 20 4 2 99425

ocean-02 6 4 1 99416

ocean-02 10 4 1 99416

ocean-02 15 4 1 99416

ocean-02 16 4 1 99415

ocean-01 22 3 8 99384

ocean-01 26 3 8 99384

ocean-01 29 3 8 99384

ocean-02 19 3 8 99384

ocean-01 23 3 7 99374

ocean-01 20 3 5 99354

ocean-01 31 3 5 99354

ocean-01 16 3 3 99334

ocean-01 21 3 3 99334

ocean-01 9 3 1 99314

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

You can reproduce results by downloading my latest solver and using these

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.