FULLY SUPERSYMMETRIC CHAINS
3D-CHAINS: NRC-, NRCT-, NRCZ- AND NRCZT- CHAINS
Until now, apart from c-chains, all the chains I have considered were defined and could be spotted as (pure or extended) xy-chains in either of the two dimensional rc-, rn- or cn- spaces. Surprisingly, this was enough to solve 97% of the randomly generated puzzles.
Nevertheless, for the remaining puzzles, some way of "knitting" through the two dimensional spaces is needed. c-chains are the simplest example of such a knitting. This post introduces more general three dimensional (3D) chains, which are the 3D analogues of the two dimensional xy-, xyt- and xyzt- chains.
The general idea remains the same: the presence of any candidate that is already ruled out by previous cells in the chain (or by the target cell) can be forgotten as an additional candidate whenever convenient (but it can still be used as a left linking candidate for the next cells). In order to use this idea in the 3D view, we just have to slightly adapt its formulation.
GENERAL 3D-CHAINS
3D-chains are also defined in the thread on the NRC notation (the notation which will be used here). Let me repeat the definitions here.
The basic notion underlying the 3D-chains is that of an nrc-link.
Definition: two candidates n1r1c1 and n2r2c2 are nrc-linked if they are different and:
- either n1=n2 and the two rc-cells (r1, c1) and (r2, c2) are rc-linked (i.e. share a unit) in rc-space,
- or n1 <> n2 and the rc-cells (r1, c1) and (r2, c2) are the same
Being nrc-linked is the most general, fully super-symmetric, support for the immediate detection of a contradiction between two nrc-candidates. It is quasi "physical" in the sense that it depends only on the grid structure. In particular, it does not depend on the truth value of these candidates. (Of course, if one of the candidates is true the other must be false, but this is how we use the link, not its factual definition).
An nrc-link is written as "—".
Definition: a 3D-chain is a sequence of candidates, such that the first and the last candidates in the sequence are different (there is no global loop) and any two consecutive candidates are nrc-linked.
Notice that global loops are excluded by definition, but not internal loops. Internal loops can be shown to be useless only for some types of chains (e.g. in 2D: xy-, hxy-, c-).
Definition: a target of a 3D-chain is a candidate that does not belong to the 3D-chain and that is nrc-linked to both endpoints of the 3D-chain.
Notice that, in conformance with the approach adopted in my book, targets never belong to the chain. This allows to define specific types of chains with homogeneous patterns and this provides for the possibility of several targets for the same chain.
Of course, interesting 3D-chains (i.e. 3D-chains that allow eliminations) will impose additional conditions. For examples, see the thread on nrc-, nrct-, nrcz- and nrczt- chains.
Basically, these conditions will allow to group adjacent candidates that are related by stronger links than mere nrc-links.
NRC-CHAINS
Definition: two candidates n1r1c1 and n2r2c2 are nrc-conjugate if they are nrc-linked and:
- either n1 <> n2, (r1, c1) and (r2, c2) are the same rc-cell, and the only candidates for this cell are n1 and n2 - i.e. cell (r1, c1) is bivalue,
- or n1=n2, (r1, c1) and (r2, c2) are different rc-cells, and there is a row, a column or a block along which (r1, c1) and (r2, c2) are conjugate for n1 – i.e. in which n1 is a candidate for only these two cells.
nrc-conjugate is the most general, fully super-symmetric, synthesis of the bivalue property of cells and conjugacy property of candidates in rc-space.
Definition: an nrc-chain is a 3D-chain of even length 2n such that, for any odd k with 1 <= k <= n, n(2k-1)r(2k-1)c(2k-1) and n(2k)r(2k)c(2k) are nrc-conjugate.
Here parentheses stand for subscripts, because I can't write subscripts with the software of this forum.
Two nrc-conjugate candidates will be represented by the pattern {n1r1c1 n2r2c2}
An nrc-chain (of length 6) can be represented by the pattern:
{1 2} — {3 4} — {5 6}
where the curly braces indicate the nrc-conjugacy relation.
Theorem (nrc-chain rule): given an nrc-chain, any target candidate can be eliminated.
NRCT-CHAINS
Definition: given a set S of candidates, two candidates n1r1c1 and n2r2c2 are nrc-conjugate modulo S if they do not belong to S, they are nrc-linked and:
- either n1 <> n2, (r1, c1) and (r2, c2) are the same rc-cell, and the only candidates for this cell are n1, n2 and possibly any other value n such that (n, r2, c2) is nrc-linked to an element of S,
- or n1=n2, (r1, c1) and (r2, c2) are different rc-cells, and there is a row, a column or a block along which (r1, c1) and (r2, c2) are conjugate for n2 modulo S – i.e. in which n2 is a candidate only for these two cells and possibly for any other cell (r, c) such that n1rc is nrc-linked to an element of S.
Definition: an nrct-chain is a 3D-chain of even length 2n such that, for any odd k with 1 <= 2k <= n, n(2k-1)r(2k-1)c(2k-1) and n(2k)r(2k)c(2k) are nrc-conjugate modulo the set of previous even nrc-cells of the chain.
An nrct-chain (of length 6) can be represented by the pattern:
{1 2} — {3 4} — {5 6 (2#2)}
where the curly braces indicate the nrc-conjugacy relation and the (2#2) indicates a optional conditional candidate.
Theorem (nrct-chain rule): given an nrct-chain, any target candidate can be eliminated.
NRCZ-CHAINS
Definition: given a candidate C, an nrcz-chain built on C is a 3D-chain of even length 2n such that:
- for any odd k with 1 <= k <= n, n(2k-1)r(2k-1)c(2k-1) and n(2k)r(2k)c(2k) are nrc-conjugate modulo C,
- C is nrc-linked to both endpoints of the chain - C is thus the (nrcz-) target of the nrcz-chain.
Theorem (nrcz-chain rule): given an nrcz-chain, its target candidate can be eliminated.
NRCZT-CHAINS
Definition: given a candidate C, an nrczt-chain built on C is a 3D-chain of even length 2n such that:
- for any odd k with 1 <= k <= n, n(2k-1)r(2k-1)c(2k-1) and n(2k)r(2k)c(2k) are nrc-conjugate modulo the set consisting of C plus the previous even nrc-cells of the chain,
- C is nrc-linked to both endpoints of the chain - C is thus the (nrczt-) target of the nrczt-chain.
An nrczt-chain (of length 6) can be represented by the pattern:
{1 2 (*)} — {3 4 (*)} — {5 6 (2#2)}
where (*) indicates an optional candidate conditioned by its having an nrc-link with the target.
Theorem (nrczt-chain rule): given an nrczt-chain, its target candidate can be eliminated.
PROOFS OF THE NRC-, NRCT-, NRCZ AND NRCZT- CHAIN RULES
The proofs of the nrc- and nrct-, nrcz- and nrczt- chain rules follow the same general pattern, which is the adaptation to 3D-space of the proofs for the xy-, xyt-, xyz- and xyzt- chain rules: in any of these chains, if the first candidate is false, then all the even candidates must be true. This can easily be proven by recursion on the length of the chain.
The application to the chain rules themselves is straightforward. For any target cell C, if the first candidate is true, then the target candidate must be false; and if the first candidate is false, then the last is true, and the target candidate must be false.
In the case of nrcz- and nrczt- chains, the target cell has to be included in the proof itself. Apart from this, the rest of the proof goes along the same lines as for xyt-chains.
As I already indicated, what is difficult for these chains is not proving the validity of the associated chain rules, it is
- for the theoretician, establishing the proper definiton in their full generality,
- for the player, spotting the actual chains on an actual grid.
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
All of the above definitions can straightforwardly be extended to AICs, which should be called in the above approach nrc chains of subsets. We can thus get AICt and AICzt chains. These have not been included in SudoRules 13.
NRC(Z)(T) COLOURING
To the nrc(z)(t)-chain resolution rules can be associated resolution techniques (see the thread on this distinction, here: http://forum.enjoysudoku.com/viewtopic.php?t=5600)
The first obvious technique consists of drawing arrows from each candidate to the next one in the underlying 3D chain.
The second technique is based on colouring. Inspired by xyt-chains, John Mac Leod has devised an xyt-colouring scheme, which I re-formulated as follows:
"Build the chain from first to last candidate, starting with the first two. Colour in blue the even candidates (corresponding to sources of nrc-links). Then:
You still build the chain from head to tail, starting with the same two cells as above. Colour in blue their right linking candidates. Then:
- when looking for the next cell, search among those that are linked to the last and contain its right linking candidate, forgetting the presence as an extra candidate (but not as a potential right linking candidate) of any candidate that is nrc-linked to the same number already coloured in blue,
- colour in blue the right linking candidate of the cell you have just added to the chain."
This colouring scheme can easily be adapted to nrc(z)(t) chains.
EXTENSION: AICT AND AICZT
All of the above can straightforwardly be extended to AICs, what should be called in the above approach nrc chains of subsets.
RESULTS
The nrc-, nrct- and nrczt- chains have been included in the new version of SudoRules (version 13).
SudoRules 13 can solve all but one (for which it meets a memory overflow problem) of the 10,000 randomly generated puzzles in the Sudogen0 collection.
This is noticeable, since SudoRules 13 has no rule for subsets (no Hinges, no Almost Locked Sets,…) and no rule for Uniqueness.
SudoRules 13 can also solve 24 out of the first 30 puzzles in Ruud’s top10000.
Among the other puzzles that cannot be solved with only the rules described here:
- EasterMonster (BTW, has any solution been published - I mean without T&E)?
EXAMPLES
As a first simple example of nrc-chains, let me take the puzzle used by Ron Hagglund in the thread where he introduced the hinge pattern (Sudoku UK forum/ Eureka, December 25, 2005 - 11:52 pm). This will show how (at least) some hinges can be replaced by xy(z)(t) chains.
My new NRC notation of chains is used.
604352970
002470036
370690002
429536187
751284369
863719200
200160093
100040620
006020700
- Code: Select all
number 8 : column C4 interaction with block B8
==> 8 eliminated from the candidates for R9C6
number 8 : column C4 interaction with block B8
==> 8 eliminated from the candidates for R8C6
number 8 : column C4 interaction with block B8
==> 8 eliminated from the candidates for R7C6
nrc3-chain N1R9{C8 C9} - {N1 N8}R1C9 - {N8 N5}R8C9
==> 5 eliminated from the candidates for R9C8
nrc3-chain {N8 N9}R9C4 - N9R8{C4 C2} - N3{R8 R9}C2
==> 8 eliminated from the candidates for R9C2
nrc3-chain {N9 N5}R9C1 - {N5 N3}R9C6 - N3{R9 R8}C2
==> 9 eliminated from the candidates for R8C2
number 9 : hidden-single-in-row R8 ==> R8C4 = 9
number 8 : naked-single ==> R9C4 = 8
nrc2-chain N8R1{C2 C9} - N8{R8 R7}C9
==> 8 eliminated from the candidates for R7C2
number 4 : naked-single ==> R7C2 = 4
number 4 : hidden-single-in-column C7 ==> R3C7 = 4
numbers 5 and 8 : naked-pairs-in-block B9: R7C7-R8C9
==> 5 eliminated from the candidates for R9C9
number 1 : xy-wing on cells R1C2*, R3C3 and R3C8* with numbers 1, 8 and 5
==> 1 eliminated from the candidates for R1C9
…(Naked Singles)…
614352978
982471536
375698412
429536187
751284369
863719254
247165893
138947625
596823741
For a more complex example, with nrc-, nrct- and nrczt- chains, see the thread "Ruud's10K Problem #66" (indeed #663)
edited 08/17/07 : changed the title of the thread
edited 07/24/08 : added the following:
There is a question about the first cell of an nrcz(t) chain that I haven't answered correctly in the first posts of this thread: has the first cell to be bivalue or conjugate? I answered yes, but this is incorrect. As the pattern I gave for the nrczt6 chains ({1 2 (*)} — {3 4 (*)} — {5 6 (2#2)}) shows, there can be additional z-candidates in the first cell.
It is easy to give an example of such a situation: consider candidates in row 1 and block 1:
C1=n1r1c1, C2 = n1r1c9, additional z candidates: n1r1c2 and n1r1c3, no other n1 candidate in row1
target = n1r3c2
Surprisingly, allowing this possibility doesn't seem to lead to the solution of more puzzles than disallowing it (but it may allow solutions with shorter chains) - this remark is based on an analysis of the 10.000 puzzles in Sudogen0. In the current version of SudoRules (version 13), this is allowed.
