The Hidden Logic of Sudoku


Denis Berthier



book cover


Online Supplements


The zt-ing principle




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.


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)