Fully supersymmetric chains

berthier · Posted: Fri Aug 17, 2007 9:43 am Post subject: Fully supersymmetric chains

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 are 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 n2D: 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 belongs to S.

Definition: an nrct-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 modulo the set of previous even candidates 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, that does not contain C and 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, that does not contain C and 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
nrc-chains subsume 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
nrc-chains subsume Nice Loops (without subsets)

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).
The first obvious technique consist 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 value) of any candidate that sees 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 top1000.

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

berthier · Posted: Fri Aug 17, 2007 9:47 am Post subject:

This should be part of the first post, but it seemed too lo,g for the software of this forum.

EXAMPLE

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 (see the thread describing it).

604352970
002470036
370690002
429536187
751284369
863719200
200160093
100040620
006020700