The NRC notation

berthier · Posted: Fri Aug 17, 2007 9:52 am Post subject: The NRC notation

THE NRC NOTATION

This thread is only about a new notation.
The nrc-, nrct-, nrcz- and nrczt- chains that are evoked several times here are defined in the "fully supersymmetric chains" thread, where they should be discussed.

1) INTRODUCTION AND JUSTIFICATION

In my book, "The Hidden Logic of Sudoku" (HLS), I have introduced various types of chains: xyt-, xyz-, xyzt- and their "hidden counterparts" in the rn- and cn- spaces.
In order to represent the associated patterns in all these spaces, I was able to use the same representation: e.g. the pattern {1 2} — {2 3} — {3 4} — {4 1} can represent an xy4, an hxy4-rn or an hxy4-cn chain, depending on the space where it is interpreted.
The three associated chain rules were thus written as:
rc /- *{1 2} — {2 3} — {3 4} — {4 1}* (rc was generally omitted, being the default)
rn /- *{1 2} — {2 3} — {3 4} — {4 1}*
cn /- *{1 2} — {2 3} — {3 4} — {4 1}*
where the * indicates the cells to which any target cell must be linked, and the numbers are shortcuts for variables in the remaining third dimension (respectively: n, c, r).
In this notation, I have adopted the convention that between the curly brackets, the first (respectively the second) variable is always the left (resp. the right) xy-linking variable. Additional variables, as may appear in xyt-, xyz-, xyzt- chains and their hidden counterparts are always written after these two.

When such a chain pattern is instantiated in a real chain of a real grid, it is convenient to write the real chain as follows.
For xy-chains:
- for an xy-chain (in rc-space):
{N1 N5}R7C5 — {N5 N3}R8C3 — {N3 N6}R9C3 — {N6 N1}R9C4, which eliminates e.g. N1R8C6.
- for an hxy-rn-chain (in rn-space):
N1R2{C2 C4} — N1R6{C4 C6} — N6R6{C6 C3} — N6R2{C3 C2}, which eliminates e.g. N3R2C2.
- for an hxy-cn-chain (in cn-space):
N7{R1 R5}C5 — N7{R5 R3}C3 — N9{R3 R6}C3 — N9{R6 R1}C2, which eliminates e.g. N9R1C5.
And for xyt-chains:
- for an xyt-chain in rc-space:
{N1 N5}R7C5 — {N5 N3}R8C3 — {N3 N6}R9C3 — {N6 N1 N5}R9C4, which eliminates e.g. N1R8C6. N5 is allowed in the last cell (R9C4) because it is linked (by a block) to the first (R7C5), where N5 appears as the right linking candidate.
- for an hxyt-chain in rn-space:
N1R2{C2 C4} — N1R6{C4 C6} — N6R6{C6 C3} — N6R2{C3 C2 C4}, which eliminates e.g. N3R2C2. C4 is allowed in the last cell (N6R2) because it is linked (by a row) to the first (N1R2), where C4 appears as the right linking candidate.
- for an hxyt-chain in cn-space:
N7{R1 R5}C5 — N7{R5 R3}C3 — N9{R3 R6}C3 — N9{R6 R1}C2, which eliminates e.g. N9R1C5. Here no additional t- value is possible, because N9C3 and N9C2 are not linked to previous cells other than the preceding one.
Similar things can be written for xyz- and xyzt- chains.

I have occasionally used other notations on this forum, such as:
{N1 N5}@R7C5 — {N5 N3}@R8C3 — {N3 N6}@R9C3 — {N6 N1}@R9C4
for an xy4-chain, but I finally came to the conclusion that the @ sign or any additional sign is useless and can only obscure the 3D symmetries of Sudoku. So that my final NRC notation for real chains does not include such signs.

