The Hidden Logic of Sudoku


Denis Berthier



book cover


Online Supplements


Subsumption theorems




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.


Given two resolution rules R1 (Pattern1 => Action1) and R2 (Pattern2 => Action2), we say that R2 subsumes R1 if R1 is a special case of R2. More precisely:
- Pattern2 is more general than Pattern1;
- when Pattern1 is satisfied,  Action2  is equivalent to Action1.




1) OBVIOUS SUBSUMPTION RELATIONSHIPS


nrc-chains subsume xy, hxy-rn and hxy-cn- chains plus Nice Loops (without subsets)
nrct-chains subsume nrc-chains, xyt-, xyt-rn- and cyt-cn- chains.
nrcz-chains subsume nrc-chains, xyz-, xyz-rn- and xyz-cn- chains
nrczt-chains subsume nrc-chains, xyzt-, xyzt-rn- and xyzt-cn- chains




2) BASIC INTERACTIONS


THEOREM: NRCZ-CHAINS OF LENGTH 1 SUBSUME BASIC INTERACTIONS

As the converse is obvious, we also have:

THEOREM: NRCZ-CHAINS OF LENGTH 1 ARE EQUIVALENT TO BASIC INTERACTIONS

Proof:

ROW INTERACTION WITH BLOCK (RiB):

First, the general pattern for a non-degenerate RiB (seen in standard rc-space) is:

XXXXXX-----11-----12----(13)
                        ?------?------?
                        ?------?------?

the rightmost 9 cells are in the same block,
11, 12, 13 designate occurrences of the target value under consideration,
the 6 X's indicate that the target value is not allowed in the 6 cells of the row outside the block,
parens indicate an optional candidate,
? indicates a possible place for the target (in the same block as 11 12 13),
Rows and columns within a block can be permuted.
Notice that at least two occurrences of the target value must occur in the row under consideration: otherwise, we'd have a Naked Single.


First case:

XXXXXX-----11-----12-----X
                        ?------?-----?
                        ?------?-----?

subsumed by NRC1: {11 12}


Second case:

XXXXXX-----11-----12----13
                         ?------?------?
                         ?------?------?

subsumed by NRCZ1 : {11 12 13#z}



BLOCK INTERACTION WITH ROW (BiR)

First, the general pattern for a non-degenerate RiB (seen in standard rc-space) is (with the same conventions as above); here the target (?) is in the same row as 11 12 13 and outside their common block:


X-------X------X
X-------X----- X
11-----12-----(13)-------------?-------



First case:

X-----X-----X
X-----X-----X
11----12----X-----------Z

subsumed by NRC1: {11 12}


Second case:

X------X------X
X------X------X
11----12------13---------Z

subsumed by NRCZ1: {11 12 13#z}


INTERACTIONS WITH COLUMNS
the result is obtained by rc symmetry.




3) NRCZT-CHAIN RULES SUBSUME "ALMOST ALL" NAKED, HIDDEN AND SUPER-HIDDEN SUBSET RULES



In my book and in several forums, I've already formulated several theorems about the subsumption of subset rules by nrczt-chain rules.
In the following three parts, I'll give further results, some logical and some statistical.

In the first part, I'll recall the exact subsumption theorems.
In the second part, I'll try to evaluate the practical scope of what, in the Naked, Hidden and Super-Hidden (fish) Subset rules, is not subsumed by nrczt-chains.
In the third part, I'll give a simple example.


PART 1) EXACT NRCZT SUBSUMPTION THEOREMS FOR SUBSET RULES

Notations:
P = Pairs
T= Triplets
Q = Quadruplets
N = Naked
H = Hidden
SH = Super-Hidden (Fish)
In patterns, numbers 1, 2, 3,... stand for variables: n1, n2, n3,... if in rc-space; c1, c2, ... if in rn-space,....

The N theorems are proven directly; using symmetry and super-symmetry, the H and SH corollaries are straightforward consequences.


