Mirrored from **Sudopedia**, the Free Sudoku Reference Guide

ORIENTED 3D-CHAINS: NRC-, NRCT-, NRCZ- AND NRCZT- CHAINS

1) NRC-LINKS and GENERAL 3D-CHAINS

The basic notion underlying all 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; i.e. are in the same row, column or block) in rc-space,

- or n1 <> n2 and the rc-cells (r1, c1) and (r2, c2) are the same.

Remarks:

- 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).

In the nrc-notation, 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 (those that do not contain the t extension, i.e. nrc and nrcz).

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 this approach, 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, such as nrc-, nrct-, nrcz- and nrczt- chains) will impose additional conditions. Basically, these conditions will allow to group adjacent candidates that are related by stronger links than mere nrc-links.

2) NRC-CONJUGACY and 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.

Remarks:

- "nrc-conjugate" is the most general, fully super-symmetric, synthesis of the bivalue property of cells and the conjugacy property of candidates in rc-space;

- "nrc-conjugate" is equivalent to"bivalue in either of the rc-, rn-, cn or bn- 2D spaces".

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).

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 and numbers stand for the indices of the candidates.

In an nrc-chain, candidates can be grouped by 2 and an nrc-chain can be seen as a chain of cells in varying 2D-spaces.

Odd candidates are therefore called left-linking candidates and even candidates are called right-linking candidates. (These definitions anso apply to the following types of chains).

This shows that the (supposedly) conflicting views of chains as chains of cells versus chains of candidates can be reconciled when supersymmetry is properly taken into account.

Theorem (nrc-chain rule): given an nrc-chain, any target candidate can be eliminated.

3) NRC-CONJUGACY MODULO A SET OF CANDIDATES and 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 (2#2)} — {5 6 (2#2) (4#4)}

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.

4) 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.

5) 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-candidates in 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 (2#2) (*)} — {5 6 (2#2) (4#4)}

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.

6) 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 candidate 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.

7) NRCT- AND NRCZT- LASSOS

Once a partial nrct- or nrczt- chain has been built, it is normally ended on the right when its last right-linking candidate can be nrc-linked to a target. But there appears to be two other ways of getting a contradiction on the target.

Notice that the following remarks are not useful for nrc- or nrcz- chains, due to the no-loop theorems that can be proven for them (as for xy-chains).

The first case is when there is already somewhere in the partial chain a left-linking candidate C that might be taken as a right-linking candidate of a later part of the chain if loops had not been excluded. In this case, the target of the partial chain can be eliminated (for the same reason as usual: this situation leads to a contradiction).

Notice that, when this happens, the target can be eliminated but nothing can be said directly about C; this is because the part of the chain before C cannot be excised, due to the t-candidates it may be used to justify in further cells. We call this case an rl-lasso ("rl" because a right-linking candidate is equal to a previous left-linking candidate). (Notice that there is no full chain in this case and that a target of an rl-lasso does not have to be linked to the last candidate.)

The second case is when there is already somewhere in the chain a right-linking candidate C that might be taken as a left-linking candidate of a later part of the chain if loops had not been excluded. As in the previous case, the target can be eliminated (for the same reason and with the same other remarks applying). We call this case an lr-lasso ("lr" because a left-linking candidate is equal to a previous right-linking candidate). (Again, there is no full chain in this case and that a target of an lr-lasso does not have to be linked to the last candidate.)

8) SUBSUMPTION RELATIONSHIPS

nrc-chains subsume xy, hxy-rn and hxy-cn- chains plus basic Nice Loops or AICs (i.e. Nice Loops or AICs 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.

nrczt-chains subsume most types of fish.

nrcz-chains subsume Broken Wings.

nrcz-chains subsume the basic row or column interactions with blocks.

This page was last modified 05:28, 26 August 2008.