In HLS, I have also made it evident that, fundamentally, a conjugacy link is a bivalue cell when seen in the proper rn-, cn- or bn- space. Moreover, it appears that all the chains that have ever been defined (such as AICs), when properly considered as 3D chains or chains in nrc-space, are (extended forms of) xy-chains. Now, it also appears that these extensions of xy-chains can be considered as allowing some additional cells in the appropriate space.
The above uniform NRC notation, when extended to nrc-space, has the advantage of exhibiting this most clearly.
Moreover, the t-, z- and zt- extensions introduced in HLS for 2D-chains can be generalised to 3D-chains in nrc-space (for these extensions, see the thread on nrc-, nrct-, nrcz- and nrczt- chains) and the NRC notation proves very convenient for this.

2) THE NRC NOTATION

Conventions:
- numbers are named N1, … N9,
- rows are named R1,… N9,
- columns are names C1,…C9,
- candidates are named NiRjCk, e.g. N1R3C6 denotes candidate N1 for rc-cell (R3, C6),
- lower case letters denote variables, upper case letters denote constants. Thus r1 is any row, but R1 is the first row; n1 is any number, but N1 is number 1,
- in real chains, only upper case letters will appear (this is obvious),
- in chain patterns, only lower case letters should appear (this is because of the natural geometric symmetries of Sudoku).

The basic notions underlying the NRC notation are that of an nrc-link, of a 3D-chain and of nrc-conjugate candidates (an nrc-group of nrc-candidates that can appear as a set of candidates in an appropriate 2D subspace) - see exact definition in the other thread.

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 any two candidates in the sequence are different (there is no loop, neither global nor internal) and any two consecutive candidates are nrc-linked.
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.
Thus, curly braces will be used to put together candidates that are in the same cell in either of the rc-, rn-, cn- or bn- spaces.
For instance, when curly braces enclose only 2 candidates, it means in rc-space that we have either a bivalue cell in rc-space or a conjugacy relation along a row, a column or a block
When they enclose more than two candidates, it means that we have a generalised form of these relations. For examples of these, see the thread on nrc-, nrct-, nrcz- and nrczt- chains.

3) EXAMPLES OF THE NRC NOTATION

First example:
N8R6{C8 C4} — N8R3{C4 C9}, which eliminates e.g. N8R2C8.
In this short AIC, the first bivalue cell in rn-space corresponds to a conjugacy link for number N8 along row R6. We then follow a simple link in cn-space from N8R6C4 to N8R3C4. Finally the second and last bivalue cell in rn-space corresponds a conjugacy link, still for number N8, along row R3. This allows to eliminate e.g. N8R2C8, because it is nrc-linked to N8R6C8 via a cn-link and to N8R3C9 via an rc-link (along a block).

Second example:
{N4 N8}R9C1 — {N8 N5}R4C1 — N5R6{C1 C8} — N5R9{C8 C7},
which eliminates e.g. N4R9C7.
In this simple AIC, we first have two bivalue rc-cells, joined by an xy-link in rc-space, then two bivalue rn-cells joined by an xy-link in rn-space. These two groups of cells are joined by an ordinary nrc-link between N5R4C1 and N5R6C1. The target N4R9C7 is in the same rn-cell as the first cell N4R9C1 and in the same cn-cell as the last cell N5R9C7.

AICs built on subsets (ALS, Hinges) can be represented as easily, with a subset (inner curly brackets) included within the brackets. In this case, it may happen that only one coordinate is left out of the outer brackets.

It has always been clear that extensions of xy or conjugacy chains were needed. Several proposals have been made, e.g. extending the notion of conjugacy to subsets, giving rise to AICs. In the Hidden Logic of Sudoku, I have made another proposal, built on extending the content of the cells in an xy-chain.
Moreover, by making explicit the fact that conjugacy means bivalue in the proper representation, this notation allows to simply represent the 3D analogues of the xyt- xyz- and xyzt- chains, which subsume all these chains and their hidden counterparts. Indeed, it is the impossibility to represent naturally these extensions that led me to devise the NRC notation. To convince yourself of this impossibility, just try to express an xyt-chain in the Eureka notation.