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.
I'm glad I'm not trying to implement puzzle ratings. (I was unsure where to place gsf's rating method.)
: