Sudoku Players' Forum (clone)

Principles of the nrc notation

In this thread, I’ll summarise the basics of the nrc notation.
This notation is the particular version for Sudoku of a general and natural notation meaningful for any finite Constraint Satisfaction Problem. For those interested in details or in such an extension and its application to other real puzzles, see my last book: "Pattern-Based Constraint Satisfaction and Logic Puzzles".

The nrc notation does not allow a priori to write any logical formula - but only those corresponding to predefined resolution rules. In case a new kind of resolution rule is introduced, the corresponding extension of the nrc notation may have to be explicitly specified.
This being said, the notation is already defined for many patterns, including all sorts of both reversible or oriented chains (which indeed allow to solve all the known puzzles) and its general principles are sufficiently clear to ensure that non-ambiguous extensions could be written if necessary.

The notation explicitly relies on a precise resolution model and on a view of Sudoku as a finite Constraint Satisfaction Problem.

Resolution model

The solution of a Sudoku puzzle is made of a sequence of steps, each of which is the result of applying a well-defined resolution rule
A resolution rule is of the type: rule-name[size]: condition pattern ==> action, with variables for rows, columns, blocks, numbers
- rule-name refers to the particular type of rule being invoked
- size refers to the size of the pattern among patterns of the above type
- action is a set of assertion(s) and/or elimination(s)
- condition pattern is a set of elementary conditions one may check directly on the current resolution state when specific values are assigned to all the variables representing rows, columns, blocks, numbers (when the condition pattern is instantiated)
- the formula "condition pattern ==> action" can be proven from the four basic axioms of Sudoku, independently of any particular instantiation

Needless to say, all the usual resolution rules satisfy these definitions (sometimes, after being properly re-written):
- Subsets, basic AICs, AICs with Subsets, …, SK-loops, J-Exocets
- whips, g-whips, S-Whips, W-whips and the corresponding braids and generalized braids
An example that doesn’t satisfy these definitions: Exocets that are not J-Exocets (a specific proof must be found in each particular case)
Another example: Trial-and-Error, which is a procedure and not a resolution rule (see my last book for the precise relation between this procedure and some resolution rules, namely braids)

All the patterns are defined at the same time as their size; they make families of patterns of same type but of different sizes. Thus, even if unspecified in current speech, a Subset or whip is in fact always a Subset or a whip of some well-defined size.

Sudoku as a Constraint Satisfaction Problem and its CSP-Variables

It is obvious that Sudoku is a Constraint Satisfaction Problem, with "natural" variables the 81 ricj for i,j = 1…9
In the "Hidden Logic of Sudoku" (HLS) (2007), I have introduced 3 additional 2D spaces, corresponding to 3 new sets of variables: rinj, cinj and binj, for i,j = 1…9, resulting in a total of 324 CSP-Variables The result was an extended Sudoku board, made of 4 sub-boards, each representing 81 of these variables.

Additional variables are redundant, but they are very useful for representing e.g. conjugacy. Indeed conjugacy becomes bivalue for the appropriate 2D cell. They are the basis for a fully super-symmetric view of Sudoku and they lead to extending patterns defined in the usual rc-space to their supersymmetric forms. In this way xy-chains become the well-known basic AICs; but more complex chains, such as t-chains can also be extended, as shown in HLS, giving rise to whips.
Examples from other puzzle types largely confirm the validity of this modeling choice, with explicit additional CSP-Variables.

Another advantage of this view is, there are only two basic relations between candidates:
- for 2 candidates: linked, i.e. related by a direct contradiction (different values in the same cell, same values in the same row/column/block), expressible by a (binary) logical NAND
- for any number of candidates: being the whole set of remaining candidates for some variable, expressible by a (multi-ary) logical XOR

The above definition of a resolution rule implies that the condition pattern must ultimately be expressed only in terms of the above basic XOR and NAND relations.
In another thread, it has been debated why XOR should be used instead of OR.
The question is legitimate, because the proofs of the resolution rules rely only on the OR part of the XOR.
However, there are two arguments for considering the XOR relation as primary instead of the OR:
- a modeling one: the fact is, all the direct OR relations are XOR;
- a complexity argument: as one has to look for the NAND relations in any case, knowing in advance that all the basic OR relations are XOR simplifies this other part of the search.
Should any indirect OR relation appear in a pattern, it should somehow be justified in terms of the elementary NAND and XOR

nrc notation for rows, columns, blocks, numbers, cells, candidates, g-candidates

rows are named r1, … r9, columns c1, …c9, blocks b1, … b9
numbers are named similarly n1, …n9
This is useful when 2D cells other than the rc-cells must be named
r1c1, … r9c9
r1n1, … r9n9
c1n1, … c9n9
b1n1, … b9n9
The "n" symbol allows to deal with numbers in the same way as with rows, columns, blocks. It is important wrt to all the super-symmetries of Sudoku.
The 729 candidates are written n1r1c1, …., n9r9c9
Notice that wrt to the 4 types of CSP-Variables, nirjck = true means simultaneously: rjck = ni, rjni = ck, ckni = rj, bpsq = ni (where (bp, sq) = (rj, ck), same rc-cell expressed in rc or bs coordinates)
A special notation is used for g-candidates, e.g.: n5r1c456 represents the set of (at most) 3 candidates for number n5 in row rj and columns c4, c5, c6.
(This notion of a g-candidate can also be extended to any CSP)

nrc notation for basic chains

Basic chains are "alternating" in the sense that their proof involves alternatively positive and negative inferences. There is no magic here: there are two types of rules, or at least of elementary actions: asserting a candidate as the real value of a cell or eliminating a candidate. All the mythology about AICs reduces to this obvious fact !!!
More complex chains may involve embedded patterns (e.g. Subsets), but at some point or another, the same alternating inferences phenomenon will happen, for the same reason.

Negative inferences can only rely on relation "linked", i.e. they are very straightforward. Therefore they should be represented by a very simple sign. In graphs, a line is used to represent a link between nodes (here the nodes are candidates). Correspondingly, in the nrc notation, a — is used for this purpose.

Positive inferences can only rely on the XOR relation, e.g.: XOR(a, b, c) AND (NOT a) AND (NOT b) ==> c
As the XOR involves the whole set of candidates for some CSP-Variable, it is naturally represented in the nrc notation by the standard set symbol: {}

However, only two candidates need be displayed within the {} symbols:
- the left-linking one, specifying how the cell is linked to the previous part of the chain
- the right-linking one, specifying the conclusion of the positive inference (within the context of the previous part), and used to link the cell to the forthcoming part of the chain
The reason is, a 2D-cell can be used for a positive inference iff it has only one candidate not contradicted by a previous part of the chain.
This is another way of saying that basic chains are non-anticipative or no-look-ahead: only the already defined part of a chain can be used to justify extending it further.


Elementary example 1: an xy-chain
xy-chain[3]: r1c1{n1 n2} — r1c4{n2 n6} — r3c4{n6 n1} ==> r3c1 ≠ 1
the type of the rule specifies that:
— must be understood as a direct link between the two candidates it relates
each CSP-Variable involved is to type rc and is bivalue

Elementary example 2: a bivalue-chain (= basic AIC)
bivalue-chain[3]: r1c1{n1 n2} — c2n2{r1 r3} — r3c4{n2 n1} ==> r3c1 ≠ 1
the type of the rule specifies that:
— must be understood as a direct link between the two candidates it relates
each CSP-Variable (which can be of any rc, rn, cn or bn type) involved is bivalue
in particular, c2n2{r1 r3} means that in column c2 number n2 is a candidate in only rows r1 and r3 (they are conjugate in the classical sense; in the super-symmetric view, conjugate is the same thing as bivalue).