Pairs:
Theorem: XY2 is equivalent to NP.
Corollary: NRC2 (and therefore also NRCZT2) subsumes NP, HP and SHP.



Triplets:
As proven in my book, the general pattern for a non-degenerate NT is: rc/- {1 2 (3)} - {2 3 (1)} - {3 1 (2)} (where the 2 links are the same unit).
Parens indicate optional candidates.

Consider a candidate 1 in a cell belonging to the unit of the triplet but not to the triplet itself (i.e. a candidate that can be eliminated by NT in this unit)
Using the # and * symbols for the t- and z- candidates, the above pattern becomes the nrczt3-chain based on the chosen candidate:
rc/- {1 2 (3)} - {2 3 (1*)} - {3 1 (2#1)},
provided that candidate 3 is absent from the first cell.

Theorem: XYZT3 eliminates any candidate 1 eliminated by a NT with pattern {1 2} - {2 3 (1)} - {3 1 (2)} (all links along the same unit)
Corollary: NRCZT3 eliminates any candidate 1 eliminated by a NT, HT or SHT with pattern {1 2} - {2 3 (1)} - {3 1 (2)} (all links along the same


Changing the order of the chain and/or renaming the candidates, if necessary, it appears that the only cases when we can't get an xyzt3-chain based on a candidate 1 eliminated by NT in the same unit correspond to the pattern {1 2 3} - {2 3 (1)} - {3 1 2)}
We thus get a better formulation:
Theorem: XYZT3 (and therefore also NRCZT3) eliminates any candidate eliminated by NT in a cell outside of the triplet provided that another of the 3 candidates in the triplet appears in only 2 cells of the triplet.
Theorem: HXYZT3(row) (and therefore also NRCZT3) eliminates any candidate eliminated by HT(row) in a cell of the hidden triplet provided that another of the 3 cells in the triplet doesn't contain one of the candidates in the triplet.
Theorem: SHXYZT3(row) (and therefore also NRCZT3) eliminates any candidate eliminated by Swordfish(row) in a column of the Swordfish outside of the 3 rows in the Swordfish provided that a cell of the Swordfish in one of the other 2 columns in the Swordfish doesn't contain the candidate of the Swordfish.



Quadruplets:
As proven in my book, the general pattern for a non-degenerate cyclic NQ is: rc/- {1 2 (3) (4)} - {2 3 (4) (1)} - {3 4 (1) (2)} - {4 1 (2) (3)} (where the 3 links are the same unit).

Consider a candidate 1 in a cell belonging to the unit of the quadruplet but not to the quadruplet itself (i.e. a candidate that can be eliminated by NQ in this unit)
As before, the above pattern becomes the nrczt4-chain based on the chosen candidate:
rc/- {1 2 (3) (4)} - {2 3 (4) (1*)} - {3 4 (1*) (2#1)} - {4 1 (2#1) (3#2)},
provided that candidates 3 and 4 are absent from the first cell and candidate 4 is absent from the second.

We thus get:
Theorem: XYZT4 eliminates any candidate 1 eliminated by a NQ with pattern {1 2} - {2 3 (1)} - {3 4 (1) (2)} - {4 1 (2) (3)} (all links along the same unit)
Corollary: NRCZT4 eliminates any candidate 1 eliminated by a NQ, HQ or SHQ with pattern {1 2} - {2 3 (1)} - {3 4 (1) (2)} - {4 1 (2) (3)} (all links along the same unit)

See below corresponding theorems for finned fish, sashimi or not.


PART 2) EXAMINING HOW NRCZT-CHAIN RULES COMPENSATE FOR THE NON SUBSUMED CASES OF NAKED, HIDDEN AND SUPER-HIDDEN SUBSET RULES

From the theorems in part 1, one can see that most of the eliminations allowed by naked, hidden and super-hidden subset rules can be done by corresponding nrczt-chains (of the same size).
But "most" still keeps a very vague meaning.
Using the Sudogen0 reference collection of 10,000 random minimal puzzles, I analysed what this means in practice.
For this purpose, I ran SudoRules with all the rules turned off, except ECP, NS, HS and nrczt chains and lassos of any length, on the full Sudogen0 collection. (Remember that basic interaction rules are subsumed by NRCZ1).

Results:
- all the puzzles in Sudogen0 are still solved by this epurated version of SudoRules;
- all these puzzles are solved with chains of the same maximal length as in the full SudoRules, except:
# 220, 1239, 6420, 6580, 8693, 8701, 9514 need chains of length 4 instead of 3
# 1222 needs chains of length 5 instead of 3

Notice the meaning of "compensate" in the title. It doesn't mean that any subset is repalced by a corresponding chain but that there appears to be some opportune, maybe unrelated, chain(s) that do the same elimination work. In the few cases for which the level is changed, we can be sure that there is no related chain and they are cases of exceptional subset patterns.

Although this is not a formal proof, it may help understand why almost any puzzle solved using AICs with ALSs can also be solved using only nrczt-chains: nrczt-chains formally subsume the most common cases of AICs with ALSs (same proof as for pure subset rules) and they compensate for almost all of the other cases in practice.
(We already know that nrczt-chains also subsume hinges).


PART 3) EXAMPLE

Consider puzzle Sudogen0 #220
.4..72.6.
.......9.
.7.49.5..
796..1.5.
.1....8..
..3...6..
9........
6..134...
...9....8

If we allow subset rules, we get:

***** SudoRules version 13 *****
.4..72.6........9..7.49.5..796..1.5..1....8....3...6..9........6..134......9....8
;;; start common part
hidden singles ==> r1c3 = 9, r3c6 = 6, r2c2 = 6, r9c5 = 6, r5c4 = 6, r7c9 = 6, r8c9 = 5, r8c7 = 9, r2c5 = 1, r3c8 = 8
.49.72.6.
.6..1..9.
.7.49658.
796..1.5.
.1.6..8..
..3...6..
9.......6
6..1349.5
...96...8
interaction row r8 with block b7 for number 8 ==> r7c3 <> 8, r7c2 <> 8
interaction row r4 with block b5 for number 8 ==> r6c6 <> 8, r6c5 <> 8, r6c4 <> 8
interaction column c2 with block b7 for number 3 ==> r9c1 <> 3
interaction block b8 with row r7 for number 2 ==> r7c8 <> 2, r7c7 <> 2, r7c3 <> 2, r7c2 <> 2
;;; end common part

naked-pairs-in-a-row {n1 n3}r1{c7 c9} ==> r1c4 <> 3
interaction block b2 with row r2 for number 3 ==> r2c9 <> 3, r2c7 <> 3, r2c1 <> 3
naked-pairs-in-a-row {n1 n3}r1{c7 c9} ==> r1c1 <> 3
hidden-single-in-a-block ==> r3c1 = 3
naked-pairs-in-a-row {n1 n3}r1{c7 c9} ==> r1c1 <> 1
naked and hidden singles ==> r3c3 = 1, r3c9 = 2, r9c1 = 1
interaction column c1 with block b4 for number 4 ==> r5c3 <> 4
;;; at this point, the decided values are:
.49.72.6.
.6..1..9.
371496582
796..1.5.
.1.6..8..
..3...6..
9.......6
6..1349.5
1..96...8
;;; end equivalent parts

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; restrictive naked triplets (we can check that we have all 3 values in all 3 cells):
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
naked-triplets-in-a-row {n4 n5 n2}r5{c1 c3 c5} ==> r5c9 <> 4
naked-triplets-in-a-row {n4 n5 n2}r5{c1 c3 c5} ==> r5c8 <> 4 ;;; this elimination can't be done by any equivalent nrczt3-chain
naked-triplets-in-a-row {n4 n5 n2}r5{c1 c3 c5} ==> r5c8 <> 2
naked-triplets-in-a-row {n4 n5 n2}r5{c1 c3 c5} ==> r5c6 <> 5
xy3-chain {n7 n4}r2c9 - {n4 n3}r4c9 - {n3 n7}r5c8 ==> r6c9 <> 7, r5c9 <> 7
naked and hidden singles ==> r2c9 = 7, r2c7 = 4
interaction column c7 with block b9 for number 7 ==> r9c8 <> 7, r8c8 <> 7
naked and hidden singles ==> r8c8 = 2, r8c2 = 8, r8c3 = 7, r6c1 = 8, r1c1 = 5, r2c1 = 2, r5c1 = 4, r2c3 = 8, r1c4 = 8, r4c5 = 8, r7c6 = 8, r6c5 = 4, r4c9 = 4, r4c7 = 2, r4c4 = 3, r2c4 = 5, r2c6 = 3
interaction column c7 with block b9 for number 7 ==> r7c8 <> 7
nrc2-chain n5{r9c6 r7c5} - n5{r5c5 r5c3} ==> r9c3 <> 5
x-wing-in-columns n5{r5 r7}{c3 c5} ==> r7c2 <> 5
naked-single ==> r7c2 = 3
nrc3-chain n7{r7c4 r7c7} - n1{r7c7 r7c8} - {n1 n7}r6c8 ==> r6c4 <> 7
naked singles
GRID 220 SOLVED. LEVEL = L3, MOST COMPLEX RULE = NRC3
549872361
268513497
371496582
796381254
412659873
853247619
935728146
687134925
124965738


Without subset rules
(solve-nth-grid-from-text-file (str-cat ?*PuzzlesDir* "Sudogen/sudogen0.txt") 220)
***** SudoRules version 13 *****
.4..72.6........9..7.49.5..796..1.5..1....8....3...6..9........6..134......9....8
;;; start common part
hidden singles ==> r1c3 = 9, r3c6 = 6, r2c2 = 6, r9c5 = 6, r5c4 = 6, r7c9 = 6, r8c9 = 5, r8c7 = 9, r2c5 = 1, r3c8 = 8
.49.72.6.
.6..1..9.
.7.49658.
796..1.5.
.1.6..8..
..3...6..
9.......6
6..1349.5
...96...8
interaction row r8 with block b7 for number 8 ==> r7c3 <> 8, r7c2 <> 8
interaction row r4 with block b5 for number 8 ==> r6c6 <> 8, r6c5 <> 8, r6c4 <> 8
interaction column c2 with block b7 for number 3 ==> r9c1 <> 3
interaction block b8 with row r7 for number 2 ==> r7c8 <> 2, r7c7 <> 2, r7c3 <> 2, r7c2 <> 2
;;; end common part

nrczt2-chain n5{r1c1 r1c4} - n8{r1c4 r1c1} ==> r1c1 <> 1
interaction row r1 with block b3 for number 1 ==> r3c9 <> 1
nrczt2-chain n5{r1c1 r1c4} - n8{r1c4 r1c1} ==> r1c1 <> 3
nrczt2-chain n5{r1c4 r1c1} - n8{r1c1 r1c4} ==> r1c4 <> 3
interaction row r1 with block b3 for number 3 ==> r3c9 <> 3
naked and hidden singles ==> r3c9 = 2, r3c3 = 1, r3c1 = 3, r9c1 = 1
interaction column c1 with block b4 for number 4 ==> r5c3 <> 4
interaction row r1 with block b3 for number 3 ==> r2c9 <> 3, r2c7 <> 3
;;; end equivalent parts
;;; notice that, although the state can easily be checked to be the same as above, the resolution path is different: the naked pairs haven't been replaced by equivalent nrczt2 chains (but they could have); this is because there are many resolution paths and which one is chosen by SudoRules can't be guaranteed.

nrczt3-chain n1{r6c8 r6c9} - {n1 n3}r1c9 - {n3 n4}r4c9 ==> r6c8 <> 4
nrczt3-chain n5{r6c5 r7c5} - n2{r7c5 r7c4} - n7{r7c4 r6c4} ==> r6c4 <> 5
nrczt3-chain n9{r5c9 r5c6} - n3{r5c6 r5c8} - n7{r5c8 r5c9} ==> r5c9 <> 4
nrczt3-lr-lasso n9{r5c6 r5c9} - n3{r5c9 r5c8} - n7{r5c8 r5c9} ==> r5c6 <> 5
nrczt3-lr-lasso {n2 n5}r5c3 - {n5 n4}r5c1 - {n4 n5}r5c5 ==> r5c8 <> 2
nrczt4-lr-lasso {n4 n3}r4c9 - n3{r5c9 r5c6} - n7{r5c6 r5c9} - n9{r5c9 r5c6} ==> r5c8 <> 4 ;;; instead of triplet rule above
interaction column c8 with block b9 for number 4 ==> r9c7 <> 4
interaction column c8 with block b9 for number 4 ==> r7c7 <> 4
nrczt3-lr-lasso {n4 n3}r4c9 - {n3 n7}r5c8 - n7{r6c9 r5c9} ==> r2c9 <> 4
naked singles ==> r2c9 = 7, r2c7 = 4
interaction column c7 with block b9 for number 7 ==> r9c8 <> 7, r8c8 <> 7
naked and hidden singles ==> r8c8 = 2, r8c2 = 8, r8c3 = 7, r6c1 = 8, r1c1 = 5, r2c1 = 2, r5c1 = 4, r2c3 = 8, r1c4 = 8, r4c5 = 8, r7c6 = 8, r6c5 = 4, r4c9 = 4, r4c7 = 2, r4c4 = 3, r2c4 = 5, r2c6 = 3
interaction column c7 with block b9 for number 7 ==> r7c8 <> 7
nrczt2-chain n5{r5c3 r5c5} - n5{r7c5 r9c6} ==> r9c3 <> 5
nrczt2-chain n5{r6c2 r6c6} - n5{r9c6 r9c2} ==> r7c2 <> 5
naked-single ==> r7c2 = 3
nrczt3-chain n1{r7c7 r7c8} - {n1 n7}r6c8 - n7{r6c4 r7c4} ==> r7c7 <> 7
naked-singles
GRID 220 SOLVED. LEVEL = L4, MOST COMPLEX RULE = NRCZT4
549872361
268513497
371496582
796381254
412659873
853247619
935728146
687134925
124965738





4) SUBSUMPTION RELATIONSHIPS FOR FINNED AND SASHIMI FISH



Theorem: Most cases of finned and sashimi fish are subsumed by nrcz-chains.


1) x-wing:

Theorem: Any finned x-wing,  sashimi or not, is subsumed by an nrcz-chain of length 2.

Preliminaries: standard x-wing on rows is the following special case of nrc-chains: n1{r1c2 r1c1} - n1{r2c1 r2c2}, where:
- the two nrc-conjugate links are along rows r1 and r2,
- the mere central nrc-link is along column c1,
- the targets are considered as linked to both endpoints of this chain along column c2;
(Notice that, for the eliminations on column c1, chain n1{r1c1 r1c2} - n1{r2c2 r2c1} must be considered instead.)

Proof for finned fish: In the corresponding finned fish, additional candidate n1 may appear in the same row and block as the last candidate (n1r2c2) of this chain. But, any candidate n1rc such that rc is in the intersection of the column and the block containing the last candidate, makes the n1{r1c2 r1c1} - n1{r2c1 r2c2} chain into an nrcz-chain wrt the target n1rc, and the additional candidates on row r2 are exactly what the z-extension allows to disregard.

Proof for sashimi fish: In the corresponding sashimi fish, additional candidate n1 may appear in the same row and block as the last candidate (n1r2c2) of this chain and candidate n1 may be absent from r2c2. But, any candidate n1rc such that rc is in the intersection of the column and the block containing the last candidate, still makes the n1{r1c2 r1c1} - n1{r2c1 r2c2} chain into an nrcz-chain wrt the target n1rc, and the additional candidates on row r2 are exactly what the z-extension allows to disregard.


2) Swordfish

