The Hidden Logic of Sudoku
A new conceptual framework
for solving Sudoku puzzles with pure logic
Denis Berthier
First edition: May 2007
Second edition: November 2007
Online Supplements
The zt-ing principle
Generalised whips
and braids
© Denis
Berthier. All the material in this page and the pages it gives
access to are the property of the author and may not be
re-published or re-posted without his prior written permission.
Warning: you should read and
understand the concepts in the whips page
and the braids page before reading this
page.
1) INTRODUCTION TO THE ZT-ING PRINCIPLE
There are elementary or "atomic"patterns and there are ways to
combine them into more complex ones.
Examples of atomic patterns:
Naked, Hidden and Super-Hidden (i.e. Fish) subsets: Singles, Pairs,
Triplets, Quads.
Almost-ing is the standard way of combining such "atomic" patterns
into chains. For example:
- an xy-chain can be seen as a chain of almost-ed Naked-Singles
- an nrc-chain (basic NL or basic AIC) can be seen as a chain of
almost-ed Naked or Hidden Singles
- an ALS-chain can be seen as a chain of almost-ed Naked sets
(Singles, Pairs, Triplets, Quads, ...)
As mentioned by Gerra in the "Almosting" thread of the Sudoku
Player's Forum, here http://www.sudoku.com/boards/viewtopic.php?t=6100
: "Almost everything can be Almosted, I suppose, and these Almost
patterns can be chained up with anything."
If, instead of almost-ing, you do zt-ing,
you get:
- an xyzt-chain is a chain of zt-ed Naked-Singles
- an nrczt-chain (basic NL or basic AIC) is a chain of zt-ed Naked
or Hidden Singles
- a zt-whip(ALS) is a chain of zt-whipped Naked, Hidden and
Super-Hidden (Fish) sets (Singles, Pairs, Triplets, Quads)
- a zt-braid(ALS) is a chain of zt-braided Naked, Hidden and
Super-Hidden (Fish) sets (Singles, Pairs, Triplets, Quads)
The zt-ing principle can also be extended to any Constraints
Satisfaction Problem (see CSP1
and CSP2).
The following idea is the generalisation of the idea of the z- and
t- extensions, first introduced in the first edition of my book for
xyz-, xyt- and xyzt- chains and extended in the second edition to
nrc-, nrcz-, nrct- and nrczt- chains.
"zt-ing", which can be seen as a generalisation of
"almost-ing", is the natural way of including elementary
patterns in chains, whips or braids.
Instead of almost-ing wrt to the previous right-linking
candidate in the chain, zt-ing does almost-ing wrt to the
target and all the previous right-linking candidates.
It is a natural, and fully supersymmetric, generalisation of the
"almost-ing" principle widely used to include ALS, AALS, AAALS ...,
AHS, AAHS, ...., A-Fish, AA-Fish, ..., in AICs.
In the same way as my definition of a chain unifies the previously
conflicting views of a chain as a sequence of candidates and as a
sequence of cells (in this case of rc-, rn-, cn- or bn- cells), my
definitions of a generalised whip or braid in the following sections
unifiy the research on elementary patterns with limited resolution
potential and the research on more complex patterns with broad
resolution potential, which have to be based on chains, whips or
braids.
zt-ing has been applied to define chains, whips or braids of
increasigly high complexity (although the basic nrczt-whips are
enough to solve all the puzzles that a human player can solve):
- xyzt-chains
- nrczt-chains, lassos, nrczt-whips and nrczt-braids
The classification results
show how powerful the basic nrczt-whips are: in 10,000,000 randomly
generated puzzles (using various types of random generators), none
was found that whips could not solve.
In this page, we apply our general zt-ing principle to define more
complex whips and braids that can be used to solve exceptionally
hard puzzles: zt-whips(FP) and zt-braids(FP), where FP is a family
of patterns with an associated resolution rule.
Results at the bottom of the this page (section 3.3) show how
powerful the zt-ing principle is.
2) GENERALISED WHIPS
2.1) HINGES,
HINGED-zt-WHIPS, zt-LOCKED-SETS, zt-WHIPS(LS) and
HINGED-zt-WHIPS(LS)
The goal of this section is to show how one can extend the
nrczt-whips in such a way that they generalise AICs wth ALSs. This
extension is much more general than merely inserting standard ALSs
within a whip or a braid.
2.1.1) Hinges and hinged-zt-whips
Hinges were first introduced by Ron Haglund.
Define a segment as the intersection of a row or column with a
block.
Hinges are the means of using basic interactions (BI) within a
chain.
The typical situation is as follows (rows and columns can be
interchanged; the roles of rows and blocks can be interchanged):
For some number n, we have the pattern:
Code:
? ? ?
+ + (+)
X X X
X X +in
? ? +out
? means presence of n irrelevant
+ means presence of n compulsory
(+) means presence of n optional
X means presence of n forbidden
+in means that n is present and is used as a left-linking candidate
+ out means that n is present and is used as the next left-linking
candidate
Definition: a segment-candidate is a number together with the cells
of a segment in which it is present as a candidate.
Definition: a segment-candidate is nrc-linked to a candidate if both
have the same the number-component and if the rc-cell of the
candidate is rc-linked to all the rc-cells of the segment-component.
We can now define a hinged zt-whip in the same way as an nrczt-whip
by allowing right-linking candidates to be either an ordinary
candidate or a segment-candidate.
As usual, we have the corresponding:
hinged-zt-whip elimination theorem:
given a hinged-zt-whip, one can eliminate its target.
the proof of which is obvious, as for basic nrczt-whips.
The only difference is that we need to say what being true means for
a segment-candidate: it merely means that one of the occurrences of
the number in the segment must be true, which leaves no possibility
of being true for the next left-linking candidate.
2.1.2) Locked Sets and zt-whips(LS)
Given a set S of candidates, one can easily extend the definitions
of Naked, Hidden and Super-Hidden (i.e. fish) Subsets to Naked,
Hidden and Super-Hidden (i.e. fish) subsets modulo S: what remains
when all the candidates that are nrc-linked to at least one element
of S are "forgotten", must be a Naked, Hidden and Super-Hidden (i.e.
fish) Subset.
More specifically:
Definitions: Given a set S
of candidates,
- an rc-cell and a number constitute a Naked-Single modulo S if,
when all the candidates that are nrc-linked to at least one element
of S are fogotten, what remains is a Naked-Single in this rc-cell
for this number.
- a set of 2 rc-cells in the same row (resp. column, block) and a
set of 2 numbers constitute a Naked-Pairs-in-a-row (resp. column,
block) modulo S if, when all the candidates that are nrc-linked to
at least one element of S are fogotten, what remains is a
Naked-Pairs-in-a-row (resp. column, block) in these 2 rc-cells for
these 2 numbers.
- a set of 3 rc-cells in the same row (resp. column, block) and a
set of 3 numbers constitute a Naked-Triplets-in-a-row (resp. column,
block) modulo S if, when all the candidates that are nrc-linked to
at least one element of S are fogotten, what remains is a
Naked-Triplets-in-a-row (resp. column, block) in these 3 rc-cells
for these 3 numbers.
- a set of 4 rc-cells in the same row (resp. column, block) and a
set of 4 numbers constitute a Naked-Quads-in-a-row (resp. column,
block) modulo S if, when all the candidates that are nrc-linked to
at least one element of S are fogotten, what remains is a
Naked-Quads-in-a-row (resp. column, block) in these 4 rc-cells for
these 4 numbers.
- an rc-cell and a number constitute a Hidden-Single-in-a-row (resp.
column, block) modulo S if, when all the candidates that are
nrc-linked to at least one element of S are fogotten, what remains
is a Hidden-Single-in-a-row (resp. column, block) in this rc-cell
for this number.
- a set of 2 rc-cells in the same row(resp. column, block) and a set
of 2 numbers constitute a Hidden-Pairs-in-a-row (resp. column,
block) modulo S if, when all the candidates that are nrc-linked to
at least one element of S are fogotten, what remains is a
Hidden-Pairs-in-a-row (resp. column, block) in these 2 rc-cells for
these 2 numbers.
- a set of 3 rc-cells in the same row (resp. column, block) and a
set of 3 numbers constitute a Hidden-Triplets-in-a-row (resp.
column, block) modulo S if, when all the candidates that are
nrc-linked to at least one element of S are fogotten, what remains
is a Hidden-Triplets-in-a-row (resp. column, block) in these 3
rc-cells for these 3 numbers.
- a set of 4 rc-cells in the same row (resp. column, block) and a
set of 4 numbers constitute a Hidden-Quads-in-a-row (resp. column,
block) modulo S if, when all the candidates that are nrc-linked to
at least one element of S are fogotten, what remains is a
Hidden-Quads-in-a-row (resp. column, block) in these 4 rc-cells for
these 4 numbers.
- a set of 2 rc-cells in the same row (resp. column) and a set of 2
columns (resp. rows) constitute an X-Wing-in-a-row (resp. column)
modulo S if, when all the candidates that are nrc-linked to at least
one element of S are fogotten, what remains is an X-Wing-in-a-row
(resp. column) in these 2 rows (resp. columns) for these 2 columns
(resp.rows).
- a set of 3 rc-cells in the same row (resp. column) and a set of 3
columns (resp. rows) constitute a Swordfish-in-a-row (resp. column)
modulo S if, when all the candidates that are nrc-linked to at least
one element of S are fogotten, what remains is a Swordfish-in-a-row
(resp. column) in these 3 rows (resp. columns) for these 3 columns
(resp.rows).
- a set of 4 rc-cells in the same row (resp. column) and a set of 4
columns (resp. rows) constitute a Jellysfish-in-a-row (resp. column)
modulo S if, when all the candidates that are nrc-linked to at least
one element of S are fogotten, what remains is a Jellysfish-in-a-row
(resp. column) in these 4 rows (resp. columns) for these 4 columns
(resp.rows).
We call such structures collectively "S Locked Sets" or S-LS.
Remarks:
1) we don't have to consider subsets of size > 4.
2) in compliance with my general view of symmetry and
super-symmetry, I make no fundamental distinction between ALS
(Almost Locked Sets), AHS (or H-ALS, Hidden Almost Locked Sets) and
SH-ALS (Super-Hidden ALS, Almost-Fish - I don't know if these are
currently used in AICSs), although the definitions I've given here
don't explicit these symmetries (they could be made explicit by
systematically using the rc-, rn-, cn- and bn- spaces).
3) the number of additional candidates (nrc-linked to S) in any of
the (rc-, rn-, cn- or bn-) cells of any of these patterns is totally
irrelevant.
One can also define a candidate nrc-linked to an S-LS: it is any
candidate that could be standardly eliminated by the underlying LS.
Definition: given a target
candidate z, a zt-whip(LS)
built on z is any sequence L1 R1 L2 R2 L3 R3 .... Ln of elements
alternatively called left-linking and right-linking, where
- L1, L2 ... Ln are candidates, (as usual, it is not necessary to
extend the possibilities on left-linking candidates),
- each of R1, R2, R3 ... Rn-1 is a Locked Set modulo the target and
the previous right-linking candidates,
- L1 is nrc-linked to the target,
- for each 1 < k <= n, Lk is nrc-linked to Rk-1 (in the above
extended sense of "nrc-linked)"; this is the first part of the whip
condition,
- for each 1 <= k < n, Lk is nrc-linked to at least one
element of one of the rc- (resp. rn-, cn- or bn-) cells containing
Rk; this is the second part of the whip condition,
- there is an rc-, rn-, cn- or bn- cell containing Ln such that
there is no candidate in this cell compatible with the target and
the previous right-linking elements.
zt-whips(LS) are an obvious common generalisation of nrczt-whips and
of AICs
(except that they rely only on real candidates, not on ghosts, i.e.
on re-using candidates already eliminated - a misleading idea that
would introduce much useless complexity).
As usual, we have the corresponding
zt-whip(LS) elimination theorem:
given a zt-whip(LS), one can eliminate its target.
the proof of which is obvious, following the same pattern as usual:
if the target was true, then all the left-linking candidates would
be false and all the right-linking ones would be true.
The only difference is that we need to say what being true means for
a Subset-candidate: it merely means that the n-candidates of the
n-cells are globally true for these n cells, which leaves no
possibility of being true for the next llc.
1.3) Combining hinges and locked
sets: hinged-zt-whips(LS)
We can now define a hinged-zt-whip(LS) in the same vein as a
zt-whip(LS), by allowing a right-linking candidate to be either as
in a zt-whip(LS) or a segment-candidate.
As usual, we have the corresponding:
hinged-zt-whip(LS) elimination
theorem: given a hinged-zt-whip(LS), on can eliminate its target.
the proof of which is obvious, as above.
2.2) ZT-WHIPS(FP)
Let's go one step further.
Definition: If P is any elementary pattern (e.g. BI, Pairs, Fish,
..., as in the pevious cases, or any new pattern), with an
associated resolution rule R, a candidate C is nrc-linked to P if it satisfies the conditions
of the elimination of a target for rule R.
If S is a set of candidates, one can define as previously being a
pattern in the FP family modulo S.
Given any family FP of elementary patterns, one can define a
zt-whip(FP).
Definition: given a target
candidate z, a zt-whip(FP)
built on z is any sequence L1 R1 L2 R2 L3 R3 .... Ln (notice that
there is no Rn) of elements alternatively called left-linking and
right-linking, such that:
- L1, L2 ... Ln are candidates, (as usual, it is not necessary to
extend the possibilities on left-linking candidates),
- each of R1, R2, R3 ... Rn-1 is a candidate or a pattern from the
FP family modulo the target and the previous right-linking elements,
- L1 is nrc-linked to the target,
- for each 1 < k <= n: Lk is nrc-linked to Rk-1 (in the above
extended sense of "nrc-linked)"; this is the first part of the whip
condition,
- for each 1 <= k < n, there is a set of candidates R'k
containing those in Rk, such that Lk is nrc-linked to at least one
of those in R'k-Rk and the set of candidates in R'k-Rk compatible
with the target and the previous right-liking elements is equal to
Rk; this is the second part of the whip condition,
- there is an rc-, rn-, cn- or bn- cell containing Ln such that
there is no candidate in this cell compatible with the target and
the previous right-linking elements.
zt-whip(FP) elimination theorem:
given a zt-whip(FP), one can eliminate its target.
zt-whips(FP) are a means of allowing some very restricted from of
branching within a whip - the kind of branching that is limited to
the inside of a pattern in the FP family.
2.3) HOW TO FIND COMPLEX
WHIPS?
A word is in order on how to find these generalised whips.
As for any other pattern, nothing can replace "practice".
But, as for the chains and whips previously introduced, there are
also five general recommendations:
1) look first for the 2D counterparts,
2) look for the nrc before the nrct before the nrczt,
3) look for short whips before longer ones,
4) when you have found a whip, try to find other ones by circular
permutation of the candidates,
5) use the composability property
of whips: this is a way of re-using partial
chains/whips/braids. Most whips have parts with no z- or t-
additional candidates and parts with t-candidates justified by
nearby right-linking candidates. Compose longer whips by assembling
such shorter ones before you look for whips with t-candidates
justified by right-linking candidates far away before them.
3) GENERALISED BRAIDS
This section is the transposition to braids of what was done to
whips in section 2.
3.1) HINGED-zt-BRAIDS,
zt-BRAIDS(LS) and HINGED-zt-BRAIDS(LS)
We can now define a hinged-zt-braid, a zt-braid(LS) or a
hinged-zt-braid(LS) in the same vein as a hinged-zt-whip, a
zt-whip(LS) or a hinged-zt-whip(LS), by allowing left-linking
candidates to be linked to the target or to any previous
right-linking object instead of just the previous right-linking
object.
As usual, we have the corresponding elimination theorems.
Let BI be the Basic Interaction rules.
Let SubsetRules be the set of resolution rules for (Naked, Hidden
and Super-Hidden) Singles, Pairs, Triplets and Quads.
It is obvious that any elimination done by a hinged-zt-braid could
be done by T&E(ECP+NS+HS+BI). The converse is true and more
interesting:
Theorem: Any elimination that can
be done by T&E(ECP+NS+HS+BI) can be done by a hinged-zt-braid.
It is obvious that any elimination done by a zt-LS-braid could be
done by T&E(SubsetRules). The converse is true and more
interesting:
Theorem: Any elimination that can
be done by T&E(SubsetRules) can be done by a zt-LS-braid.
It is obvious that any elimination done by a hinged-zt-LS-braid
could be done by T&E(SubsetRules + BI). The converse is true and
more interesting:
Theorem: Any elimination that can
be done by T&E(SubsetRules + BI) can be done by a
hinged-zt-LS-braid.
As for the basic nrczt-braids, these theorems allow an easier study
of the scope of these new braids (see below).
3.2) GENERAL ZT-BRAIDS(FP)
As for whips, let's go one step further.
Given any family FP of elementary patterns with associated
resolution rules, one can define a zt-braid(FP).
Definition: given a target candidate z, a zt-braid(FP) built on z is any sequence L1 R1 L2 R2
L3 R3 .... Ln of elements alternatively called left-linking and
right-linking, where
- L1, L2 ... Ln are candidates, (as usual, it is not necessary to
extend the possibilities on left-linking candidates),
- each of R1, R2, R3 ... Rn-1 is a pattern from the FP family modulo
the target and the previous right-linking elements,
- L1 is nrc-linked to the target,
- for each 1 < k <= n, Lk is nrc-linked to the target or to
some previous right-linking candidate (in the above extended sense
of "nrc-linked)"; this is the first part of the braid condition (and
the only difference with whips),
- for each 1 <= k < n, there is a set of candidates R'k
containing those in Rk, such that Lk is nrc-linked to at least one
of those in R'k-Rk and the set of candidates in R'k-Rk compatible
with the target and the previous right-linking elements is equal to
Rk; this is the second part of the braid condition,
- there is an rc-, rn-, cn- or bn- cell containing Ln such that
there is no candidate in this cell compatible with the target and
the previous right-linking elements.
As previously, if FP is a family of elementary patterns with
associated resolution rules:
- a zt-braid(FP) is a generalisation of a zt-whip(FP),
- one can define the procedure T&E(FP), T&E with no
guessing, based on the resolution rules of the patterns in FP,
- and we have the
zt-braid(FP) vs T&E(FP)
theorem: let FP be any family of elementary patterns with
associated resolution rules; then any elimination done by
T&E(FP) can be done by a zt-braid(FP).
The proof works exactly as for the simple nrczt-braids.
Such theorems could be used in a very practical way. Suppose you
want to build a puzzle that can't be solved with some predefined set
of chain rules CT based on a family FP of generating patterns. If
one knows that if a puzzle P is not in T&E(FP), it can't be
solved by CT. Of course, this is putting stronger constraints than
needed on P (not solvable by braids instead of not solvable by
chains). But checking that P is not in T&E(FP) is much faster
than checking that it isn't in CT.
As a player, you may also want to check if a puzzle has a chance of
being solvable by some set of techniques. You can do this with an
elementary T&E procedure.
Remark:
As for any chain, lasso or whip or
braid in the xy-to-nrczt family, the additional t- or z-
candidates are not part of the zt-braids(FP).
This is not an arbitrary convention; it has practical consequences:
if I notice a braid but I don't use it immediately (e.g. because
I've seen a shorter one), then, later, some z- or t- candidates may
have disappeared; if the left-linking and right-linking ones haven't
changed, this will still be the same braid. This is extensively used
in SudoRules.
3.3) THE SCOPE OF
ZT-BRAIDS(FP) FOR SOME FAMILIES FP OF GENERATING PATTERNS
The above theorem can be used to evaluate the scope of several types
of braids (which are also an upper boundary for the corresponding
whips).
Above, I mentioned that all the puzzles in a set of random
collections with a total of approximately 10,000,000 minimal puzzles
could be solved by T&E(ECP+NS+HS) or equivalently by
nrczt-braids (indeed, I also showed that they can be solved by
nrczt-whips).
As a result, puzzles that are not in the scope of nrczt-braids are
extremely rare and if we want to compare the scopes of several types
of more complex braids, we can only do this on a collection of
exceptionally hard puzzles.
The natural choice for this is gsf's colection of 8152 hardest.
The following results may help clarify through examples how the
above theorems lead to scope estimations.
They also shed some very unusual light on the top level of the
hierarchy, which, with respect to the various types of braids
considered here, appears to be drastically more homogeneous than
suggested by the Q1 rating on which gsf list is based.
Let BI be the Basic Interaction rules.
Let Subset2 be the set of resolution rules for (Naked, Hidden and
Super-Hidden) Pairs.
Let Subset3 be the set of resolution rules for (Naked, Hidden and
Super-Hidden) Triplets.
Let Subset4 be the set of resolution rules for (Naked, Hidden and
Super-Hidden) Quads.
Here, in conformance with my general approach respecting
super-symmetry, no difference has been made between Naked, Hidden or
Super-Hidden (i.e. Fish) subsets of the same size (although separate
computations could easily be done for each).
Let Finned be the family of finned fish of size 2, 3 or 4.
Finally, let x2y2 be the family of x2y2-belts, defined here. They are my interpretation of
Steve's pattern (also known as SK-loop or hidden-pairs loop).
In the following table, the first column defines the sets of puzzles
I consider: slices of 500 puzzles starting from the top of gsf's
list.
The following columns show how many puzzles of each slice can be
solved using the FP family of generating patterns mentioned in the
first row.
What's noticeable is that there is almost no difference for the
slices corresponding to puzzles with Q1 rating between 99408
(EasterMonster) and ~8800, after which there is a drastic change in
behaviour.
Nb of puzzles solved by different types of braids: each FP family of
generating patterns is eqal to the previous one plus those indicated
after the + sign.
Notice that all the final 1152 (and almost all the final 2152)
puzzles in the list can be solved by ordinary braids.
| FP family |
ECP+NS+HS
|
+BI
|
+Subset2 |
+Subset3 |
+Subset4 |
+Finned |
+x2y2
|
| 1-500 |
0 |
187 |
336 |
414 |
443 |
466 |
489 |
500-1000
|
0
|
178
|
335
|
415
|
460
|
480
|
497
|
1001-1500
|
0
|
163
|
382
|
451
|
486
|
494
|
500
|
1501-2000
|
0
|
168
|
397
|
476
|
490
|
496
|
499
|
2001-2500
|
0
|
135
|
367
|
434
|
474
|
489
|
497
|
| 2501-3000 |
0
|
116
|
334
|
443
|
479
|
493
|
499
|
3001-3500
|
1
|
120
|
335
|
424
|
473
|
486
|
498
|
3501-4000
|
0
|
113
|
325
|
426
|
472
|
493
|
499
|
4001-4500
|
1
|
104
|
298
|
395
|
448
|
471
|
497
|
4501-5000
|
0
|
231
|
399
|
450
|
482
|
494
|
499
|
5001-5500
|
47
|
348
|
487
|
500 |
500 |
500 |
500 |
5501-6000
|
434
|
490
|
500
|
500 |
500 |
500 |
500 |
6001-6500
|
487
|
500
|
500 |
500 |
500 |
500 |
500 |
6501-7000
|
494
|
500 |
500 |
500 |
500 |
500 |
500 |
7001-7500
|
500
|
500 |
500 |
500 |
500 |
500 |
500 |
7501-8000
|
500
|
500 |
500 |
500 |
500 |
500 |
500 |
8001-8152
|
152
|
152 |
152 |
152 |
152 |
152 |
152 |
Total
|
2616
|
4505
|
6647
|
7480
|
7859
|
8014
|
8126
|
Rest
|
5536
|
3647
|
1505
|
672
|
293
|
136
|
26
|
This table shows that almost all the hardest known puzzles can be
solved with braids built on subsets (Naked, Hidden and Fish) and on
x2y2-belts.
Almost all the known puzzles can be solved by braids(FP), with FP =
ECP+NS+HS+BISubsets+Finned+x2y2.
It shouldn't be too difficult to find some simple pattern that, when
added to FP, would allow to solve the remaining 26 puzzles.
As a comparaion of nrczt-whips with all the rules in Mike Barker's
solver (including all chains of ALSs) showed that they had
approximately the same coverage, these results illustrate the
advantages of the zt-ing principle over the almosting principle
(which is at the basis of ALS chains).
Home(The Hidden Logic of Sudoku)
Home(Denis
Berthier)