Whip example
Elementary example 3: a whip
whip[3]: r1c1{n1 n2} — c2n2{r1 r3} — r3c3{n6 n1} ==> r3c1 ≠ 1
the type of the rule specifies that:
— must be understood as a direct link between the two candidates it relates
each CSP-Variable (which can be of any rc, rn, cn or bn type) involved is bivalue modulo the target n1r3c1 and the previous right-linking candidates
in particular: there may be in r3c3 other candidates (e.g. n2), provided that they are linked to n1r3c1 or n2r1c1 or n2r3c2. Such candidates (z-candidates like to the target, t-candidates linked to a previous right-linking candidate) are not part of the whip pattern; they don’t have to be explicitly mentioned.
Optionally, or when an example must be detailed, the 2D cells may be numbered with subscripts and the following notation may be used
whip[3]: r1c1{n1 n2}1 — c2n2{r1 r3}2 — r3c3{n6 n2#2 n1}3 ==> r3c1 ≠ 1, where #2 means the candidate is linked to the 2nd right-linking candidate. * would be used if it was linked to the target.


[Edit 2015/08/19: added the following partial copy of a post in another thread]
Comparison of the nrc and AIC notations for the same patterns: a bivalue r5c5 cell and a bilocal candidate n1 in row r5:

AIC notation:                 nrc notation:
 -(1=2)r5c5-                — r5c5{n1 n2} —
 -(1)r5c5=(1)r5c6-       — r5n1{c5 c6} —

While the AIC notation, introduced before the Sudoku symmetries were fully understood, fails to capture the essential identity of "bivalue" and "bilocal", it appears naturally in the nrc notation.

nrc notation for Subsets

Examples should be enough:
Naked Pair in a row: r1{c3 c4} {n5 n6} - short version NP: r1c34n56
Hidden Pair in a row: r1 {n5 n6} {c3 c4} - short version HP: r1n56c34
X-Wing in rows: n1 {r2 r3} {c4 c5} - short version SHP: n1r23c45

nrc notation for chains with embedded patterns (Subsets or other chains)

First fundamental remark: only right-linking elements need be generalized; left-linking ones may be kept as mere candidates.
Second fundamental remark: only full patterns will ever appear as right-linking objects (there is no A-thing or AAHHHA-thing). This is possible because the zt-ing principle is stronger than the almosting principle.

There are two options:
either each full sub-pattern is written at its place inside the proper {}
or each sub-pattern is written as a capital letter in the proper {} and a line is added for each such letter, fully describing the pattern in the nrc notation
I largely prefer the second option.


nrc notation for other patterns (nets):
I’ve never felt any need for such extensions, but it is easy to accommodate almost anything within the {}, using capital letters and separate lines for defining them, while retaining the essential XOR meaning for {}.


Note: as whips or braids are enough to solve almost all the 9x9 puzzles (indeed only one in about 30,000,000 cannot be solved by braids), such extensions are rarely useful.

One more comparison of nrc and AIC notations

Let's take the easy puzzle from this recent thread: http://forum.enjoysudoku.com/august-20-2015-t32646.html.
This is the simplest solution proposed, with a single basic AIC:

Leren wrote:

Code: Select all

*--------------------------------------------------------------*
| 2     358   6      | 1     57    9      | 34    357   3458   |
| 359  f3589  1      | 2     4     578    | 6    e3579  358    |
| 59    7     4      | 3     56    568    |d29    1    c258    |
|--------------------+--------------------+--------------------|
| 4     235   29     | 59    35679 567    | 1     8     356    |
| 3567  35    79     | 8     2     1      | 349   359   3456   |
| 356   1     8      | 4     3569  56     | 239   2359  7      |
|--------------------+--------------------+--------------------|
| 17    6    a27     | 59    59    3      | 8     4    b12     |
| 19   g9-2   5      | 6     8     4      | 7     23    123    |
| 8     4     3      | 7     1     2      | 5     6     9      |
*--------------------------------------------------------------*

(2) r7c3 = r7c9 - r3c9 = (2-9) r3c7 = r2c8 - r2c2 = (9) r8c2 => - 2 r8c2; stte

This is how it is written in the nrc and AIC notations (AIC is from above, nrc is its translation):

nrc:     biv-chain[4]: r7n2{c3 c9} — r3n2{c9 c7} — b3n9{r3c7 r2c8} — c2n9{r2 r8} => r8c2 ≠ 2    (*)
AIC:                         (2) r7c3 = r7c9 - r3c9 = (2-9) r3c7 = r2c8 - r2c2 = (9) r8c2 => - 2 r8c2     (**) 

Notice that, apart from the explicit statement of the pattern being used in nrc (announcing that every 2D cell will be strictly bivalue), the length of the description is about the same. But groupings of terms are different: nrc considers that the — (- in AIC) are straightforward, while the parts within the { } (around the = in AIC) are the most important ones. AIC makes no difference (or, if any, it makes the opposite one, as suggested by the "(2-9) r3c7" ).

Whereas every step has a straightforward meaning in the nrc notation, there's only one step of the AIC notation that doesn't raise a problem. Actually, among the 9 steps (= or - signs), there's only one, the (2-9) r3c7, that can be straightforwardly interpreted; all the other steps require non-local information (i.e. information not directly present at the left or right of the = or - sign.

Let's see the ='s first:
- in order to understand the first =, one has to extend the scope of the first (2) to the right beyond the right side of the first =
- in order to understand the second =, one has to momentarily forget the remaining ( -9) in the (2-9) AND to extend the scope of the 2 in (2-9) to the left beyond the left side of the second equal
- in order to understand the third =, one has to momentarily forget the (2- ) AND to extend the scope of the remaining (9) to the right beyond the right side of the third =
- in order to understand the fourth =, one has to extend the scope of the second (9) to left right beyond the left side of the fourth =

Let's now see the -'s:
- in order to understand the first -, one has to extend the first (2) to the right beyond the first = AND to split the (2-9) AND to extend the 2 in this (2-9) to the left beyond the second =
- the second -, within (2-9), is the only place where things are clear
- as for the last -, one has to split the (2-9), to extend the 9 to the right beyond the second = AND to extend the last (9) to the left beyond the last =

Two final points:
- the position of the last (9), after the =, is arbitrary; the same meaning was intended at the start of the chain, with the (2) before the =
- parentheses around the (2) and (9) convey no meaning and are therefore useless


* One could also write the 3rd cell as b3n9{s7 s5}, using the dual coordinate system (where r3c7=b3s7 and r2c8=b3s5), but it would be more difficult to check the — with the previous and next candidates; that's why the standard nrc notation redundantly writes the full rc instead of the s for the bn variables:
biv-chain[4]: r7n2{c3 c9} — r3n2{c9 c7} — b3n9{s7 s5} — c2n9{r2 r8} => r8c2 ≠ 2
** I'm not an expert in AIC; I suppose this is a standard form; correct me otherwise, I'll revise the details

I don't get the point you are trying to make.

Understanding chains so that they can be followed is a matter of learning the conventions they use.

Validating chains requires sight of the pencil marked grid. But the AIC and nrc chains both state the inferences that exist between successive terms, so surely the scope of the checks the reader would need to make are the same in each case.

.

David P Bird wrote:I don't get the point you are trying to make.
Understanding chains so that they can be followed is a matter of learning the conventions they use.
Validating chains requires sight of the pencil marked grid. But the AIC and nrc chains both state the inferences that exist between successive terms, so surely the scope of the checks the reader would need to make are the same in each case.

I just want to point out that some conventions (nrc) are more natural than others (AIC).
The placement of digits in AIC is inconsistent (sometimes before, sometimes after)
The placement of parenthesis in AIC is inconsistent (either it means nothing and it is useless OR (not XOR ) it means different things at different places.
The grouping of terms is uniform in nrc, not in AIC.
Moreover, the rc/rn/cn/bn symmetry apparent in the nrc notation at the elementary level of one term, that I pointed out in a previous post, is here shown in a full pattern.

I agree that the reader has to check the same things: it's the same pattern. What I mean is, each step is easier to check with the nrc notation.
I also agree that in both cases, the reader has to learn a few basic conventions in order to understand, but I think the uniformity of nrc makes it easier to learn.
I know I won't convince you. I just hope you consider the comparison with some objectivity.

"more natural" is in the eye of the beholder. For each of your points about AIC, there is an equivalent point about nrc notation, for example the ordering of the nrc terms is inconsistent in nrc notation. Which is preferred/more natural is going to be a matter of personal preference.

JasonLion wrote:"more natural" is in the eye of the beholder. For each of your points about AIC, there is an equivalent point about nrc notation, for example the ordering of the nrc terms is inconsistent in nrc notation. Which is preferred/more natural is going to be a matter of personal preference.

Probably in the same way as what you consider as a matter of personal attack.

The way you wrote before was from the point of view of someone trying to work out the meaning of an AIC from scratch while having prior knowledge of nrc conventions. It was far from a fair comparison.

The AICs are now well established for notating Sudoku discussions, so much so that any attempt to enforce a superior method is almost certain to fail. However various dialects and breaches of grammar have taken hold because of the current fashion to concentrate on single-step solutions, and it some of these that you are choosing to focus on.

As it is, I'm mimicking the role of the 'Commissariat Général de la Langue Française' and trying to stop them going too far, as I'm sure you would have to do too if a significant number of players were using nrc notation.

Recommended reading: 'Mother Tongue' by Bill Brydson.
One fact he gives is that in 1987 translations were costing the European Community $15 per word, $500 per page, amounting to $700 million or a third of all administration costs.

PS I saw nothing personal in the edited sentence.

.

David P Bird wrote:The way you wrote before was from the point of view of someone trying to work out the meaning of an AIC from scratch while having prior knowledge of nrc conventions. It was far from a fair comparison.
The AICs are now well established for notating Sudoku discussions, so much so that any attempt to enforce a superior method is almost certain to fail.

AICs are "well established" on this forum, i.e. for a few handfuls of people, as I can see from the mean (number of views)/(number of posts) in the recent threads.
And even among these, previous discussions have shown they are not so well established.
Your conclusion is realistic, but sad: "any attempt to enforce a superior method is almost certain to fail".

David P Bird wrote:However various dialects and breaches of grammar have taken hold because of the current fashion to concentrate on single-step solutions, and it some of these that you are choosing to focus on.

On the contrary, my example was the simplest and most "classic" AIC.


Considering David's conclusion, which I believe particularly realistic, I've decided to withdraw from this forum.