After re-ordering of the rows and columns, the most general cyclic Swordfish on rows for number n1 looks like:

..1a === 1b === (1c)
(1d) === 1e === 1f
..1g == (1h) === 1i
===========1x

where (1c), (1d) and (1h) are optional and 1x is a target in the same column as 1i

The most general cyclic Swordfish on rows for number n1, with fin (and sashimi), looks like:

..1a === 1b === (1c)
(1d) === 1e === 1f
..1g == (1h) === [1i] === 1fin
===========1x

1+ is a candidate in the fin
1fin is any candidate in the fin
[1i] is the potentially missing candidate in the sashimi
1x is a target in column and block of the last candidate: [1i]

Consider the chain 1f-1e-1b-1a-1g-(1i if present, 1fin otherwise). It is an nrczt-chain wrt 1x, If 1d is absent.

- additional candidates 1c and 1fin (if present) are justified by the z extension
- additional candidate 1h i(if present) s justified by the t extension

Theorem: Any 2x2x2 finned swordfish with or without sashimi is subsumed by an nrcz3-chain.
Theorem: Any other finned swordfish with or without sashimi is subsumed by an nrczt3-chain, provided that it has a missing candidate in a row and a column different from that of the base for the fin/sashimi.



3) Jellyfish

After re-ordering of the rows and columns, the most general cyclic Jellyfish on rows for number n1 looks like:

..1a === 1b === (1c) == (1d)
(1e) === 1f ==== 1g == (1h)
(1i) === (1j) === 1k === 1l
1m === (1n) == (1o) == 1p
==================1x
with similar conventions.


The most general cyclic Jellyfish on rows for number n1, with fin (and sashimi), looks like:
..1a === 1b === (1c) == (1d)
(1e) === 1f ==== 1g == (1h)
(1i) === (1j) === 1k === 1l
1m === (1n) == (1o) == [1p] === 1fin
==================1x

Consider the chain: 1l-1k-1g--1f-1b-1a-1m-(1p if present, 1fin otherwise). It is an nrczt-chain if 1e, 1i and 1j are absent:
- additional candidates 1d, 1h and 1fin (if present) are justified by the Z extension
- additional candidates 1c, 1n and 1o (if present) are justified by the t-extension

Theorem: Any 2x2x2x2 finned cyclic jellyfish with or without sashimi is subsumed by an nrcz4-chain.
Theorem: Any other finned cyclic jellyfish with or without sashimi is subsumed by an nrczt4-chain, provided that it has:
- a row different from that of the fin/sashimi base with a missing candidate in a column different from that of the fin/sashimi base
- another row different from that of the fin/sashimi base with a missing candidate in the previous column and a missing candidate in another column also different from that of the fin/sashimi base.




5) NRCZ CHAINS SUBSUME BROKEN WINGS



Broken Wings were defined by Rod Hagglund (here: http://www.sudoku.com/boards/viewtopic.php?t=2666&highlight=)
The logic they invoke for justifying the eliminations t very different from the logic of the nrczt-chain rules. Nevertheless, we have:
 
Theorem: nrcz-chains subsume broken wings.

What RodHaggund calls guardian cells can be understood as mere additional z-candidates.
There's no need of the t-extension.

Even without the t-extension, nrcz-chains are much more general than broken wings:
- there's no need for a closed loop
- there no need for all links to be conjugacy links (modulo the guardians): the constraint bears only on even links;
- the length can be odd or even, no matter (this is a consequence of the previous point);
- the number of additional z-candidates in any link is completely irrelevant.



Home(The Hidden Logic of Sudoku)         Home(Denis Berthier)