The Hidden Logic of Sudoku
A new conceptual framework
for solving Sudoku puzzles with pure logic
Denis Berthier
First edition: May 2007
Second edition: November 2007
Online Supplements
nrczt chains and lassos
© Denis
Berthier. All the material in this page and the pages it gives
access to are the property of the author and may not be
re-published or re-posted without his prior written permission.
A) FULLY
SUPERSYMMETRIC CHAINS or 3D-CHAINS:
NRC-, NRCT-, NRCZ- AND NRCZT- CHAINS
Before the introduction of 3D chains and apart from c-chains, all
the chains I had considered were defined and could be spotted as
(pure or extended) xy-chains in either of the two dimensional rc-,
rn- or cn- spaces: (h)xy(z)(t) chains. 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 right-linking candidate in the
chain (or by the target) 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.
A1) GENERAL DEFINITIONS AND THEOREMS
GENERAL 3D-CHAINS
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, it is not its factual definition).
An nrc-link is written in the simplest and most natural way as "—".
Here are now the most basic definitions for chains.
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.
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 forthcoming definitions of 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.
Remark on inner
loops: notice that global loops are excluded by definition,
but not inner loops. Inner loops can easily be proven to be useless (in the
sense that they don't lead to more eliminations) for some types of
chains (in 2D: xy, hxy, c, xyz, hxyz; in 3D: nrc-, nrcz-).
It would therefore seem to be an arbitrary restriction to exclude
inner loops a priori from
chains with the t-extension. But, in practice, inner loops are useless. Moreover, nrczt-
chains or whips in which inner loops would
be allowed are subsumed by nrczt-braids
in which allowing loops is obviously a priori useless.
Let us therefore say that 3D (nrc, nrcz, nrct, nrczt) chains or
whips that satisfy the no-loop condition are "standard". In all
these web pages, only standard chains, lassos or whips will be
considered.
To be explicit, the no-loop condition is expressed as: all the
candidates in the chain are different.
NRC-CHAINS
Definition: two candidates n1r1c1 and n2r2c2 are nrc-conjugate or nrc-bivalue 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" or "nrc-bivalue" is the most general, fully
super-symmetric synthesis of two properties of candidates:
- the bivalue property of rc-cells,
- the conjugacy property of candidates, which is merely a bivalue
property of corresponding rn-, cn- of bn-cells in rn-, cn- or bn-
space.
Definition: an nrc-chain of
length n is a 3D-chain of 2n candidates 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 3) 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
of length n is a 3D-chain of 2n candidates 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 previous right-linking candidates.
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 Z, an nrczt-chain of length n is a 3D-chain of 2n
candidates 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 Z
plus the previous right-linking candidates,
- 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 3) 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.
In any of these chains, odd candidates are called left-linking and
even candidates are called right-linking. This is because of their
nrc-link with the previous or the next candidate.
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:
- for any of the chains without the z-extension: if the first
candidate was false, then all the even candidates would be true and
all the odd candidates would be false;
- in the case of nrcz- and nrczt- chains, the target cell has to be
included in the proof itself: if the target was true, then all the
odd candidates would be false and all the even candidates would be
true.
In both cases, 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 candidate C, if it was true true, then it would be
false; therefore, it is false.
What is difficult for these chains is not proving the validity of
the associated chain rules, it is:
- for the theoretician, establishing the proper definitons in their
full generality,
- for the player, spotting the actual chains on an actual grid.
Remarks:
1) As for the 2D chains, the
additional t- or z- candidates are not part of the 3D chains.
This is not an arbitrary convention; it has practical consequences:
if I notice a chain but I don't use it immediately (e.g. because
I've seen a shorter one), then, later, some z- or t- candidates may
have disappeared; if the left-linking and right-linking ones haven't
changed, this will still be the same chain. This is extensively used
in SudoRules.
2) 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.
OBVIOUS 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
Lots of other, less obvious, subsumption relations are available in
the "subsumption" page.
Theorem: nrczt-chains subsume the
basic interactions.
See the subsumption page.
RESULTS
The nrc-, nrct- and nrczt- chains have been included in SudoRules
version 13 (used for the second edition of the book).
SudoRules 13 can solve all 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 all the puzzles in Ruud’s top10000.
Among the puzzles that cannot be solved with only the rules
described here:
- EasterMonster (for which no "pure logic" solution has yet been
found).
COMMENTS
1) Relationship with MINLs (Multiple Inference Nice Loops)
MINLs are nets (with branching and merging of different paths)
whereas any of the (h)xy(z)(t) or nrc(z)(t) chains is a chain - i.e.
a linearly ordered sequence of cells (for the 2D chains) or
candidates (for the 3D chains).
In any of the chains I defined, there is always a single path from
head to tail: x1, y1, x2, y2, x3, y3 ......, xn, yn.
The logic of these chains is also very simple. All are conceptually
straightforward (though very powerful) extensions of the most basic
xy-chains.
The (very standard) logic of an xy-chain (the once and for all proof
of the xy-chain theorem) is as follows:
If target
then not x1
then y1
then not x2
then y2
......
then
not xn
then
yn
then
not target.
Therefore not target
The yk => not x(k+1) steps are ensured by the existence of a
direct link between these 2 candidates.
The not xk => yk steps are ensured by a bivalue cell containing
only xk and yk.
The simplest generalisation consists of admitting additional
candidates in these bivalue cells: any candidates that are linked to
a previous y candidate or to the target. I suggest you try first to
find such xyt or xyzt chains. For examples, you can look at the
dedicated xyt-chains thread on this forum.
The next step is transfering this result to the rn and cn spaces,
i.e. using exactly the same patterns but in the rn or cn
representations. The Sudocue program can generate automatically
these representations. If you have learnt to find xy(z)t chains,
then you`ll find easily their `hidden` counterparts.
The next step starts with the nrc chains. These are just a different
view of the most basic NLs or AICs (which are exactly the same
thing). An nrc-chains is just an xy-chain in which:
- all the links are nrc-links between candidates instead if links
between cells
- and the ivalue relationship between each (xk, yk) couple is
replaced by a bivalue or bilocation relationship.
Now the same principle can be applied to nrc-chains as was applied
to xy-chains: any of the bivalue or bilocation relation can be
relaxed to a bivalue or bilocation modulo the previous yk candidates
(the right-linking candidates) and/or the target. In practice, this
merely means that any candidate that might prevent the bivalue or
bilocation relation to hold may be forgotten (but not deleted - this
is just doable while a given chain is built) provided that it is
nrc-linked to any of the previous yk or the target.
A2) CLASSIFICATION RESULTS FOR 3D CHAINS, or fully
supersymmetric chains or nrc(z)(t)-chains
Although there is no reason for this, chains remain frightening for
some people.
This problem may be the result of the language often used to speak
of them ("weak" and "strong" links, …), confusing a factual presence
of a pattern on a grid and the way a theorem allowing to draw
conclusions from it has been proven once and for all.
Chains are no more and no less patterns than any other pattern (e.g.
fish or pairs).
The following results show that most of the time, chains needed to
solve a puzzle can be of very limited length.
Definitions
Basic resolution rules (the L4_0 level in my book) are defined as:
- Subsets of length 1 to 4: Naked + Hidden + Super Hidden (fish)
- Basic Interactions
- XY-Wing, XYZ-Wing
Levels L4,… Ln are defined as:
Ln = basic rules + 2D chains, i.e. (h)xy(z)(t)- and c- chains, of
length no more than n; the length of a 2D chain is defined as the
number of cells on which it lies (in its base space: rc-, rn- or cn-
), target not included;
Levels M4,… Mn are defined as:
Mn = Ln + 3D chains, i.e. nrc(z)(t)-chains, of length no more than
n; the length of a 3D chain is defined as the number of cells on
which it lies when considered as a chain of cells (i.e. half the
number of its linking candidates), target not included.
This convention amounts to considering bilocation links as
equivalent to bivalue links, i.e. to putting no penalty on 3D chains
wrt 2D chains of the same length. This is the stance usually adopted
by adpets of AICs. But SudoRules could be used with other
conventions.
Collection of puzzles used for these results
The Sudogen0 collection has been used.
Remember that it is a randomly generated collection of minimal
puzzles; it was generated with the suexg / suexco generator from
Magictour. It is available on my web pages.
(Remember that "minimal" means that if a clue is deleted, then the
resulting puzzle has more than one solution).
Classification results
The following table gives the number of puzzles solved at each
level, in the L and M classifications.
level.......4..........5............6...........7
L.........8271.....8959......9326.......9472
M........9638.....9893......9964.......9984
Comments
As can be seen from these tables,
- 99% of the randomly generated
minimal puzzles can be solved with 3D chains of length no more
than 5;
- almost all (99.84%) the randomly
generated minimal puzzles can be solved with 3D chains of length
no more than 7.
(Notice that all the remaining 16 puzzles are also solved by
SudoRules, but with longer chains).
3D chains are harder to discover than 2D chains, but they allow to
consider only short chains, compatible with the idea taken from
psychology that a human being's short term memory has size 7 (+-2).
A3) NRCZT- CHAINS AND NRCZT- LASSOS
Once we have built a partial nrct- or nrczt- chain, 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 we had not
excluded loops. 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 we had not excluded loops.
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.)
Generally, these lassos lead to slightly shorter partial
nrc(z)t-chains and faster solutions, and they are interesting for
this reason, but they do not lead to eliminations that could not
have been obtained without them, as shown by the following
classification results.
More precisely, when applicable, they generally shorten the chains
by only 1 cell and very rarely by 2 cells. (This has been tested on
the full Sudogen0 collection of 10,000 puzzles).
We can therefore consider using them as a minor improvement over
nrc(z)(t) chains alone.
Updated classification results
The following table gives the number of puzzles solved at each
level, in the L, M and N classifications (elaborating on the results
given previously):
Level n in the N classification allows lassos of length n.
level.......4..........5............6...........7
L.........8271.....8959......9326.......9472
M........9638.....9893......9964.......9984
N........9658.....9913......9975.......9991
As can be seen from these tables,
- 99% of the randomly generated
minimal puzzles can be solved with 3D chains or lassos of length
no more than 5;
- almost all (99.9%) the randomly
generated minimal puzzles can be solved with 3D chains or lassos
of length no more than 7.
(Notice that the 9 remaining puzzles are also solved by SudoRules,
but with longer chains or lassos).
More detailed results, based on a sample of 1,000,000 puzzles are
available in the "ratings" page.
A4) MODERATE LEVEL EXAMPLES OF NRC(Z)(T) CHAINS
Here are three pedagogic examples, in increasing order of
complexity. These puzzles are taken from the Ocean collection, a vey
nice collection, with all its puzzles starting with one or more
swordfish: http://www.sudoku.com/boards/viewtopic.php?t=4144
Puzzle #1uses only nrc chains (of length no more than 4).
Our first example, which is also #1 in the list uses only
nrc-chains.
Remember that nrc-chains are merely another view of "basic" AICs,
i.e. AICs with no subsets of any kind (groups, hinges, …).
The chains used in this example should therefore be familiar.
000010002
001000030
040005600
000006700
300000005
008400000
007800040
050000900
200030000
swordfish-in-columns n3{r7 r1 r6}{c2 c6 c7} ==> r7c9 <> 3,
n3{r7 r1 r6}{c2 c6 c7} ==> r6c9 <> 3, r1c4 <> 3,
==> r1c3 <> 3
swordfish-in-columns n4{r4 r8 r2}{c1 c5 c9} ==> r8c6 <> 4,
r8c3 <> 4, r4c3 <> 4, r2c7 <> 4, ==> r2c6
<> 4
swordfish-in-rows n5{r2 r6 r7}{c7 c1 c5} ==> r9c7 <> 5,
r4c5 <> 5, r4c1 <> 5, r1c7 <> 5, r1c1 <> 5
nrc3-chain n5{r9c8 r1c8} - {n5 n8}r2c7 - {n8 n1}r9c7 ==> r9c8
<> 1
nrc3-chain {n1 n8}r9c7 - {n8 n4}r1c7 - n4{r1c6 r9c6} ==> r9c6
<> 1
nrc3-chain n2{r8c8 r7c7} - n3{r7c7 r7c2} - {n3 n6}r8c3 ==> r8c8
<> 6
nrc4-chain n3{r1c2 r1c6} - n4{r1c6 r2c5} - n4{r8c5 r8c1} - n8{r8c1
r9c2} ==> r1c2 <> 8
nrc3-chain n8{r9c2 r2c2} - {n8 n5}r2c7 - n5{r7c7 r9c8} ==> r9c8
<> 8
nrc4-chain n5{r1c3 r2c1} - n5{r2c7 r7c7} - n3{r7c7 r7c2} - {n3
n6}r8c3 ==> r1c3 <> 6
nrc4-chain {n9 n5}r1c3 - n5{r4c3 r4c4} - n3{r4c4 r3c4} - n3{r3c3
r1c2} ==> r1c2 <> 9
nrc4-chain n3{r1c6 r3c4} - n3{r4c4 r4c9} - n4{r4c9 r2c9} - n4{r2c5
r1c6} ==> r1c6 <> 9, r1c6 <> 8, r1c6 <> 7
nrc4-chain {n6 n3}r8c3 - n3{r3c3 r3c4} - {n3 n4}r1c6 - n4{r9c6 r8c5}
==> r8c5 <> 6
nrc3-chain n6{r2c5 r7c5} - n5{r7c5 r7c7} - n5{r2c7 r2c1} ==> r2c1
<> 6
nrc3-chain n6{r2c5 r7c5} - n5{r7c5 r7c7} - {n5 n8}r2c7 ==> r2c5
<> 8
nrc4-chain n2{r8c8 r7c7} - n5{r7c7 r7c5} - n6{r7c5 r2c5} - n4{r2c5
r8c5} ==> r8c5 <> 2
nrc4-chain {n8 n5}r2c7 - n5{r7c7 r7c5} - n6{r7c5 r2c5} - n4{r2c5
r2c9} ==> r2c9 <> 8
nrc4-chain n6{r2c5 r7c5} - {n6 n1}r7c9 - {n1 n8}r9c7 - n8{r9c2 r2c2}
==> r2c2 <> 6
row r2 interaction-with-block b2 ==> r1c4 <> 6
nrc3-chain n6{r1c1 r1c2} - n3{r1c2 r7c2} - {n3 n6}r8c3 ==> r8c1
<> 6, r7c1 <> 6
nrc3-chain n6{r1c1 r6c1} - n5{r6c1 r2c1} - {n5 n9}r1c3 ==> r1c1
<> 9
nrc4-chain n6{r1c1 r6c1} - n5{r6c1 r4c3} - {n5 n9}r1c3 - {n9 n7}r1c4
==> r1c1 <> 7
nrc4-chain {n7 n9}r1c4 - {n9 n5}r1c3 - n5{r4c3 r4c4} - n3{r4c4 r3c4}
==> r3c4 <> 7
nrc4-chain {n6 n3}r8c3 - n3{r3c3 r3c4} - {n3 n4}r1c6 - n4{r9c6 r9c3}
==> r9c3 <> 6
nrc3-chain n4{r4c1 r5c3} - {n4 n9}r9c3 - {n9 n1}r7c1 ==> r4c1
<> 1
nrc4-chain {n1 n8}r9c7 - {n8 n4}r1c7 - {n4 n3}r1c6 - n3{r6c6 r6c7}
==> r6c7 <> 1
nrc3-chain {n2 n3}r6c7 - n3{r4c9 r4c4} - n5{r4c4 r6c5} ==> r6c5
<> 2
nrc4-chain {n2 n3}r6c7 - n3{r7c7 r8c9} - n3{r8c3 r3c3} - n2{r3c3
r2c2} ==> r6c2 <> 2
nrc4-chain {n2 n3}r6c7 - n3{r6c6 r4c4} - n5{r4c4 r9c4} - n5{r9c8
r7c7} ==> r7c7 <> 2
…(NS+HS)…
635914872
981267534
742385619
419526783
326178495
578493261
197852346
853641927
264739158
Puzzle #3 uses nrct chains (still of length no more than 4)
The second example, #3 in the list, requires various kinds of
chains, including nrct-chains of length upto 4.
Interestingly, it also uses 2D chains, i.e. chains in the rc-, rn-
and cn- spaces. Remember that these chains are particular case of
nrc(z)(t) chains.
I keep have in SudoRules as independent chains because they are
easier to spot (in my view of things, more general does not mean
better).
Remember that 2D chains are enough to solve 97% of the randomly
generated puzzles - although nrc(z)(t) chains sometimes allow using
shorter chains (but 3D instead of 2D).
This is a very good example for understanding what is allowed by the
t extension.
000010002
001000030
040005600
000007400
300000006
008900000
006300080
050000100
200040000
swordfish-in-columns n3{r9 r1 r6}{c2 c6 c7} ==> r9c9 <> 3,
r9c3 <> 3, r6c9 <> 3, r6c5 <> 3, r1c3 <> 3
nrc3-chain n4{r6c6 r6c1} - n4{r5c3 r8c3} - n4{r8c8 r1c8} ==> r1c6
<> 4
nrc4-chain n3{r1c6 r3c5} - n3{r3c3 r8c3} - n4{r8c3 r5c3} - n4{r6c1
r6c6} ==> r6c6 <> 3
hidden singles ==> r4c5 = 3, r1c6 = 3, r3c3 = 3, r9c2 = 3, r8c9 =
3, r6c7 = 3, r8c1 = 8, r2c2 = 2, r1c2 = 8
column c2 interaction-with-block b4 ==> r6c1 <> 6, r4c1
<> 6
row r9 interaction-with-block b8 ==> r7c6 <> 1
hidden-pairs-in-a-block {n1 n8}{r9c4 r9c6} ==> r9c6 <> 9,
r9c6 <> 6, r9c4 <> 7, r9c4 <> 6
hidden-single-in-a-row ==> r9c8 = 6
hidden-pairs-in-a-block {n1 n8}{r9c4 r9c6} ==> r9c4 <> 5
hidden-single-in-a-block ==> r7c5 = 5
block b8 interaction-with-row r8 ==> r8c8 <> 7, r8c3
<> 7
nrc2-chain n8{r2c7 r5c7} - n8{r4c9 r4c4} ==> r2c4 <> 8
nrczt2-chain n8{r2c7 r5c7} - n8{r5c5 r3c5} ==> r2c6 <> 8
nrc3-chain {n9 n2}r7c6 - n2{r7c7 r8c8} - n4{r8c8 r7c9} ==> r7c9
<> 9
nrct3-chain n2{r3c4 r3c5} - {n2 n8}r5c5 - n8{r2c5 r3c4} ==> r3c4
<> 7
nrczt3-chain n4{r6c1 r7c1} - {n4 n7}r7c9 - n7{r7c2 r5c2} ==> r6c1
<> 7
nrczt3-chain n5{r4c4 r5c4} - n5{r5c3 r1c3} - n5{r1c8 r6c8} ==>
r4c9 <> 5
nrczt3-chain n5{r5c4 r4c4} - n5{r4c3 r1c3} - n5{r1c8 r6c8} ==>
r5c7 <> 5
hxyt-cn4-chain {r1 r8}c8n4 - {r8 r5}c3n4 - {r5 r4}c3n2 - {r4 r1}c3n5
==> r1c8 <> 5
column c8 interaction-with-block b6 ==> r6c9 <> 5
nrc3-chain {n1 n7}r6c9 - {n7 n4}r7c9 - n4{r7c1 r6c1} ==> r6c1
<> 1
nrc4-chain n5{r6c8 r6c1} - n4{r6c1 r7c1} - {n4 n7}r7c9 - {n7 n1}r6c9
==> r6c8 <> 1
nrct4-chain {n2 n8}r5c5 - n8{r5c7 r4c9} - n8{r3c9 r3c4} - n2{r3c4
r3c5} ==> r8c5 <> 2, r6c5 <> 2
naked-single ==> r6c5 = 6
hidden-single-in-a-row ==> r4c2 = 6
naked-pairs-in-a-row {n1 n7}r6{c2 c9} ==> r6c8 <> 7, r6c6
<> 1
hidden-pairs-in-a-column {n1 n8}{r5 r9}c6 ==> r5c6 <> 4,
r5c6 <> 2
swordfish-in-columns n4{r7 r6 r2}{c1 c6 c9} ==> r2c4 <> 4
nrc2-chain n2{r6c8 r6c6} - n2{r7c6 r7c7} ==> r8c8 <> 2
naked and hidden singles ==> r7c7 = 2, r7c6 = 9, r8c5 = 7, r5c2 =
9
column c1 interaction-with-block b1 ==> r1c3 <> 9
xy3-chain {n2 n4}r6c6 - {n4 n5}r6c1 - {n5 n2}r4c3 ==> r4c4
<> 2
xy3-chain {n1 n8}r5c6 - {n8 n7}r5c7 - {n7 n1}r6c9 ==> r5c8
<> 1
row r5 interaction-with-block b5 ==> r4c4 <> 1
xy3-chain {n2 n5}r4c3 - {n5 n8}r4c4 - {n8 n2}r5c5 ==> r5c3
<> 2
hidden-single-in-a-block ==> r4c3 = 2
nrc3-chain {n5 n4}r6c1 - n4{r5c3 r5c4} - n5{r5c4 r4c4} ==> r4c1
<> 5
naked and hidden singles ==> r4c1 = 1, r6c2 = 7, r7c2 = 1, r6c9 =
1, r3c8 = 1
x-wing-in-rows n7{r3 r7}{c1 c9} ==> r9c9 <> 7, r2c9
<> 7, r2c1 <> 7 r1c1 <> 7
nrc3-chain {n5 n9}r9c9 - {n9 n4}r8c8 - n4{r7c9 r2c9} ==> r2c9
<> 5
hidden-single-in-a-column ==> r9c9 = 5
nrc3-chain {n7 n5}r1c3 - n5{r1c7 r2c7} - n7{r2c7 r2c4} ==> r1c4
<> 7
hidden-single-in-a-block ==> r2c4 = 7
nrc3-chain n6{r2c1 r2c6} - n4{r2c6 r6c6} - {n4 n5}r6c1 ==> r2c1
<> 5
…(NS+HS)…
685413792
921786534
743295618
162837459
394521876
578964321
416359287
859672143
237148965
Puzzle #6 uses nrczt chains (still of length no more than 4)
Our third example, #6 in the list, uses nrczt4 chains. After you
have understood with the previous example what is allowed by the t
extension, it will allow you to understand what is allowed by the z
extension.
000010002001000030040005600000007800100000005003400000006300090050000400200080000
swordfish-in-columns n3{r9 r1 r5}{c2 c6 c7} ==> r9c9 <> 3,
r5c5 <> 3, r1c1 <> 3
swordfish-in-columns n4{r4 r7 r2}{c1 c5 c9} ==> r7c6 <> 4,
r4c8 <> 4, r4c3 <> 4, r2c6 <> 4
swordfish-in-rows n5{r2 r6 r7}{c7 c1 c5} ==> r9c7 <> 5,
r4c5 <> 5, r4c1 <> 5, r1c7 <> 5, r1c1 <> 5
nrczt3-chain n1{r4c4 r6c6} - n1{r6c7 r7c7} - n1{r7c2 r9c2} ==>
r9c4 <> 1
nrc4-chain n5{r7c7 r7c5} - n5{r6c5 r4c4} - n1{r4c4 r8c4} - {n1
n2}r7c6 ==> r7c7 <> 2
hidden-single-in-a-block ==> r8c8 = 2
column c8 interaction-with-block b3 ==> r3c9 <> 8, r2c9
<> 8
nrc4-chain n3{r1c6 r3c5} - n3{r4c5 r4c9} - n4{r4c9 r2c9} - n4{r2c5
r1c6} ==> r1c6 <> 9, r1c6 <> 8, r1c6 <> 6
nrc4-chain n4{r1c8 r2c9} - n4{r2c5 r7c5} - n5{r7c5 r7c7} - n5{r9c8
r1c8} ==> r1c8 <> 8
hidden singles ==> r3c8 = 8, r3c9 = 1
row r8 interaction-with-block b8 ==> r9c6 <> 1, r7c6
<> 1
naked-single ==> r7c6 = 2
nrct3-chain n3{r5c7 r4c9} - n4{r4c9 r2c9} - n9{r2c9 r6c9} ==>
r5c7 <> 9
nrc4-chain n4{r1c8 r2c9} - n4{r2c5 r7c5} - n5{r7c5 r7c7} - n5{r9c8
r1c8} ==> r1c8 <> 7
nrc4-chain n3{r4c9 r5c7} - n3{r5c6 r1c6} - n4{r1c6 r1c8} - n4{r5c8
r4c9} ==> r4c9 <> 9
block b6 interaction-with-row r6 ==> r6c6 <> 9, r6c5
<> 9, r6c2 <> 9, r6c1 <> 9
nrc4-chain n9{r6c9 r2c9} - n4{r2c9 r4c9} - n3{r4c9 r5c7} - n2{r5c7
r6c7} ==> r6c7 <> 9
hidden-single-in-a-block ==> r6c9 = 9
nrc3-chain {n7 n4}r2c9 - {n4 n5}r1c8 - n5{r2c7 r2c1} ==> r2c1
<> 7
nrc4-chain n5{r9c4 r9c8} - {n5 n4}r1c8 - {n4 n7}r2c9 - {n7 n6}r9c9
==> r9c4 <> 6
nrc4-chain n3{r1c2 r1c6} - n4{r1c6 r1c8} - {n4 n7}r2c9 - {n7 n9}r1c7
==> r1c2 <> 9
nrc4-chain n3{r4c9 r5c7} - n3{r5c6 r1c6} - n4{r1c6 r1c8} - n4{r5c8
r4c9} ==> r4c9 <> 6
column c9 interaction-with-block b9 ==> r9c8 <> 6
nrc4-chain n4{r7c5 r9c6} - n4{r1c6 r1c8} - n5{r1c8 r9c8} - n5{r9c4
r7c5} ==> r7c5 <> 7
nrct4-chain {n8 n7}r7c9 - {n7 n4}r2c9 - n4{r4c9 r4c1} - {n4 n8}r7c1
==> r7c2 <> 8
nrczt4-chain {n7 n9}r1c7 - {n9 n5}r2c7 - n5{r1c8 r9c8} - n7{r9c8
r5c8} ==> r6c7 <> 7
nrc3-chain {n2 n1}r6c7 - n1{r4c8 r4c4} - n5{r4c4 r6c5} ==> r6c5
<> 2
nrc4-chain {n6 n5}r6c5 - {n5 n4}r7c5 - n4{r2c5 r1c6} - n3{r1c6 r5c6}
==> r5c6 <> 6
nrczt4-chain {n7 n9}r1c7 - {n9 n5}r2c7 - n5{r1c8 r9c8} - n7{r9c8
r6c8} ==> r5c7 <> 7
block b6 interaction-with-column c8 ==> r9c8 <> 7
nrc3-chain n1{r4c4 r4c8} - {n1 n5}r9c8 - n5{r9c4 r4c4} ==> r4c4
<> 9, r4c4 <> 6
nrc3-chain n1{r4c4 r4c8} - {n1 n5}r9c8 - n5{r9c4 r4c4} ==> r4c4
<> 2
xy3-chain {n6 n5}r6c5 - {n5 n1}r4c4 - {n1 n6}r4c8 ==> r6c8
<> 6, r4c5 <> 6
nrc3-chain {n1 n5}r9c8 - n5{r9c4 r4c4} - n1{r4c4 r4c8} ==> r6c8
<> 1
naked-single ==> r6c8 = 7
nrc3-chain {n2 n3}r5c7 - {n3 n4}r4c9 - n4{r5c8 r5c3} ==> r5c3
<> 2
nrczt3-chain n2{r6c2 r6c7} - n1{r6c7 r4c8} - n6{r4c8 r4c1} ==>
r6c2 <> 6
nrczt3-chain {n2 n3}r5c7 - n3{r5c6 r4c5} - n2{r4c5 r4c3} ==> r5c2
<> 2
hxy-rn4-chain {c2 c6}r1n3 - {c6 c8}r1n4 - {c8 c3}r5n4 - {c3 c2}r5n7
==> r1c2 <> 7
nrc4-chain {n8 n2}r6c2 - n2{r6c7 r5c7} - n3{r5c7 r5c6} - n3{r1c6
r1c2} ==> r1c2 <> 8
nrc4-chain {n6 n3}r1c2 - {n3 n4}r1c6 - n4{r1c8 r5c8} - n6{r5c8 r4c8}
==> r4c2 <> 6
nrc3-chain n6{r4c1 r4c8} - {n6 n4}r5c8 - n4{r5c3 r4c1} ==> r4c1
<> 9
nrc4-chain n6{r4c1 r4c8} - {n6 n4}r5c8 - {n4 n5}r1c8 - n5{r2c7 r2c1}
==> r2c1 <> 6
nrc4-chain {n9 n2}r4c2 - n2{r6c2 r6c7} - {n2 n3}r5c7 - n3{r9c7 r9c2}
==> r9c2 <> 9
nrc4-chain {n9 n2}r4c2 - n2{r6c2 r6c7} - {n2 n3}r5c7 - n3{r5c6 r4c5}
==> r4c5 <> 9
row r4 interaction-with-block b4 ==> r5c3 <> 9, r5c2
<> 9
nrc3-chain {n2 n3}r4c5 - n3{r3c5 r1c6} - n4{r1c6 r2c5} ==> r2c5
<> 2, r2c5 <> 2
nrc4-chain n1{r7c2 r7c7} - {n1 n2}r6c7 - {n2 n3}r5c7 - n3{r9c7 r9c2}
==> r9c2 <> 1
hidden-single-in-a-block ==> r7c2 = 1
naked-triplets-in-a-column {n7 n9 n5}{r1 r2 r7}c7 ==> r9c7
<> 7
nrc3-chain n3{r8c9 r9c7} - {n3 n7}r9c2 - {n7 n6}r9c9 ==> r8c9
<> 6
hidden-single-in-a-block ==> r9c9 = 6
nrczt3-chain n3{r8c9 r9c7} - {n3 n7}r9c2 - n7{r7c1 r7c7} ==> r8c9
<> 7
block b9 interaction-with-row r7 ==> r7c1 <> 7
nrc3-chain {n8 n4}r7c1 - {n4 n5}r7c5 - n5{r6c5 r6c1} ==> r6c1
<> 8
naked-pairs-in-a-row {n5 n6}r6{c1 c5} ==> r6c6 <> 6
hxyzt4-rn-chain-type-1 {c3 c2}r5n7 - {c2 c4}r9n7 - {c4 c8}r9n5 - {c8
c3}r1n5 ==> r1c3 <> 7
nrc4-chain n7{r2c9 r7c9} - n8{r7c9 r8c9} - n3{r8c9 r8c1} - {n3
n7}r9c2 ==> r2c2 <> 7
nrc4-chain {n6 n5}r6c1 - n5{r6c5 r4c4} - n1{r4c4 r4c8} - n6{r4c8
r4c1} ==> r5c2 <> 6
column c2 interaction-with-block b1 ==> r1c1 <> 6
nrc3-chain n6{r1c4 r1c2} - n3{r1c2 r1c6} - n4{r1c6 r2c5} ==> r2c5
<> 6
xyzt4-chain {n7 n4}r2c9 - {n4 n5}r1c8 - {n5 n9}r2c7 - {n9 n7}r2c5
==> r2c4 <> 7
nrc4-chain n6{r1c4 r1c2} - n3{r1c2 r1c6} - n4{r1c6 r1c8} - {n4
n6}r5c8 ==> r5c4 <> 6
block b5 interaction-with-column c5 ==> r8c5 <> 6
hidden-pairs-in-a-block {n1 n6}{r8c4 r8c6} ==> r8c6 <> 9,
r8c4 <> 9, r8c4 <> 7
nrc3-chain n7{r8c5 r9c4} - n5{r9c4 r7c5} - n4{r7c5 r2c5} ==> r2c5
<> 7
row r2 interaction-with-block b3 ==> r1c7 <> 7
naked-single ==> r1c7 = 9
nrc2-chain n7{r8c5 r3c5} - n7{r1c4 r1c1} ==> r8c1 <> 7
column c1 interaction-with-block b1 ==> r3c3 <> 7
nrc3-chain {n8 n5}r1c3 - {n5 n4}r1c8 - n4{r5c8 r5c3} ==> r5c3
<> 8
block b4 interaction-with-column c2 ==> r2c2 <> 8
nrc3-chain n7{r1c1 r1c4} - n6{r1c4 r1c2} - n3{r1c2 r3c1} ==> r3c1
<> 7
hidden-single-in-a-block ==> r1c1 = 7
hidden-pairs-in-a-block {n5 n8}{r1c3 r2c1} ==> r2c1 <> 9
hidden-pairs-in-a-column {n3 n9}{r3 r8}c1 ==> r8c1 <> 8
xy3-chain {n7 n9}r8c5 - {n9 n3}r8c1 - {n3 n7}r9c2 ==> r9c4
<> 7
hidden singles ==> r8c5 = 7, r3c4 = 7
row r8 interaction-with-block b7 ==> r9c3 <> 9
xy3-chain {n9 n4}r2c5 - {n4 n5}r7c5 - {n5 n9}r9c4 ==> r2c4
<> 9
nrc3-chain {n8 n6}r1c4 - n6{r1c2 r2c2} - n2{r2c2 r2c4} ==> r2c4
<> 8
xy4-chain {n8 n7}r5c2 - {n7 n3}r9c2 - {n3 n6}r1c2 - {n6 n8}r1c4
==> r5c4 <> 8
…(NS+HS)…
765813942
821649537
349725681
692537814
174298365
583461279
416352798
958176423
237984156
A5) COMPLEX LEVEL EXAMPLE OF NRC(Z)(T) CHAINS
Here is now one of the most complex examples (Sudogen0 #707), where
each step is the direct application of one of these rules.
This example will also illustrate the nrc-notation.
Remember that, seen in rc-space:
- {n1 n2}rc means a bivalue cell
- n{r1c1 r2c2} means a conjugacy links for value n,
while all this merely means bivalue when seen in the proper rc-,
rn-; cn- or bn- space.
Remember also that, for chains with the t or z extensions, bivalue
and conjugacy are to be understood modulo the previous right linking
candidates (and modulo the target for z extensions).
400300608
005001030
016040007
070000080
000002000
051006370
002090800
000100000
000004009
naked and hidden singles ==> r6c5 = 8, r1c8 = 1, r3c1 = 3
r3 interaction with b2 ==> r2c4 <> 8
r1 interaction with b2 ==> r3c6 <> 5 , r3c4 <> 5
c2 interaction with b1 ==> r2c1 <> 2
naked-pairs-in-column {n2 n4}{r2 r6}c9 ==> r8c9 <> 4 , r8c9
<> 2, r7c9 <> 4 , r5c9 <> 4 , r4c9 <> 4 ,
r4c9 <> 2
nrczt3-chain n7{r5c5 r5c4} - n7{r2c4 r2c1} - n7{r7c1 r7c6} ==>
r8c5 <> n7, r9c4 <> n7, r9c5 <> n7
nrczt6-chain {n9 n2}r6c1 - n2{r4c1 r4c7} - n2{r6c9 r2c9} - n4{r2c9
r2c7} - n9{r2c7 r3c7} - n9{r3c8 r5c8} ==> r5c3 <> n9, r5c2
<> n9
nrczt6-chain {n9 n2}r6c1 - {n2 n6}r4c1 - {n6 n8}r5c1 - n9{r5c1 r4c3}
- {n9 n7}r1c3 - {n7 n9}r2c1 ==> r8c1 <> n9
nrczt6-chain {n9 n2}r6c1 - n2{r4c1 r4c7} - n2{r6c9 r2c9} - n4{r2c9
r2c7} - n9{r2c7 r3c7} - n9{r3c8 r5c8} ==> r5c1 <> n9
nrczt11-chain {n6 n8}r5c1 - n8{r2c1 r2c2} - {n8 n3}r9c2 - {n3
n4}r7c2 - {n4 n5}r7c8 - {n5 n7}r7c4 - n7{r5c4 r5c5} - n1{r5c5 r4c5}
- n3{r4c5 r8c5} - n3{r7c6 r7c9} - n1{r7c9 r7c1} ==> r7c1 <>
6
nrczt13-chain n9{r8c2 r8c3} - {n9 n7}r1c3 - {n7 n8}r9c3 - n8{r8c1
r8c6} - n7{r8c6 r7c6} - n3{r7c6 r7c9} - n1{r7c9 r9c7} - n7{r9c7
r8c7} - n4{r8c7 r8c8} - n2{r8c8 r8c5} - {n2 n5}r1c5 - n5{r1c6 r4c6}
- n3{r4c6 r8c6} ==> r8c2 <> 3
nrczt13-chain n6{r4c9 r4c1} - n2{r4c1 r4c7} - n2{r6c9 r2c9} -
n2{r3c8 r3c4} - n8{r3c4 n8r9c4} - n6{r9c4 r2c4} - {n6 n7}r2c5 -
n7{r2c1 r1c3} - {n7 n3}r9c3 - n3{r7c2 r7c6} - n7{r7c6 r8c6} -
n7{r8c7 r9c7} - n1{r9c7 r7c9} ==> r7c9 <> 6
nrczt13-chain n1{r9c1 r7c1} - n1{r7c9 r9c7} - n7{r9c7 r8c7} -
n7{r8c1 r2c1} - n8{r2c1 r2c2} - {n8 n3}r9c2 - {n3 n4}r7c2 - {n4
n9}r8c2 - {n9 n8}r8c3 - n4{r8c3 r8c8} - n2{r8c8 r8c5} - n6{r8c5
r8c9} - n6{r4c9 r4c1} ==> r9c1 <> 6
nrczt14-chain n7{r8c7 r9c7} - n1{r9c7 r7c9} - {n1 n5}r7c1 - n7{r7c1
r2c1} - {n7 n9}r1c3 - n9{r8c3 r8c2} - n4{r8c2 r7c2} - {n4 n6}r7c8 -
{n6 n7}r7c4 - n7{r5c4 r5c5} - n1{r5c5 r4c5} - n3{r4c5 r4c6} - {n3
n7}r7c6 - n7{r1c6 r8c6} ==> r8c3 <> 7
nrczt14-chain n8{r9c4 r8c6} - n8{r3c6 r3c4} - n2{r3c4 r2c4} -
n6{r2c4 r2c5} - n7{r2c5 r2c1} - n7{r1c3 r9c3} - n8{r9c3 r5c3} -
n8{r5c1 r9c1} - {n8 n3}r9c2 - n3{r5c2 r5c5} - n7{r5c5 r5c4} - {n7
n5}r7c4 - {n5 n2}r8c5 - {n2 n6}r9c5 ==> r9c4 <> 6
nrczt11-chain n3{r8c9 r7c9} - n1{r7c9 r9c7} - n7{r9c7 r8c7} -
n2{r8c7 r8c8} - n4{r8c8 r7c8} - {n4 n6}r7c2 - n6{r7c4 r9c5} - {n6
n5}r9c8 - n5{r3c8 r3c7} - n2{r3c7 r3c4} - n2{r9c4 r8c5} ==> r8c5
<> 3
nrczt7-chain n8{r9c4 r8c6} - n8{r8c3 r5c3} - n8{r5c1 r2c1} - n7{r2c1
r1c3} - n7{r1c6 r7c6} - n3{r7c6 r9c5} - {n3 n8}r9c3 ==> r9c2
<> 8
nrczt11-chain n7{r5c4 r5c5} - n1{r5c5 r4c5} - n3{r4c5 r9c5} - {n3
n6}r9c2 - n6{r9c5 r8c5} - n2{r8c5 r9c4} - {n2 n5}r9c8 - {n5 n3}r8c9
- {n3 n1}r7c9 - {n1 n5}r7c1 - {n5 n7}r7c6 ==> r7c4 <> 7
b8 interaction with c6 ==> r1c6 <> 7
nrct7-chain n7{r7c6 r7c1} - n7{r2c1 r1c3} - n7{r9c3 r9c7} - n7{r8c7
r8c6} - n8{r8c6 r9c4} - {n8 n3}r9c3 - n3{r9c5 r7c6} ==> r7c6
<> 5
nrct9-chain n7{r5c4 r2c4} - n7{r2c1 r1c3} - n7{r1c5 r5c5} - n1{r5c5
r4c5} - n3{r4c5 r9c5} - {n3 n8}r9c3 - n8{r9c4 r8c6} - {n8 n9}r3c6 -
n9{r3c8 r5c8} ==> r5c4 <> 9
r5 interaction with b6 ==> r4c7 <> 9
nrczt10-chain {n6 n5}r7c4 - {n5 n2}r8c5 - {n2 n7}r2c5 - n7{r2c1
r1c3} - {n7 n5}r1c5 - {n5 n9}r1c6 - {n9 n8}r3c6 - n8{r8c6 r9c4} -
{n8 n3}r9c3 - {n3 n6}r9c2 ==> r9c5 <> 6
nrczt10-chain {n5 n6}r7c4 - {n6 n2}r8c5 - {n2 n7}r1c5 - n7{r1c3
r9c3} - n7{r7c1 r7c6} - n3{r7c6 r8c6} - n3{r8c9 r7c9} - n1{r7c9
r9c7} - {n1 n8}r9c1 - {n8 n5}r9c4 ==> r9c5 <> 5
nrczt6-chain {n6 n3}r9c2 - {n3 n2}r9c5 - {n2 n5}r8c5 - {n5 n7}r1c5 -
{n7 n9}r1c3 - n9{r8c3 r8c2} ==> r8c2 <> 6
nrczt8-chain {n6 n3}r9c2 - {n3 n2}r9c5 - {n2 n5}r8c5 - {n5 n8}r9c4 -
{n8 n7}r9c3 - n7{r9c7 r8c7} - {n7 n3}r8c6 - {n3 n6}r8c9 ==> r8c1
<> 6
c1 interaction with b4 ==> r5c2 <> 6
nrczt9-chain {n2 n3}r9c5 - {n3 n6}r9c2 - {n6 n5}r9c8 - {n5 n8}r9c4 -
{n8 n7}r9c3 - {n7 n9}r1c3 - {n9 n9}r1c6 - {n5 n7}r8c6 - n7{r8c7
r9c7} ==> r9c7 <> 2
nrczt9-chain {n6r2c5 r2c4} - n7{r2c4 r2c1} - n7{r1c3 r9c3} - n7{r9c7
r8c7} - n2{r8c7 r8c8} - n4{r8c8 r7c8} - n6{r7c8 r7c2} - {n6 n3}r9c2
- {n3 n2}r9c5 ==> r2c5 <> 2
nrczt8-chain n6{r9c2 r7c2} - n6{r7c4 r2c4} - {n6 n7}r2c5 - n7{r2c1
r1c3} - {n7 n8}r9c3 - n8{r9c4 r8c6} - n7{r8c6 r7c6} - n3{r7c6 r9c5}
==> r9c2 <> 3
naked-single ==> r9c2 = 6
nrc2-chain n3{r9c5 r9c3} - n3{r7c2 r5c2} ==> r5c5 <> 3
r5 interaction with b4 ==> r4c3 <> 3
xy-wing {n4 n2}r6c9 - {n2 n9}r6c1 - {n9 n4}r4c3 ==> r4c7 <>
4
xyzt6-chain-type-3: on cells {n5 n2}r9c8 - {n2 n3}r9c5 - {n3 n7}r7c6
- {n7 n8}r8c6 - {n8 n9}r3c6 {n9 n5}r3c8 ==> r8c8 <> 5
nrczt6-chain n3r9c5, n2r9c5, n2r9c8, n5r9c8, n5r8c9, n6r8c9, n6r7c8,
n4r7c8, n4r7c2, n3r7c2, n3r7c9 and n3r8c9 ==> r8c6 <> 3
nrczt5-chain n3r8c9, n3r7c9, n1r7c9, n1r9c7, n7r9c7, n7r8c7, n7r8c6,
n8r8c6, n8r8c1 and n5r8c1 ==> r8c9 <> 5
nrczt7-chain n8{r3c4 r9c4} - n2{r9c4 r2c4} - n6{r2c4 r2c5} - n7{r2c5
r2c1} - n7{r7c1 r7c6} - {n7 n5}r8c6 - {n5 n9}r1c6 ==> r3c4
<> 9
nrczt7-chain n3{r4c6 r7c6} - n3{r9c5 r9c3} - n7{r9c3 r1c3} - n9{r1c3
r1c2} - n2{r1c2 r1c5} - {n2 n8}r3c4 - {n8 n9}r3c6 ==> r4c6
<> 9
number 9: c6 interaction with b2 ==> r2c4 <> 9
nrczt6-chain n1{r9c1 r9c7} - n7{r9c7 r9c3} - {n7 n9}r1c3 - n9{r1c6
r3c6} - n8{r3c6 r3c4} - n8{r9c4 r9c1} ==> r9c1 <> 5
nrct5-chain n9{r5c8 r3c8} - n5{r3c8 r3c7} - n2{r3c7 r3c4} - n8{r3c4
r9c4} - n5{r9c4 r9c8} ==> r5c8 <> 5
nrczt5-chain n5{r3c8 r3c7} - n5{r9c7 r9c4} - n8{r9c4 r3c4} - n2{r3c4
r3c8} - {n2 n5}r9c8 ==> r7c8 <> 5
xy-wing {n3 n6}r8c9 - {n6 n4}r7c8 - {n4 n3}r7c2 ==> r8c3 <>
3
hidden-single-in-row r8 ==> r8c9 = 3
column c9 interaction with block b6 ==> r5c8 <> 6
nrczt4-chain: n9{r1c6 r3c6} - n8{r3c6 r8c6} - {n8 n4}r8c3 - {n4
n9}r4c3 ==> r1c3 <> 9
naked-single ==> r1c3 = 7
hidden-pairs-in-row r2 {n6 n7} {c4 c5} ==> r2c4 <> 2
hidden-pairs-in-column {n2 n8}c4{r3 r9} ==> r9c4 <> 5
number 5: r9 interaction with b9 ==> r8c7 <> 5 , r7c9
<> 5
naked and hidden singles ==> r7c9 = 1, r9c1 = 1, r9c7 = 7, r9c8 =
5, r3c7 = 5
number 2: r9 interaction with b8 ==> r8c5 <> 2
naked-pairs-in-block {n5 n6}{r7c4 r8c5} ==> r8c6 <> 5
hidden-pairs-in-block {n5 n7}{r7c1 r8c1} ==> r8c1 <> 8
xy-wing {n2 n4}r6c9 - {n4 n9}r5c8 - {n9 n2}r3c8 ==> r2c9 <>
2
…(45 NS)…
427359618
895671234
316248597
274935186
638712945
951486372
742593861
589167423
163824759
Still more complex examples (with still longer chains) are available
in the whips page. But remember that such
puzzles are extremely rare.
A6) RESOLUTION TECHNIQUES
ASSOCIATED WITH THE NRC(Z)(T) RESOLUTION RULES
XY(Z)(T) COLOURING
With the nrc(z)(t)-chain resolution rules one can associate
resolution techniques (for this distinction, see the resolution rule page).
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 left 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.
NRC(Z)(T)-TAGGING
There are resolution rules, which are mathematical theorems in the
"condition-action" form; these theorems guarantee that asserting a
value or (more often) deleting of a candidate, is legitimate. As
such, resolution rules are invaluable: without them (or any other
form of formal theorem that might appear some day in their stead),
Sudoku can only be ad hoc reasoning; as I already said also, but it
is useful to repeat it, FOL is the ultimate scientifc form of this
rules, but most of the time, using the auxiliary predicates that I
have already be proven to be writtable as FOL formulæ, a non
ambiguous English formulation guarantees that they can be expressed
as resolution rules. There is another reason why resolution rules
are invaluable: only precise formulations of such rules allow to
prove subsumption relationships between different rules;
And there are resolution techniques associated with such rules,
whose purpose is to answer the practical question: how do we apply
the rules on a real grid, i.e. how do we find the patterns (defining
the condition part of a rule) on a real grid.
(There may also be resolution techniques that cannot be associated
with a resolution rule, such as T&E or tabling, but I'm not
considering them here).
As nrc-chains are "basic" AICs or "basic" NLs (viewed in a different
perspective), I'll skip this case.
Let me consider the case of the nrcz, nrct and nrczt chains.
Notice that the first methods defined below are the straightforward
transposition of the methods already introduced for xy(z)t chains
and are also no more than an expansion of a short section in the
introductory post. But nrc(z)(t) tagging is different.
Remember that I defined "nrc-conjugate" (or "nrc-bivalue", as you
prefer - in 3D space these concepts are equivalent) as ordinary
bivalue OR odinary bilocation.
Remember that an nrc(z)(t) chain is first a particular sequence of
2n candidates and that it can also be considered as a sequence of n
cells. As these chains are 3D generalisations of xy-chains, odd
candidates are named left-linking candidates, even candidates are
named right-linking candidates.
nrc(z)t chains can be found by using two different methods, which
both build the chain from first to last candidate and both start
with two candidates that are linked by an nrc-bivalue link. Let's
call these two candidates as the seed of the chain. In either
method, the chain is progressively extended to the right, in steps
that add two candidates. Suppose we already have an nrc(z)t chain on
2(n-1) candidates and let's try to extend it with two more
candidates.
For simplicity, in case we deal with an nrczt chain, suppose a
target candidate TC has been chosen.
First resolution technique: simple
arrows
Initialisation:
- initialise the procedure by drawing a red arrow between the first
and second candidates;
Next steps:
- find a candidate that is nrc-linked to candidate 2(n-1), it is the
new left-linking candidate;
- draw a blue arrow from candidate 2(n-1) to this new candidate;
- find a candidate that is nrc-conjugate with the previous one
modulo any previous right-linking (i.e. even) candidate in the chain
in case the t-extension is used and modulo TC in case the
z-extension is used); it is the new right-linking candidate; the
fact that this candidate is OK is checked on the fly, noting that
the previous right linking candidates are the arrival points of the
red arrows;
- draw a red arrow from candidate 2(n-1)+1 to this new candidate.
(in folk language, red arrows support "strong inferences" and blue
arrows support "weak" ones).
Second resolution technique:
nrc(z)(t) colouring
(This method was inspired by the xyt-colouring algorithm first
defined by John MacLeod to spot the xyt-chains, and corrected by me.
See above).
Initialisation:
In case the z-extension is used, the algorithm must be initialised
by colouring in blue any candidate that is nrc-linked to the target.
In case the t-extension is used, the algorithm must be initialised
by colouring in blue any candidate that is nrc-linked to the second
candidate. These two colouring processes must be combined for
nrczt-chains. The extension step is:
Next steps:
- find a candidate that is nrc-linked to candidate 2(n-1), it is the
new left-linking candidate; notice that colouring MUST NOT BE TAKEN
INTO ACCOUNT HERE (that was the bug in John's algorithm);
- draw an arrow from candidate 2(n-1) to this new candidate;
- find a candidate that is nrc-conjugate with the previous one
modulo any candidate already coloured in blue (i.e. ignore any blue
candidate); it is the new right-linking candidate;
- draw an arrow from candidate 2(n-1)+1 to this new candidate;
- colour in blue any candidate that is nrc-linked to this new
candidate.
Notice that, in either of these techniques, no value is tentatively
asserted and no candidate is tentatively eliminated (i.e. none of
these techniques introduces anything that could reasonably be called
T&E).
For either technique, after each such step,
- if the z-extension is used, eliminate TC if it linked to both
first and current last candidates; (things could be made a little
more general, but this is simpler for a beginner);
- if the z-extension is not used, eliminate any candidate that is
nrc-linked to both first and current last candidates.
What happens if?
- what happens if there is not target (or if the predefined target,
in case the z-exetension is used)? Answer: nothing happens. You may
continue extending your chain. BTW; if an elimination is done, you
may also continue extending your chain (except if the z-extension is
used: if TC is eliminated, there's no reason for wanting to
eliminate it again;)
- waht happens if, at some point, the extension step cannot be done?
First, this will occur mainly when looking for right linking
candidates - but that's a secondary matter. At the levl of the
values and the candidates present on the grid, NOTHING will happen.
As for ANY type of chain, you'll just have to find a better one. How
can this be done? The answer is very standard: go one step backwards
in the chain and try another extension. Here the two methods behave
very differently.
For the first method, you just have to erase the last arrow.
For the second method, you must erase all the colouring (and all the
arrows) and restart from nought. This is a debilitating point for
nrc(z)(t)-colouring.
Another technique for spotting
nrc(z)(t)-chains: nrc(z)(t) tagging
Can nrc(z)(t) colouring be saved? Answer: yes, by nrc(z)(t) tagging.
Choose a sequence of letters.
Follow the same procedure as for nrc(z)(t) colouring, but, instead
of colouring the candidates, tagg them with letters; a candidate
needs be tagged with only one letter (if it is already tagged, don't
tagg it again). Of course, in any new step of the technique
described above for colouring, the next letter in the sequence must
be used.
When you have to "backtrack" to the previous step, just erase the
instances of the last letter used.
A7) TWO EXAMPLES OF VERY LONG NRCZT CHAINS AND LASSOS
An nrczt-chain of length 25
The classification results in my previous post show that long chains
are very rarely useful.
But I've also been looking for cases for which they would be.
Until now, the longest nrczt-chain I had found in the Sudogen0
collection had length 13 (in puzzle Sudogen0-707, a very hard one).
In Ruud's top 10000, I had found one of length 17. As SudoRules had
chains programmed for lengths <= 20 (and, on any puzzle, it can
check that longer chains would be useless), I didn't care for
increasing this maximal length.
Nevertheless (in the little time I currently have for Sudoku), I
still tried to find longer nrczt-chains (or lassos).
I was naturally led to try the hardest puzzles and I came upon the
following monster, which rang the bell in SudoRules indicating that
longer chains might be useful for it. I therefore extended the
maximal length to 30.
The puzzle is the following - our friend EasterMonster, with the
additional value r4c8=7 (randomly chosen among the non nrczt
backdoors):
1.......2
.9.4...5.
..6...7..
.5.9.3.7.
....7....
...85..4.
7.....6..
.3...9.8.
..2.....1
The partial resolution path is:
hidden-single-in-a-column ==> r8c9 = 7
nrczt4-chain n2{r7c8 r8c7} - n2{r4c7 r4c1} - n2{r6c2 r6c6} - n2{r2c6
r2c5} ==> r7c5 <> 2
nrczt25-chain {n8 n6}r4c9 - n6{r5c8 r1c8} - {n6 n3}r2c9 - {n3
n9}r6c9 - {n9 n5}r5c9 - {n5 n4}r7c9 - n4{r3c9 r1c7} - n9{r1c7 r1c5}
- n9{r3c5 r3c8} - n9{r7c8 r7c3} - n9{r9c1 r9c7} - n5{r9c7 r8c7} -
n5{r8c3 r1c3} - n3{r1c3 r1c4} - n3{r3c5 r3c1} - n4{r3c1 r3c2} -
n2{r3c2 r2c1} - {n2 n6}r6c1 - {n6 n4}r8c1 - {n4 n1}r8c3 - {n1
n8}r7c2 - n8{r1c2 r2c3} - {n8 n4}r4c3 - n4{r4c5 r9c5} - n8{r9c5
r3c5} ==> r3c9 <> 8
Although the puzzle is not solved, this example is interesting for
several reasons:
- an nrczt25-chain appears immediately after an nrczt4, with nothing
of moderate complexity in between;
- after this, nothing else applies - and there's no possibility for
a longer nrczt-chain to appear;
- the computation time needed for finding this monster chain is much
shorter than that for some much shorter chains in other examples. I
think the reason is there are not many possibilities for building
each step in the chain, because when the elimination allowed by this
chain is done, the longest remaining partial chain has length 9.
This indicates how hard it may be to define a complexity measure for
chains.
An nrczt-lasso of length 28
In a previous post, I described an nrczt-chain of length 25. Here is
now an nrczt-lasso of length 28.
It is found in puzzle #3 in the magictour/top1465 collection.
I think this example is interesting for the same reasons as the
previous one:
- an nrczt28-lasso appears immediately after an nrczt11-chain and an
nrczt6-lasso, with nothing of moderate length in between;
- after this, nothing else (in my set of rules) applies - and
there's no possibility for a longer nrczt-chain to appear;
- the computation time needed for finding this monster chain is much
shorter than that for some much shorter chains (of length only 6 or
7) in other examples.
In particular, this confirms what was already hinted at in the
previous example: complexities of chains are not related to their
lengths in a systematic way but they largely depend on the
particularities of the puzzles. This makes somewhat hopeless any
effort to define an priori complexity measure for chains based on
the length.
The partial resolution path is:
(solve-nth-grid-from-text-file (str-cat ?*GridsDir*
"Magictour/magictour-top1465.txt") 3)
***** SudoRules version 13 *****
708000300000601000500000000040000026300080000000100090090200004000070500000000000
hidden-single-in-a-block ==> r6c9 = 3
row r2 interaction-with-block b3 ==> r3c9 <> 8, r3c8
<> 8, r3c7 <> 8, r3c9 <> 7, r3c8 <> 7, r3c7
<> 7
block b6 interaction-with-column c7 ==> r9c7 <> 8, r7c7
<> 8, r2c7 <> 8
block b6 interaction-with-row r5 ==> r5c6 <> 5, r5c4
<> 5, r5c3 <> 5, r5c2 <> 5
hidden-pairs-in-a-row {n7 n8}r3{c4 c6} ==> r3c6 <> 9, r3c6
<> 4, r3c6 <> 3, r3c6 <> 2, r3c4 <> 9, r3c4
<> 4, r3c4 <> 3
block b2 interaction-with-column c5 ==> r9c5 <> 3, r7c5
<> 3, r4c5 <> 3
nrczt4-chain n9{r2c1 r4c1} - {n9 n5}r4c5 - n5{r2c5 r2c8} - n8{r2c8
r2c9} ==> r2c9 <> 9
nrczt4-chain n6{r1c2 r3c3} - n6{r5c3 r5c6} - n6{r6c5 r7c5} - n6{r7c7
r9c7} ==> r9c2 <> 6
nrczt6-lr-lasso n7{r9c3 r9c2} - n7{r9c9 r2c9} - n8{r2c9 r2c8} -
n5{r2c8 r2c5} - {n5 n9}r4c5 - n9{r4c1 r4c3} ==> r5c3 <> 7
nrczt11-chain n6{r9c1 r6c1} - n6{r6c5 r9c5} - n1{r9c5 r7c5} - {n1
n8}r7c1 - n8{r4c1 r6c2} - n5{r6c2 r9c2} - n7{r9c2 r5c2} - n7{r9c2
r9c3} - n7{r9c9 r2c9} - n7{r2c8 r7c8} - {n7 n6}r7c7 ==> r7c3
<> 6
nrczt28-lr-lasso n5{r6c3 r4c3} - n5{r7c3 r7c5} - n1{r7c5 r9c5} -
n6{r9c5 r6c5} - n2{r6c5 r5c6} - n4{r5c6 r5c4} - n4{r6c6 r6c7} -
n8{r6c7 r4c7} - n1{r4c7 r4c1} - n9{r4c1 r2c1} - n9{r3c3 r5c3} -
n6{r5c3 r5c2} - n6{r1c2 r1c8} - n6{r3c7 r3c3} - n4{r3c3 r2c3} -
n4{r2c8 r3c8} - n4{r3c5 r1c5} - {n4 n9}r1c6 - {n9 n5}r1c4n5{r9c4
r9c2} - n7{r9c2 r6c2} - n8{r6c2 r8c2} - {n8 n6}r7c1 - n6{r7c7 r9c7}
- n9{r9c7 r3c7} - n2{r3c7 r2c7} - {n2 n1}r3c9 - {n1 n2}r1c9 ==>
r6c6 <> 5
GRID 3 NOT SOLVED. 62 VALUES MISSING.
ANOTHER EXAMPLE OF A HARD PUZZLE
Here is an interesting example noticed by Caravail, in the French
sudoku-factory forum, as one particularly hard among those with SER
= 9.0.
It is #25 in the sudocue top10000
....8....
..4..52..
.9...2..1
.8....5.7
.3..6.81.
7.1..8.9.
6..4...5.
..28..4..
....3....
I'll use it here to illustrate a few points about nrczt-chains and
lassos.
***** SudoRules version 13 *****
hidden-single-in-a-block ==> r1c9 = 5
At this point, the PM is:
c1
c2
c3
c4
c5
c6
c7
c8 c9
--------------------------------------------------------------------------------------------
r1 | 123 1267
367 | 13679
8 134679 |
3679 3467 5
|
r2 | 138 167
4 | 13679
179 5
| 2
3678 3689 |
r3 | 358
9 35678 |
367
47
2 |
367 34678 1
|
--------------------------------------------------------------------------------------------
r4 | 249
8
69 |
1239 1249 1349
| 5
2346 7 |
r5 | 2459
3 59
| 2579
6 479
| 8
1
24 |
r6 | 7
2456 1 |
235
245 8
| 36
9
2346 |
--------------------------------------------------------------------------------------------
r7 | 6
17 3789 |
4
1279 179 |
1379
5
2389 |
r8 | 1359 157
2 |
8
1579 1679 |
4
367 369 |
r9 | 14589 1457 5789 |
125679 3
1679 | 1679 2678
2689 |
---------------------------------------------------------------------------------------------
interaction column c9 with block b6 for number 4 ==> r4c8
<> 4
nrc2-chain n2{r4c8 r9c8} - n2{r9c4 r7c5} ==> r4c5 <> 2
nrczt2-chain n5{r8c2 r6c2} - n5{r6c5 r8c5} ==> r8c1 <> 5
At this point, the PM is:
Code:
c1
c2
c3
c4
c5
c6
c7
c8 c9
--------------------------------------------------------------------------------------------
r1 | 123 1267
367 | 13679
8 134679 |
3679 3467 5
|
r2 | 138 167
4 | 13679
179 5
| 2
3678 3689 |
r3 | 358
9 35678 |
367
47
2 |
367 34678 1
|
--------------------------------------------------------------------------------------------
r4 | 249
8
69 |
1239 149 1349
| 5 236
7 |
r5 | 2459
3 59
| 2579
6 479
| 8
1
24 |
r6 | 7
2456 1 |
235
245 8
| 36
9
2346 |
--------------------------------------------------------------------------------------------
r7 | 6
17 3789 |
4
1279 179 |
1379
5
2389 |
r8 | 139 157
2 |
8
1579 1679 |
4
367 369 |
r9 | 14589 1457 5789 |
125679 3
1679 | 1679 2678
2689 |
---------------------------------------------------------------------------------------------
We now have an example of an nrczt-lasso with an additional
z-candidate in its first cell. In full nrc-notation:
nrczt7-lr-lasso n6{r9 r1 r8*}c6 - n3{r1 r4}c6 - n4{r4 r5
r1#n6r1c6}c6 - n7r5{c6 c4} - n5{r5c4 r6c4 r5c6#n4r5c6} - n2{r6c4
r4c4 r5c4#n7r5c4} - {n2 n5 n4#n4r5c6}r6c5 ==> r9c4 <> 6
interaction column c4 with block b2 for number 6 ==> r1c6
<> 6
nrczt7-lr-lasso n4{r1c8 r1c6} - {n4 n7}r3c5 - n7{r3c3 r2c2} -
n7{r8c2 r8c6} - {n7 n9}r5c6 - {n9 n1}r7c6 - {n1 n7}r7c2 ==> r1c8
<> 7
nrczt7-lr-lasso n3{r1c6 r4c6} - n3{r6c4 r6c9} - n4{r6c9 r5c9} -
n4{r5c6 r1c6} - {n4 n6}r1c8 - {n6 n7}r3c7 - {n7 n4}r3c5 ==> r1c7
<> 3
;;; At this point, the PM is:
c1
c2
c3
c4
c5
c6
c7
c8 c9
--------------------------------------------------------------------------------------------
r1 | 123 1267
367 | 13679
8 134679 | 679
346 5
|
r2 | 138 167
4 | 13679
179 5
| 2
3678 3689 |
r3 | 358
9 35678 |
367
47
2 |
367 34678 1
|
--------------------------------------------------------------------------------------------
r4 | 249
8
69 |
1239 149 1349
| 5 236
7 |
r5 | 2459
3 59
| 2579
6 479
| 8
1
24 |
r6 | 7
2456 1 |
235
245 8
| 36
9
2346 |
--------------------------------------------------------------------------------------------
r7 | 6
17 3789 |
4
1279 179 |
1379
5
2389 |
r8 | 139 157
2 |
8
1579 1679 |
4
367 369 |
r9 | 14589 1457 5789 | 12579
3
1679 | 1679 2678
2689 |
---------------------------------------------------------------------------------------------
We now have 3 lassos with 3 targets (corresponding to the
eliminations at the end of the line) that can be factored into a
single lasso (a very rare case). Written in the full nrc notation:
nrczt7-rl-lasso n3{r1 r4}c6 - n4{r4 r5 r1*}c6 - {n4 n2}r5c9 - {n2 n6
n3#n3r4c6}r4c8 - n6r6{c9 c2 c7#n6r4c8} - n2{r6c2 r4c1 r5c1#n2r5c9} -
n4r4{c1 c6 c5#n4r5c6} ==> r1c6 <> 9, r1c6 <> 7, r1c6
<> 1
In such a factorisation, the * in cell 2 means that this additional
z-candidate is justified by any of the 3 targets
This is an rl-lasso and not a chain, becase the last right-linking
candidate n4r4c6 is nrc-linked to the first right-linking candidate
n3r4c6 and not to the target (to none of the targets)
;;; nothing special in the sequel:
nrczt5-chain n1{r7c6 r4c6} - n3{r4c6 r1c6} - n4{r1c6 r5c6} - {n4
n2}r5c9 - n2{r7c9 r7c5} ==> r7c5 <> 1
nrczt6-lr-lasso n6{r4c3 r4c8} - {n6 n3}r6c7 - {n3 n7}r3c7 - {n7
n3}r3c4 - {n3 n4}r1c6 - {n4 n7}r3c5 ==> r3c3 <> 6
nrczt6-chain n5{r3c3 r3c1} - n8{r3c1 r2c1} - n8{r3c3 r3c8} - n4{r3c8
r1c8} - {n4 n3}r1c6 - n3{r1c3 r3c3} ==> r3c3 <> 7
nrczt7-rl-lasso n1{r1c4 r2c5} - n1{r4c5 r4c6} - n3{r4c6 r1c6} -
n4{r1c6 r5c6} - n7{r5c6 r5c4} - n7{r1c4 r3c5} - n4{r3c5 r1c6} ==>
r9c4 <> 1
nrczt8-lr-lasso n2{r1c2 r6c2} - n6{r6c2 r4c3} - {n6 n3}r1c3 -
n3{r1c6 r4c6} - {n3 n5}r6c4 - n5{r9c4 r8c5} - n5{r8c2 r9c2} -
n4{r9c2 r6c2} ==> r1c2 <> 7
nrczt4-chain n7{r1c3 r2c2} - n6{r2c2 r1c2} - {n6 n4}r1c8 - {n4
n3}r1c6 ==> r1c3 <> 3
nrct4-chain n8{r7c9 r7c3} - n3{r7c3 r3c3} - n5{r3c3 r3c1} - n8{r3c1
r3c8} ==> r9c8 <> 8
interaction column c8 with block b3 for number 8 ==> r2c9
<> 8
nrczt5-chain {n7 n6}r1c3 - n6{r1c2 r6c2} - {n6 n3}r6c7 - n3{r7c7
r7c9} - n8{r7c9 r7c3} ==> r7c3 <> 7
nrczt6-chain {n6 n7}r1c3 - {n7 n9}r1c7 - {n9 n3}r2c9 - {n3 n7}r3c7 -
{n7 n4}r3c5 - n4{r3c8 r1c8} ==> r1c8 <> 6
naked-pairs-in-a-row {n3 n4}r1{c6 c8} ==> r1c4 <> 3, r1c1
<> 3
hidden-triplets-in-a-block {n3 n5 n8}{r2c1 r3c1 r3c3} ==> r2c1
<> 1
nrc4-chain n3{r1c6 r1c8} - n4{r1c8 r3c8} - n8{r3c8 r2c8} - {n8
n3}r2c1 ==> r2c4 <> 3
nrczt6-chain n6{r4c8 r4c3} - {n6 n7}r1c3 - {n7 n9}r1c7 - {n9 n3}r2c9
- {n3 n8}r2c1 - n8{r3c3 r3c8} ==> r3c8 <> 6
nrczt8-lr-lasso {n3 n6}r6c7 - n6{r3c7 r3c4} - n3{r3c4 r1c6} -
n4{r1c6 r3c5} - n4{r6c5 r6c2} - n6{r6c2 r4c3} - n6{r1c3 r1c2} -
n2{r1c2 r6c2} ==> r6c9 <> 3
nrczt4-chain n8{r7c9 r7c3} - n3{r7c3 r7c7} - n3{r6c7 r4c8} - n2{r4c8
r9c8} ==> r7c9 <> 2
hidden-single-in-a-row ==> r7c5 = 2
nrc3-chain n4{r9c2 r6c2} - {n4 n5}r6c5 - n5{r8c5 r8c2} ==> r9c2
<> 5
x-wing-in-columns n5{r6 r8}{c2 c5} ==> r6c4 <> 5
nrct4-chain n5{r9c4 r5c4} - {n5 n4}r6c5 - {n4 n7}r3c5 - n7{r3c4
r9c4} ==> r9c4 <> 9
nrczt5-lr-lasso n2{r1c2 r6c2} - {n2 n3}r6c4 - {n3 n6}r6c7 - n6{r6c2
r2c2} - n6{r2c9 r3c7} ==> r1c2 <> 1
nrczt6-rl-lasso n5{r8c2 r8c5} - {n5 n4}r6c5 - {n4 n7}r3c5 - n7{r2c5
r2c8} - n8{r2c8 r3c8} - n4{r3c8 r3c5} ==> r8c2 <> 7
nrct6-chain n5{r6c5 r5c4} - {n5 n7}r9c4 - n7{r8c6 r8c8} - n7{r7c7
r7c2} - n7{r2c2 r2c5} - {n7 n4}r3c5 ==> r6c5 <> 4
naked and hidden singles ==> r6c5 = 5, r9c4 = 5, r8c2 = 5
nrczt5-lr-lasso n4{r6c9 r6c2} - n2{r6c2 r1c2} - n6{r1c2 r2c2} -
n6{r6c2 r6c7} - n6{r3c7 r2c9} ==> r6c9 <> 2
nrc3-chain n2{r5c9 r4c8} - n3{r4c8 r6c7} - {n3 n2}r6c4 ==> r5c4
<> 2
nrczt5-lr-lasso n2{r4c4 r6c4} - n3{r6c4 r4c6} - n1{r4c6 r4c5} -
n4{r4c5 r5c6} - {n4 n3}r1c6 ==> r4c4 <> 9
nrczt6-lr-lasso n1{r8c6 r8c1} - n3{r8c1 r7c3} - n8{r7c3 r7c9} -
n9{r7c9 r7c7} - n9{r1c7 r1c4} - n1{r1c4 r1c1} ==> r7c6 <> 1
nrc5-chain n1{r7c7 r7c2} - n1{r2c2 r1c1} - n2{r1c1 r1c2} - n2{r6c2
r6c4} - n3{r6c4 r6c7} ==> r7c7 <> 3
hidden-pairs-in-a-row {n3 n8}r7{c3 c9} ==> r7c9 <> 9, r7c3
<> 9
nrct7-chain n4{r9c2 r6c2} - n4{r6c9 r5c9} - n2{r5c9 r9c9} - n2{r9c8
r4c8} - {n2 n9}r4c1 - n9{r5c3 r9c3} - n8{r9c3 r9c1} ==> r9c1
<> 4
naked and hidden singles ==> r9c2 = 4, r6c9 = 4, r5c9 = 2, r9c8 =
2
naked-pairs-in-a-column {n2 n6}{r1 r6}c2 ==> r2c2 <> 6
interaction block b1 with row r1 for number 6 ==> r1c7 <>
6, r1c4 <> 6
nrc4-chain {n9 n6}r4c3 - {n6 n7}r1c3 - {n7 n9}r1c7 - n9{r7c7 r7c6}
==> r4c6 <> 9
nrc4-chain n9{r1c7 r1c4} - n1{r1c4 r1c1} - n1{r2c2 r7c2} - n1{r7c7
r9c7} ==> r9c7 <> 9
nrct4-chain n6{r4c8 r6c7} - n3{r6c7 r3c7} - n3{r2c8 r2c1} - n8{r2c1
r2c8} ==> r2c8 <> 6
hxy-cn4-chain {r9 r1}c3n7 - {r1 r4}c3n6 - {r4 r8}c8n6 - {r8 r9}c6n6
==> r9c6 <> 7
nrc3-chain n7{r9c7 r9c3} - {n7 n1}r7c2 - n1{r7c7 r9c7} ==> r9c7
<> 6
hidden-pairs-in-a-column {n3 n6}{r3 r6}c7 ==> r3c7 <> 7
nrc5-chain n6{r9c6 r8c6} - n6{r8c8 r4c8} - n6{r4c3 r1c3} - n7{r1c3
r9c3} - {n7 n1}r9c7 ==> r9c6 <> 1
interaction block b8 with row r8 for number 1 ==> r8c1 <> 1
nrc5-chain {n9 n3}r8c1 - n3{r7c3 r3c3} - {n3 n6}r3c7 - n6{r6c7 r4c8}
- {n6 n9}r4c3 ==> r9c3 <> 9
interaction column c3 with block b4 for number 9 ==> r5c1
<> 9, r4c1 <> 9
nrc4-chain n7{r2c2 r1c3} - n6{r1c3 r4c3} - n9{r4c3 r5c3} - {n9
n7}r5c4 ==> r2c4 <> 7
nrc5-chain n1{r2c2 r1c1} - n2{r1c1 r1c2} - n6{r1c2 r6c2} - n6{r6c7
r3c7} - n6{r3c4 r2c4} ==> r2c4 <> 1
nrc3-chain n1{r4c4 r1c4} - {n1 n2}r1c1 - n2{r4c1 r4c4} ==> r4c4
<> 3
x-wing-in-columns n3{r3 r6}{c4 c7} ==> r3c8 <> 3, r3c3
<> 3
naked and hidden singles ==> r7c3 = 3, r8c1 = 9, r7c9 = 8
interaction block b8 with column c6 for number 9 ==> r5c6
<> 9
x-wing-in-columns n3{r3 r6}{c4 c7} ==> r3c1 <> 3
hidden-singles ==> r2c1 = 3, r8c9 = 3, r2c8 = 8
naked-pairs-in-a-row {n4 n7}r3{c5 c8} ==> r3c4 <> 7
naked-pairs-in-a-row {n6 n9}r2{c4 c9} ==> r2c5 <> 9
naked and hidden singles
GRID Puzzles/papyg/Caravail.sdk SOLVED. LEVEL = L8, MOST COMPLEX
RULE = NRCZT8
267183945
314975286
895642371
486291537
539764812
721358694
673429158
952817463
148536729
A8) NRCZT-CHAIN RULES vs
THE RULES IN MIKE BARKER'S SOLVER
<To be developed>
Recalling that both sets of rules can solve almost any minimal
random puzzle and about 97% of top 1465, we have:
- an example of a situation (obtained from puzzle #3 ) in which no
nrczt-chain can be found but Grouped NLs can,
- an example of a situation (obtained from puzzle #113 ) in which no
Grouped NL [subject to the restrictions on size you mentionned] can
be found but nrczt-chains can,
- an example of a situation (obtained from puzzle # 77) in which
none of these can be found.
A9) RESTRICTED FORMS OF NRC(Z)(T) CHAINS
If you consider the most general definition of an nrczt-chain, as
given at the top of this page, you will see that:
- two consecutive candidates are nrc-linked,
- candidates can be grouped by pairs inside 2D (rc-, rn-, cn- or
bn-) cells,
- each pair consists of a unique left-linking and a unique
right-linking candidate,
- in each of these 2D cells, there may be additional (t or z)
candidates.
In the most general definition, these additional candidates must be
nrc-linked to a previous right-linking candidate (t-extension) or to
the target (z-extension).
Now, it makes sense to restrict this definition to the following:
within each such 2D cell, each additional candidate must be linked,
WITHIN the subspace of this cell, to a previous right-linking
candidate (t-extension) or to the target (z-extension). Said
otherwise:
- if the cell is an rc-cell, then the link must be an rc-link;
- if it is an rn-cell, then it must be an rn-link;
- if it is a cn-cell, then it must be a cn-link;
- and if it is a bn-cell, then it must be a bn-link.
Thus, we get restricted nrc(z)(t) chains.
What's the point of this restriction?
- first, the Extended Sudoku Board can be used to look for these
chains: each next cell can easily be checked in either of the four
2D subspaces, with no need for checking additional candidates that
would be justified only by outer 3D links; the only places where you
may have to swap from one subboard to another is between the 2D
cells;
- second, there will be fewer restricted-nrczt-chains than
nrczt-chains. This is of course a disadvantage when a puzzle has few
chains. But it may be an advantage for puzzles that have so many
chains that it is hard to find them. Looking for restricted forms
may be a first step.
Of course, nrc(z)(t) chains admit still more restricted forms, which
I defined long ago: their pure 2D versions, yx(z)(t) and hxy(z)(t).
If you've been using the Extended Sudoku Board for finding the pure
2D versions, then you can still use it for finding the
restricted-nrczt-chains. It is therefore a good transition step.
Finally, how do restricted-nrczt-chains behave wrt to their global
resolution power? Well, as the full version, they can solve all the
puzzles in the Sudogen0 random collection of 10.000 minimal puzzles
- sometimes faster, sometimes slower because longer chains are
needed for the same puzzle.
WARNING: after several optimisations inSudoRules, the memory
overflow probelms have disappeared. Nevertheless, the restricted
form of nrc(z)(t) chains may still be useful for human players.
An example of how using restricted
forms of nrczt-chains can be helpful
Consider the following puzzle
.12...3..
...4...5.
6..3..2..
.....7..4
..3.1.6..
8..5.....
..7..4..2
.2...9...
..6...79.
This is puzzle "Extra252-hard", from papyg, here:
http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=836 (I've
already mentioned this French forum, where nrczt-chains are used
daily)
Its SER is 9.1
If I try to solve it with the most general nrczt-chains, I get a
memory overflow.
***** SudoRules version 13 *****
hidden-singles ==> r6c5 = 4, r8c7 = 4, r3c3 = 4, r1c8 = 4
interaction column c8 with block b9 for number 6 ==> r8c9
<> 6
interaction column c4 with block b8 for number 1 ==> r9c6
<> 1
naked-pairs-in-a-row {n1 n9}r6{c3 c7} ==> r6c9 <> 9, r6c9
<> 1, r6c8 <> 1, r6c2 <> 9
nrc2-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} ==> r8c9 <> 5
nrc2-chain n5{r7c7 r4c7} - n5{r4c3 r8c3} ==> r7c2 <> 5,
r7c1 <> 5
xyt4-chain {n9 n1}r6c7 - {n1 n9}r6c3 - {n9 n8}r2c3 - {n8 n9}r2c7
==> r4c7 <> 9
hxyt-cn4-chain {r7 r4}c7n5 - {r4 r8}c3n5 - {r8 r2}c3n8 - {r2 r7}c7n8
==> r7c7 <> 1
nrc4-chain n5{r8c3 r4c3} - n5{r4c7 r5c9} - n9{r5c9 r6c7} - n1{r6c7
r6c3} ==> r8c3 <> 1
interaction column c3 with block b4 for number 1 ==> r4c1
<> 1
nrct5-chain n3{r9c6 r6c6} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8
- {n8 n2}r5c6 ==> r9c6 <> 2
nrct5-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8
- {n8 n2}r5c6 ==> r4c5 <> 2
nrct5-chain n2{r4c1 r5c1} - n4{r5c1 r5c2} - n7{r5c2 r6c2} - n6{r6c2
r6c6} - n2{r6c6 r4c4} ==> r4c8 <> 2
nrct6-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} - n8{r8c3 r2c3} - n8{r2c7
r7c7} - n8{r7c2 r9c2} - n4{r9c2 r5c2} ==> r5c2 <> 5
nrct6-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8
- {n8 n2}r5c6 - {n2 n9}r5c4 ==> r4c5 <> 9
interaction column c5 with block b2 for number 9 ==> r1c4
<> 9
;;; example of a chain whose t- or z- candidates need nrc links:
nrczt6-chain n8{r2c3 r8c3} - n8{r9c2 r3c2} - n5{r3c2 r1c1} - n5{r9c1
r9c2} - n5{r9c6 r3c6} - n1{r3c6 r2c6} ==> r2c6 <> 8
nrczt7-chain n8{r2c3 r8c3} - n8{r7c2 r3c2} - n5{r3c2 r1c1} - n5{r8c1
r9c2} - n5{r9c6 r3c6} - n1{r3c6 r2c6} - n2{r2c6 r2c5} ==> r2c5
<> 8
nrczt7-lr-lasso {n8 n2}r5c6 - {n2 n7}r5c8 - {n7 n3}r6c9 - {n3
n1}r4c8 - n1{r6c7 r2c7} - {n1 n6}r2c6 - {n6 n2}r6c6 ==> r5c9
<> 8
nrczt8-chain n8{r2c3 r8c3} - n8{r9c2 r3c2} - n5{r3c2 r1c1} - n5{r9c1
r9c2} - n5{r9c6 r3c6} - n1{r3c6 r2c6} - n2{r2c6 r2c5} - n6{r2c5
r2c9} ==> r2c9 <> 8
;;; example of a chain whose t- or z- candidates need nrc links:
nrczt8-lr-lasso n3{r4c5 r4c8} - n3{r6c9 r9c9} - n5{r9c9 r5c9} -
n9{r5c9 r6c7} - n1{r6c7 r4c7} - {n1 n8}r2c7 - n8{r3c9 r8c9} -
n8{r8c3 r2c3} ==> r8c5 <> 3
nrczt9-lr-lasso n5{r3c2 r1c1} - n7{r1c1 r5c1} - n7{r5c8 r6c8} -
n2{r6c8 r6c6} - n2{r2c6 r2c5} - n7{r2c5 r2c9} - n6{r2c9 r2c6} - {n6
n8}r1c6 - {n8 n2}r5c6 ==> r3c2 <> 7
nrczt9-lr-lasso {n7 n3}r6c9 - {n3 n2}r6c8 - {n2 n8}r5c8 - {n8
n2}r5c6 - {n2 n6}r6c6 - n3{r6c6 r4c5} - {n3 n1}r4c8 - n1{r6c7 r2c7}
- {n1 n2}r2c6 ==> r5c9 <> 7
Memory overflow
Now, if Iuse the restricted version of nrczt-chains, I get the
solution:
***** SudoRules version 13 *****
hidden-singles ==> r6c5 = 4, r8c7 = 4, r3c3 = 4, r1c8 = 4
interaction column c8 with block b9 for number 6 ==> r8c9
<> 6
interaction column c4 with block b8 for number 1 ==> r9c6
<> 1
naked-pairs-in-a-row {n1 n9}r6{c3 c7} ==> r6c9 <> 9, r6c9
<> 1, r6c8 <> 1, r6c2 <> 9
nrc2-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} ==> r8c9 <> 5
nrc2-chain n5{r7c7 r4c7} - n5{r4c3 r8c3} ==> r7c2 <> 5,
r7c1 <> 5
xyt4-chain {n9 n1}r6c7 - {n1 n9}r6c3 - {n9 n8}r2c3 - {n8 n9}r2c7
==> r4c7 <> 9
hxyt-cn4-chain {r7 r4}c7n5 - {r4 r8}c3n5 - {r8 r2}c3n8 - {r2 r7}c7n8
==> r7c7 <> 1
nrc4-chain n5{r8c3 r4c3} - n5{r4c7 r5c9} - n9{r5c9 r6c7} - n1{r6c7
r6c3} ==> r8c3 <> 1
interaction column c3 with block b4 for number 1 ==> r4c1
<> 1
nrct5-chain n3{r9c6 r6c6} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8
- {n8 n2}r5c6 ==> r9c6 <> 2
nrct5-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8
- {n8 n2}r5c6 ==> r4c5 <> 2
nrct5-chain n2{r4c1 r5c1} - n4{r5c1 r5c2} - n7{r5c2 r6c2} - n6{r6c2
r6c6} - n2{r6c6 r6c8} ==> r4c8 <> 2
nrct6-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} - n8{r8c3 r2c3} - n8{r2c7
r7c7} - n8{r7c2 r9c2} - n4{r9c2 r5c2} ==> r5c2 <> 5
nrct6-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8
- {n8 n2}r5c6 - {n2 n9}r5c4 ==> r4c5 <> 9
interaction column c5 with block b2 for number 9 ==> r1c4
<> 9
;;; same path as above, downto this point
nrczt7-chain n8{r2c2 r3c2} - n8{r2c3 r8c3} - n5{r8c3 r4c3} - n5{r4c2
r9c2} - n5{r8c1 r8c5} - n5{r3c5 r3c6} - n1{r3c6 r2c6} ==> r2c6
<> 8; instead of an nrczt6-chain
nrczt7-chain n8{r2c2 r3c2} - n5{r3c2 r1c1} - {n5 n6}r1c6 - {n6
n7}r1c4 - n7{r8c4 r8c5} - n5{r8c5 r8c3} - n8{r8c3 r2c3} ==> r2c5
<> 8
nrczt7-lr-lasso {n8 n2}r5c6 - {n2 n7}r5c8 - {n7 n3}r6c9 - {n3
n1}r4c8 - n1{r6c7 r2c7} - {n1 n6}r2c6 - {n6 n2}r6c6 ==> r5c9
<> 8
nrczt9-rl-lasso n8{r2c2 r3c2} - {n8 n9}r2c3 - n9{r6c3 r6c7} - {n9
n1}r2c7 - n1{r2c6 r3c6} - n5{r3c6 r3c5} - n5{r3c2 r1c1} - n5{r8c1
r8c3} - n8{r8c3 r2c3} ==> r2c9 <> 8; instead of an
nrczt8-chain
;;; same eliminations as above, downto this point
nrczt9-lr-lasso {n7 n3}r6c9 - {n3 n2}r6c8 - {n2 n8}r5c8 - {n8
n2}r5c6 - {n2 n6}r6c6 - n3{r6c6 r4c5} - {n3 n1}r4c8 - n1{r6c7 r2c7}
- {n1 n2}r2c6 ==> r5c9 <> 7
;;; new eliminations:
nrczt10-lr-lasso n3{r9c6 r6c6} - n3{r4c5 r4c8} - {n3 n7}r6c9 -
n7{r5c8 r3c8} - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 - n2{r4c4
r9c4} - n1{r9c4 r9c9} - n1{r7c8 r8c8} ==> r9c1 <> 3
nrczt10-lr-lasso n7{r6c2 r5c1} - n7{r5c8 r6c8} - n2{r6c8 r6c6} -
n2{r2c6 r2c5} - n7{r2c5 r2c9} - n6{r2c9 r2c6} - n1{r2c6 r3c6} -
n5{r3c6 r3c5} - {n5 n8}r1c6 - {n8 n2}r5c6 ==> r3c2 <> 7
nrct11-chain n5{r7c7 r4c7} - n5{r5c9 r5c1} - n4{r5c1 r9c1} - n4{r9c2
r5c2} - n7{r5c2 r5c8} - n8{r5c8 r4c8} - {n8 n1}r3c8 - n1{r3c6 r2c6}
- n2{r2c6 r2c5} - n2{r9c5 r9c4} - n1{r9c4 r9c9} ==> r9c9 <>
5
naked and hidden singles ==> r7c7 = 5, r5c9 = 5, r6c7 = 9, r6c3 =
1
nrczt3-chain n8{r1c4 r1c9} - {n8 n1}r2c7 - n1{r2c6 r3c6} ==> r3c6
<> 8
nrczt7-chain n8{r2c7 r4c7} - n1{r4c7 r2c7} - {n1 n7}r3c8 - {n7
n2}r5c8 - n2{r6c8 r6c6} - {n2 n6}r2c6 - n6{r2c9 r1c9} ==> r1c9
<> 8
interaction row r1 with block b2 for number 8 ==> r3c5 <> 8
nrczt6-lr-lasso n3{r9c6 r6c6} - n3{r4c5 r4c8} - n1{r4c8 r4c7} -
n8{r4c7 r2c7} - n8{r2c3 r8c3} - n8{r8c9 r3c9} ==> r9c9 <> 3
nrc2-chain n3{r8c9 r6c9} - n3{r6c6 r4c5} ==> r8c5 <> 3
nrct6-chain n3{r9c6 r6c6} - n3{r6c9 r8c9} - n3{r7c8 r4c8} - n1{r4c8
r4c7} - {n1 n8}r2c7 - n8{r3c9 r9c9} ==> r9c6 <> 8
nrczt7-chain {n1 n8}r9c9 - {n8 n3}r8c9 - {n3 n5}r8c1 - n5{r1c1 r3c2}
- n8{r3c2 r3c8} - {n8 n1}r2c7 - n1{r4c7 r4c8} ==> r8c8 <> 1
nrczt7-lr-lasso n5{r3c5 r3c2} - n5{r3c6 r9c6} - n3{r9c6 r6c6} -
n3{r4c5 r4c8} - n1{r4c8 r4c7} - n8{r4c7 r2c7} - n8{r2c2 r2c3} ==>
r1c5 <> 5
nrczt5-chain n5{r1c1 r1c6} - n5{r3c5 r3c2} - n5{r9c2 r9c5} - n2{r9c5
r9c4} - n2{r4c4 r4c1} ==> r4c1 <> 5
nrc3-chain n5{r1c1 r3c2} - n5{r4c2 r4c3} - n9{r4c3 r2c3} ==> r1c1
<> 9
nrct4-chain {n9 n8}r2c3 - {n8 n5}r8c3 - n5{r9c1 r1c1} - {n5 n9}r3c2
==> r2c2 <> 9
nrct4-chain {n9 n8}r2c3 - {n8 n5}r8c3 - n5{r9c1 r1c1} - {n5 n9}r3c2
==> r2c1 <> 9
nrct6-chain n9{r2c3 r4c3} - n9{r4c4 r5c4} - n9{r5c1 r7c1} - {n9
n2}r4c1 - n2{r4c4 r9c4} - n2{r9c5 r2c5} ==> r2c5 <> 9
nrczt6-lr-lasso n8{r8c3 r2c3} - n8{r2c7 r4c7} - n8{r5c8 r5c6} -
n8{r1c6 r1c5} - n9{r1c5 r1c9} - n9{r2c9 r2c3} ==> r8c4 <> 8
nrct7-chain n3{r4c5 r6c6} - {n3 n5}r9c6 - n5{r1c6 r1c1} - n5{r3c2
r4c2} - n5{r4c3 r8c3} - n8{r8c3 r2c3} - n8{r2c7 r4c7} ==> r4c5
<> 8
nrczt7-rl-lasso n3{r4c5 r4c8} - n1{r4c8 r4c7} - n8{r4c7 r5c8} -
n8{r4c8 r4c4} - n8{r7c4 r7c2} - n8{r3c2 r3c9} - n8{r2c7 r4c7} ==>
r7c5 <> 3
interaction block b8 with row r9 for number 3 ==> r9c2 <> 3
nrczt7-lr-lasso {n1 n8}r2c7 - {n8 n7}r3c8 - {n7 n9}r3c9 - {n9
n5}r3c5 - n5{r1c6 r1c1} - n5{r8c1 r8c3} - n8{r8c3 r2c3} ==> r2c9
<> 1
nrc5-chain n3{r4c5 r9c5} - {n3 n5}r9c6 - {n5 n1}r3c6 - n1{r2c6 r2c7}
- n1{r4c7 r4c8} ==> r4c8 <> 3
hidden-singles ==> r4c5 = 3, r9c6 = 3
interaction column c6 with block b2 for number 5 ==> r3c5
<> 5
naked-pairs-in-a-block {n1 n8}{r4c7 r4c8} ==> r5c8 <> 8
interaction row r5 with block b5 for number 8 ==> r4c4 <> 8
nrc4-chain {n8 n1}r2c7 - n1{r2c6 r3c6} - n5{r3c6 r3c2} - n9{r3c2
r2c3} ==> r2c3 <> 8
naked-singles ==> r2c3 = 9, r4c3 = 5, r8c3 = 8
nrc3-chain {n7 n5}r1c1 - n5{r8c1 r8c5} - n7{r8c5 r8c4} ==> r1c4
<> 7
hidden-single-in-a-column ==> r8c4 = 7
nrc5-chain n1{r7c4 r9c4} - n2{r9c4 r9c5} - n2{r2c5 r2c6} - n1{r2c6
r2c7} - n1{r4c7 r4c8} ==> r7c8 <> 1
interaction block b9 with column c9 for number 1 ==> r3c9
<> 1
nrczt5-lr-lasso {n8 n1}r9c9 - {n1 n3}r8c9 - n3{r6c9 r6c8} - n2{r6c8
r6c6} - n2{r4c4 r5c4} ==> r9c4 <> 8
nrc6-chain {n7 n3}r2c1 - n3{r2c2 r7c2} - n9{r7c2 r7c1} - n1{r7c1
r7c4} - {n1 n2}r9c4 - n2{r9c5 r2c5} ==> r2c5 <> 7
hidden-pairs-in-a-block {n7 n9}{r1c5 r3c5} ==> r1c5 <> 8
interaction column c5 with block b8 for number 8 ==> r7c4
<> 8
hidden-pairs-in-a-block {n7 n9}{r1c5 r3c5} ==> r1c5 <> 6
nrc4-chain {n8 n5}r3c2 - {n5 n7}r1c1 - {n7 n9}r1c5 - n9{r3c5 r3c9}
==> r3c9 <> 8
hidden-singles ==> r9c9 = 8, r7c5 = 8, r8c9 = 1, r6c9 = 3
interaction column c9 with block b3 for number 7 ==> r3c8
<> 7
naked-triplets-in-a-column {n5 n7 n3}{r1 r2 r8}c1 ==> r9c1
<> 5, r7c1 <> 3, r5c1 <> 7
interaction column c1 with block b1 for number 7 ==> r2c2
<> 7
nrc3-chain n6{r2c5 r8c5} - n5{r8c5 r8c1} - n5{r1c1 r1c6} ==> r1c6
<> 6
xy4-chain {n6 n7}r2c9 - {n7 n3}r2c1 - {n3 n5}r8c1 - {n5 n6}r8c5
==> r2c5 <> 6
naked-singles
GRID papyg/Extra252-hard-mem-overflow.sdk SOLVED. LEVEL = L11, MOST
COMPLEX RULE = NRCT11
712895346
389426157
654371289
295637814
473918625
861542973
937184562
528769431
146253798
This may seem to be only an implementation problem of SudoRules, but
it is not. As SudoRules searches for shorter chains before longer
ones, memory overflow is directly related to the number of partial
chains one has to consider before eventually reaching a solution.
This puzzle belongs to the category of puzzles that have many
useless partial chains and for which the difficulty consists of
finding the useful ones. In such cases, using restricted forms of
chains may lead to an easier solution (but there's no guarantee that
it will always be the case).
(In the opposite case of puzzles that have few partial chains, one
could try to use more general chains. But, usable generalisations of
nrczt-chains, which are not overly general, are not yet obvious.)
Note: when I give a solution of a puzzle, I always use the
unrestricted version of nrczt-chains, unless otherwise stated.
Here is another interesting
example of using the restricted version of nrczt-chains.
I've recently fallen upon the following old diagonal pattern devised
by Ruud, at the bottom of this page: http://www.sudoku.com/boards/viewtopic.php?t=4212
Code:
X . . | X . . | X . .
. X . | . X . | . X .
. . X | . . X | . . X
------+------+------
X . . | X . . | X . .
. X . | . X . | . X .
. . X | . . X | . . X
------+------+------
X . . | X . . | X . .
. X . | . X . | . X .
. . X | . . X | . . X
Ruud also gives the following list of example puzzles:
Code:
000800400070020080006009003000700000030090040009006005800300700040060020003007006
200000100030000050001008002400100900060050080005002007600900800090070030008001000
000300700030020000009001006000100300080040010002005009900700400050080020000003007
100500400060010020008007000300600700010070090009002000600400900050080030003005006
700500000000010030001009005900800000050090070007004002200900400010050060008002003
400100200080040060005009008100000700040020080003007005200400000090080000008003000
800900700090040020002006009100000500020060010007003002300500400040070090000008001
200000800090080010001002007500200600070040030004001002300600700000030080009008005
200400500040060020001002000900500700080010060005009002700100000030090050008006004
200100300000050000006002005300200400090070050007008003800900700030010060001004008
100900300060010000004006005400700200010020030002009008200400900050000080009008001
200100300010030040004007001700800900080090030000003002900500600070060020001004008
400300500090050010002000009900200600060030020007006004600400200080070030000003005
000900500010070080005002006200700400050020090009006008700800900040030010003007004
600900700000060040003000009800300200020050090006008001200800900040020010008004005
000300900040070050005008000300400700060080010004005002200500000050010070006009008
700500000030090020001004007200100500050060090007000003900200100010000050004000008
800700500040080000003004007200300700000090080000000001300500400020060090005001008
800600400030020000002007001600900000040050070009000003100200800080000060007005004
900600500080090040003002006400900700020060050009008000700100300010040020000006000
500900100000010040003008005800400000060080070002005003600000800090000060004007002
100000000030040020005003000700200800040090070003008006200000500000060030006001008
600800200070060040002000001700000900090070060008005000100200300000040020003001005
900100200060000040001007009100300900050080000007009008500200300070040010000000006
400900800030080070000000000500300000020050010009004005700000600080020030002001004
300400600040020080005000009900100200000000050006003000000200400080070030001008005
900400100040010090006000004400600700090020030002008000200900000050030000007001008
100800300030050020004001008700400200040010060005008001000700600080000030002006005
He mentions that puzzles generated according to this pattern (i.e.
clues are allowed only where there is an x) seem to be harder than
average. Notice that, now, they are far from being among the known
hardest. But the pattern is still interesting.
I'ven't tried them systematically to check Ruud's conjecture, but #7
is an interesting example for the nrczt chain rules: it provides an
example with lassos of length 14 (the longest chains or lassos I
ever used to fully solve a puzzle). Due to a memory overflow problem
with their full version, the restricted version of nrczt-chains (as
defined a few posts above) is used.
Notice how hard it becomes almost from the beginning.
Code:
8 . . | 9 . . | 7 . .
. 9 . | . 4 . | . 2 .
. . 2 | . . 6 | . . 9
-----+-----+-----
1 . . | . . . | 5 . .
. 2 . | . 6 . | . 1 .
. . 7 | . . 3 | . . 2
-----+-----+-----
3 . . | 5 . . | 4 . .
. 4 . | . 7 . | . 9 .
. . . | . . 8 | . . 1
The SER is 9.2
***** SudoRules version 13 *****
800900700090040020002006009100000500020060010007003002300500400040070090000008001
hidden-singles ==> r9c4 = 4, r8c4 = 6, r4c4 = 2, r9c5 = 3
interaction row r9 with block b7 for number 9 ==> r7c3 <> 9
interaction row r7 with block b8 for number 2 ==> r8c6 <> 2
naked-single ==> r8c6 = 1
x-wing-in-rows n4{r3 r6}{c1 c8} ==> r5c1 <> 4, r4c8
<> 4, r1c8 <> 4
nrc3-chain n9{r6c7 r5c7} - {n9 n5}r5c1 - n5{r5c6 r6c5} ==> r6c5
<> 9
nrczt8-lr-lasso {n1 n8}r6c4 - n8{r2c4 r3c5} - {n8 n3}r3c7 - n3{r1c8
r4c8} - n8{r4c8 r7c8} - n7{r7c8 r9c8} - n5{r9c8 r8c9} - n3{r8c9
r8c7} ==> r3c4 <> 1
nrczt9-chain n9{r5c7 r6c7} - n9{r6c1 r9c1} - n2{r9c1 r9c7} - n6{r9c7
r2c7} - n6{r2c1 r6c1} - n4{r6c1 r3c1} - n7{r3c1 r2c1} - n7{r2c6
r4c6} - n4{r4c6 r5c6} ==> r5c6 <> 9
interaction block b5 with row r4 for number 9 ==> r4c3 <> 9
nrczt8-chain n9{r9c3 r5c3} - {n9 n5}r5c1 - n5{r8c1 r8c9} - n3{r8c9
r8c7} - {n3 n8}r5c7 - {n8 n7}r5c4 - n7{r4c6 r2c6} - n5{r2c6 r2c3}
==> r9c3 <> 5
nrczt13-lr-lasso n9{r9c3 r5c3} - n9{r6c1 r6c7} - n6{r6c7 r2c7} -
n6{r2c1 r6c1} - n4{r6c1 r4c3} - n4{r4c6 r5c6} - n5{r5c6 r6c5} -
n1{r6c5 r6c4} - n1{r2c4 r2c3} - n3{r2c3 r1c3} - n5{r1c3 r8c3} -
n5{r8c9 r9c8} - {n5 n3}r1c8 ==> r9c3 <> 6
naked-single ==> r9c3 = 9
nrczt14-rl-lasso n4{r6c8 r3c8} - n4{r3c1 r6c1} - n9{r6c1 r5c1} -
n9{r5c7 r6c7} - n6{r6c7 r6c2} - n5{r6c2 r6c5} - n5{r5c6 r5c3} - {n5
n8}r8c3 - {n8 n3}r4c3 - n3{r4c8 r1c8} - n3{r1c2 r3c2} - n5{r3c2
r3c1} - n5{r3c8 r9c8} - n5{r8c9 r8c3} ==> r6c8 <> 8
nrczt8-chain n3{r8c7 r8c9} - n5{r8c9 r9c8} - {n5 n6}r1c8 - {n6
n4}r6c8 - {n4 n8}r3c8 - {n8 n7}r3c4 - {n7 n5}r2c6 - {n5 n3}r2c9
==> r3c7 <> 3
nrczt6-chain n8{r4c2 r7c2} - n8{r7c8 r3c8} - {n8 n1}r3c7 - n1{r3c2
r1c2} - n1{r1c5 r6c5} - n8{r6c5 r4c5} ==> r4c3 <> 8
nrczt10-lr-lasso n4{r1c9 r1c3} - n4{r3c1 r3c8} - n3{r3c8 r4c8} -
n8{r4c8 r7c8} - n7{r7c8 r9c8} - n5{r9c8 r1c8} - n6{r1c8 r1c2} -
n3{r1c2 r3c2} - n7{r3c2 r7c2} - n1{r7c2 r1c2} ==> r1c9 <> 3
nrczt11-lr-lasso {n1 n8}r3c7 - {n8 n5}r3c5 - {n5 n7}r2c6 - n7{r3c4
r3c1} - n4{r3c1 r6c1} - n9{r6c1 r6c7} - {n9 n3}r5c7 - n3{r8c7 r8c9}
- n8{r8c9 r8c3} - {n8 n5}r5c3 - n5{r5c6 r1c6} ==> r3c2 <> 1
nrczt10-lr-lasso n4{r1c9 r1c3} - n4{r3c1 r3c8} - {n4 n6}r6c8 -
n6{r1c8 r1c2} - n1{r1c2 r2c3} - n3{r2c3 r3c2} - {n3 n8}r4c2 -
n8{r4c8 r7c8} - {n8 n6}r7c3 - n6{r4c3 r4c9} ==> r1c9 <> 5
nrczt10-chain n3{r8c7 r8c9} - n5{r8c9 r2c9} - {n5 n6}r1c8 - {n6
n4}r1c9 - {n4 n8}r3c8 - {n8 n1}r3c7 - {n1 n5}r3c5 - n5{r6c5 r5c6} -
n4{r5c6 r5c3} - n3{r5c3 r5c7} ==> r2c7 <> 3
nrczt6-chain {n8 n5}r8c3 - n5{r8c9 r2c9} - {n5 n7}r2c6 - {n7 n6}r2c1
- {n6 n1}r2c7 - {n1 n8}r3c7 ==> r8c7 <> 8
nrczt8-lr-lasso n8{r7c8 r8c9} - n5{r8c9 r2c9} - {n5 n7}r2c6 -
n7{r3c4 r5c4} - n8{r5c4 r5c7} - {n8 n1}r3c7 - {n1 n6}r2c7 - {n6
n5}r2c1 ==> r7c3 <> 8
nrczt9-chain n9{r6c7 r6c1} - {n9 n5}r5c1 - {n5 n2}r8c1 - n2{r9c1
r9c7} - n6{r9c7 r2c7} - n6{r2c1 r9c1} - {n6 n1}r7c3 - n1{r2c3 r2c4}
- {n1 n8}r6c4 ==> r6c7 <> 8
nrczt6-lr-lasso n8{r8c3 r8c9} - n3{r8c9 r8c7} - {n3 n9}r5c7 - {n9
n5}r5c1 - {n5 n6}r6c2 - {n6 n9}r6c7 ==> r5c3 <> 8
hidden-single-in-a-column ==> r8c3 = 8
nrczt8-chain n8{r2c9 r2c4} - n8{r2c7 r5c7} - {n8 n1}r3c7 - n1{r2c7
r2c3} - n3{r2c3 r2c9} - n3{r5c9 r5c3} - n5{r5c3 r1c3} - n5{r1c8
r3c8} ==> r3c8 <> 8
nrczt6-chain n8{r4c8 r7c8} - n7{r7c8 r9c8} - n7{r7c9 r7c2} - n1{r7c2
r1c2} - n3{r1c2 r3c2} - n3{r1c3 r1c8} ==> r4c8 <> 3
interaction column c8 with block b3 for number 3 ==> r2c9
<> 3
nrct4-chain n4{r3c1 r3c8} - n3{r3c8 r1c8} - n5{r1c8 r2c9} - n5{r8c9
r8c1} ==> r3c1 <> 5
nrczt4-chain n3{r2c4 r2c3} - n1{r2c3 r2c7} - {n1 n8}r3c7 - n8{r2c9
r2c4} ==> r2c4 <> 7
nrczt4-lr-lasso n3{r2c3 r2c4} - n1{r2c4 r2c7} - {n1 n8}r3c7 -
n8{r2c7 r2c9} ==> r2c3 <> 6, r2c3 <> 5
nrc2-chain n5{r6c5 r5c6} - n5{r5c3 r1c3} ==> r1c5 <> 5
nrc3-chain n5{r6c5 r3c5} - {n5 n2}r1c6 - {n2 n1}r1c5 ==> r6c5
<> 1
hidden-single-in-a-block ==> r6c4 = 1
nrczt3-chain n5{r8c1 r8c9} - n5{r2c9 r2c6} - n5{r5c6 r6c5} ==>
r6c1 <> 5
hidden-pairs-in-a-row {n5 n8}r6{c2 c5} ==> r6c2 <> 6
nrczt5-chain {n6 n1}r7c3 - n1{r7c2 r1c2} - {n1 n3}r2c3 - n3{r3c2
r4c2} - n6{r4c2 r7c2} ==> r9c1 <> 6
nrct5-chain n9{r5c1 r6c1} - n6{r6c1 r2c1} - n7{r2c1 r2c6} - n5{r2c6
r2c9} - n5{r8c9 r8c1} ==> r5c1 <> 5
naked and hidden singles ==> r5c1 = 9, r6c7 = 9
nrczt2-chain n6{r1c2 r2c1} - n6{r6c1 r6c8} ==> r1c8 <> 6
nrc3-chain n6{r9c7 r2c7} - n1{r2c7 r2c3} - {n1 n6}r7c3 ==> r9c2
<> 6
interaction row r9 with block b9 for number 6 ==> r7c9 <>
6, r7c8 <> 6
naked-pairs-in-a-block {n7 n8}{r7c8 r7c9} ==> r9c8 <> 7
interaction row r9 with block b7 for number 7 ==> r7c2 <> 7
hidden-pairs-in-a-column {n7 n8}{r4 r7}c8 ==> r4c8 <> 6
nrc2-chain n6{r2c1 r6c1} - n6{r6c8 r4c9} ==> r2c9 <> 6
nrc3-chain n1{r2c3 r2c7} - n6{r2c7 r1c9} - n4{r1c9 r1c3} ==> r1c3
<> 1
nrc3-chain n6{r1c9 r2c7} - n1{r2c7 r2c3} - {n1 n6}r7c3 ==> r1c3
<> 6
nrc3-chain n6{r1c2 r1c9} - n4{r1c9 r3c8} - n3{r3c8 r1c8} ==> r1c2
<> 3
nrc3-chain {n3 n5}r8c9 - {n5 n6}r9c8 - n6{r6c8 r4c9} ==> r4c9
<> 3
interaction row r4 with block b4 for number 3 ==> r5c3 <> 3
nrc4-chain n3{r5c9 r8c9} - n5{r8c9 r2c9} - {n5 n7}r2c6 - n7{r3c4
r5c4} ==> r5c9 <> 7
interaction row r5 with block b5 for number 7 ==> r4c6 <> 7
nrct4-chain n7{r5c4 r5c6} - {n7 n5}r2c6 - {n5 n8}r2c9 - n8{r3c7
r5c7} ==> r5c4 <> 8
naked and hidden singles ==> r5c4 = 7, r2c6 = 7
interaction column c4 with block b2 for number 8 ==> r3c5
<> 8
interaction row r5 with block , r7c8 = 8, r7c9 = 7
naked-pairs-in-a-block {n4 n6}{r4c9 r6c8} ==> r5c9 <> 4
x-wing-in-columns n5{r1 r5}{c3 c6} ==> r1c8 <> 5
naked-single ==> r1c8 = 3
naked-pairs-in-a-column {n4 n5}{r1 r5}c3 ==> r4c3 <> 4
x-wing-in-columns n5{r1 r5}{c3 c6} ==> r1c2 <> 5
naked-pairs-in-a-column {n1 n6}{r1 r7}c2 ==> r4c2 <> 6
x-wing-in-rows n5{r2 r8}{c1 c9} ==> r9c1 <> 5
xy3-chain {n6 n4}r1c9 - {n4 n5}r1c3 - {n5 n6}r2c1 ==> r2c7
<> 6
hidden-single-in-a-block ==> r1c9 = 6
naked-singles
GRID SOLVED. LEVEL = L14, MOST COMPLEX RULE = NRCZT14
814925736
693847125
752316849
136289574
925764318
487153962
361592487
548671293
279438651
NOTE : nrczt-chains and lassos have been subsumed under the concept
of nrczt-whips. For further examples of chains and lassos, see the whips page.
**************
B) GOING BEYOND THE
NRCZT-CHAINS?
nrczt chains are the most general first order chain pattern that can
lead to a contradiction on a given target. These chains are a very
powerful tool, as shown by the statistics I published above, but
(together with the standard basic rules) they still miss a few
puzzles (less than 1 in 10,000 minimal puzzles). (Remark: this was
before the introduction of whips).
Going beyond nrczt chains requires either considering chains of
subsets (e.g. based on ALS, thus moving to second order logic) or
embedding chains into nets (that require building several chains at
the same time) - two alternatives to which I'm personnally deeply
allergic when taken in their full generality, because they are very
likely to entail a priori exponential behaviour.
An alternative is better exploiting the partial occurrences of the
nrczt-chains themselves.
Somewhere above, I defined nrc(z)t lassos (which are partial
nrc(z)t-chains) and showed that they may shorten the lengths of the
nrc(z)t-chains required to solve a puzzle, thus allowing to solve
more puzzles in practice (see my examples for Ruud's top 10,000). As
lassos can be found at the same time as chains, looking for them
doesn't require much more work than looking only for chains. From
the resolution paths I published since I introduced lassos, you can
see that they now appear quite often (as often as chains). Even
though, in the post in which I introduced lassos, I considered them
as a minor improvement over chains, I have now re-assessed them as a
real improvement.
As shown by the easy to find very long nrczt-chains, the lengths of
chains is not the only (nor even the main) criterion of how hard it
is to find them. Indeed, there seems to be no a priori criterion
based on type and length. (Of course, for a given length, xy are
easier to find than nrc, which are easier to find than nrczt,… -
easier in a local sense, merely because, at each step, there are
fewer possible extensions of the partial chain under construction -
but they are not simpler in a global sense, because they may not be
powerful enough to lead to a solution).
Nevertheless, for a given partial chain, allowing an immediate
elimination because it is an nrczt-lasso is always simpler than
having to find an extension that makes it into a full nrczt-chain.
That's the a priori reason why lassos are an improvement and this is
confirmed in practice by the puzzles I could solve with them and
which required too much time or memory without them.
In the following post, I'll introduce another way of using partial
nrczt-chains for obtaining a contradiction: nrczt-bichains.
They rest on the general partial nrczt-chain theorem already
formulated in this thread, recalled here for convenience: if the
target was true, then any right-linking candidate would be true (and
any left-linking candidate would be false) - from which the full
nrczt-chains and nrczt-lassos theorems are straightforward.
B1) BEYOND NRCZT-CHAINS:
NRCZT-BICHAINS
Warning: this section is superseded by nrczt-braids.
nrczt-bichains are an obvious consequence of the general partial
nrczt-chain theorem recalled above and they are also an example of
mild nrczt-nets.
nrczt-bichain theorem:
consider two partial nrczt-chains built on the same target such that
none is an extension of the other. Then, if one right-linking
candidate n1r1c1 of one of these chains is nrc-linked to a
right-linking candidate n2r2c2 of the other, the common target can
be eliminated.
Proof (obvious): if the target was true, then (from the general
partial nrczt-chain theorem) both n1r1c1 and n2r2c2 would be true,
which would contradict their being nrc-linked.
Remarks:
- of course, if one or two of the chains are nrct instead of nrczt,
the theorem applies to any of their common targets; and it is also
true when considering the 2D counterparts of all these chains (xyt,
xyzt, hxyt, hxyzt);
- if we drop the condition on one chain not being an extension of
the other, the theorem remains valid, but we get a case of a mere
lr-lasso;
- the condition on the right-linking candidates being nrc-linked
could be extended to any more complex indirect contradiction between
them (but this would make the pattern harder to find);
- as for lassos, this result is very specific to the t-extension and
the non reversibility it induces (in the precise technical meaning
of "reversible" I've defined in the "concept of a resolution rule"
thread: http://www.sudoku.com/boards/viewtopic.php?t=5600); if
nrczt-chains were reversible, you'd just have to append the reversed
second chain to the first in order to get an ordinary nrczt-chain of
length the sum of the two lengths; there'd be no need for
considering two chains; that's why such a type of contradiction
cannot usefully be defined for reversible NLs or AICs;
- an nrczt-chain of length n=p+q ending with an nrc or nrcz part of
length q (i.e. a reversible part with no t-candidates) can always be
considered as an nrczt-bichain of length p+q; when short chains are
searched for before longer ones, such a bichain pattern could be
found before the corresponding nrczt-chain;
- it seems that most of the nrczt-bichains come from such instances
of longer splittable nrczt-chains.
As this pattern requires two nrczt chains, one of length p and one
of length q, I call it an nrczt-bichain of length (p, q), and I
write it as nrczt-bichain(p, q) in SudoRules output. By convention,
the first argument, p, is always the larger of p and q (any of them
if p=q).
Now, what's the complexity of this pattern compared to the
complexity of nrczt-chains? One might think that, given a maximal
length n for chains, if the compexity of finding chains of length
<= n is N, then the compexity of finding bichains with both
component chains of length <=n would be of order NxN. But this is
not the case, because of the constraint of starting with the same
target.
Unfortunately, as the question has already been evoked in several
posts, measuring the complexity of chain patterns (even the simpler
ones, such as xy-chains) is a very hard topic. This complexity
doesn't rely only (not even mainly) on the maximal length allowed
for the chains (a property independent of the puzzle) but also on
the number of subchains (a property largely dependent on the
puzzle); (see my examples of an nrczt25 chain and an nrczt28-lasso
in this thread).
The only thing I can say is that, for a given puzzle, introducing
bichains in my solver may increase the computation time (upto +50%
in the few cases I considered) but it may aslo drastically reduce it
if priorities are set properly (this is understandable in case there
are many long chains and the job done by some of them can be done by
the combination of two shorter ones). But this is not a valid
indication of the complexity for a human solver.
Moreover, the more valuable comparison may have to be between
nrczt-chains of length n and nrczt-bichains with all components of
length < n (or whose sum is n). Then , the memory required is
much less when bichains are allowed.
Remark: this notion is now subsumed by the concept of an nrczt-braid.
First example of bichains: a puzzle (Sudogen0-668) that can be
solved with either nrczt6-chains or with nrczt-chains of length
<=4 together with nrczt-bichains(p, q) with both p and q <= 4.
In SudoRules, the second solution is 2.5 times faster (which doesn't
entail it is easier to find for a human player).
This example also shows how the nrc-notation is extended to
bichains: each branch is preceded by "*-" recalling the link to the
target.
Notice that any such comparison relies on the choice of an ordering
of the rules. Here, for illustration purposes, all nrczt-bichains(p,
q) have been given priority lower than nrczt-chains of length p but
higher than any other chains of length > p. Moreover, for fixed
p, nrczt-bichains(p, q) have been given higher priority than
nrczt-bichains(p, q+1).
I'm still thinking of a better classification of bichains.
1) Initial part, common to the two resolution paths:
Code:
***** SudoRules version 13 *****
.9...5.6...7..238............3.5..18....3.45.48.6.......9..48...1.7......2..1.9..
hidden singles ==> r4c4 = 4, r6c3 = 5, r6c6 = 1, r7c9 = 1
column c2 interaction-with-block b1 ==> r3c3 <> 4, r1c3
<> 4
naked-pairs-in-a-column {n6 n7}{r4 r5}c2 ==> r7c2 <> 7
column c2 interaction-with-block b4 ==> r5c1 <> 7, r4c1
<> 7
naked-pairs-in-a-column {n6 n7}{r4 r5}c2 ==> r7c2 <> 6,
r3c2 <> 6, r2c2 <> 6
column c2 interaction-with-block b4 ==> r5c3 <> 6, r5c1
<> 6, r4c1 <> 6
x-wing-in-rows n6{r2 r7}{c1 c5} ==> r9c1 <> 6, r8c5
<> 6, r8c1 <> 6, r3c5 <> 6, r3c1 <> 6
nrc2-chain n3{r1c4 r1c1} - n3{r3c2 r7c2} ==> r7c4 <> 3
nrc3-chain n6{r5c9 r4c7} - n2{r4c7 r4c1} - n9{r4c1 r5c1} ==> r5c9
<> 9
block b6 interaction-with-row r6 ==> r6c5 <> 9
naked-pairs-in-a-row {n2 n7}r6{c5 c7} ==> r6c9 <> 7, r6c9
<> 2, r6c8 <> 7, r6c8 <> 2
nrczt2-chain n7{r6c7 r6c5} - n7{r1c5 r1c9} ==> r3c7 <> 7
nrc3-chain {n2 n7}r6c5 - {n7 n9}r4c6 - n9{r8c6 r8c5} ==> r8c5
<> 2
row r8 interaction-with-block b9 ==> r7c8 <> 2
nrc3-chain {n5 n3}r7c2 - {n3 n7}r7c8 - n7{r7c1 r9c1} ==> r9c1
<> 5
nrc4-chain n6{r3c6 r2c5} - {n6 n2}r7c5 - n2{r6c5 r5c4} - n8{r5c4
r5c6} ==> r3c6 <> 8
nrc4-chain n6{r3c6 r2c5} - {n6 n2}r7c5 - {n2 n7}r6c5 - {n7 n9}r4c6
==> r3c6 <> 9
nrct4-chain {n1 n2}r5c3 - n2{r4c1 r4c7} - {n2 n7}r6c7 - {n7 n1}r1c7
==> r1c3 <> 1
nrct4-chain n6{r2c1 r7c1} - n7{r7c1 r7c8} - n3{r7c8 r7c2} - n5{r7c2
r8c1} ==> r2c1 <> 5
nrczt4-chain n6{r8c9 r9c9} - n5{r9c9 r9c4} - {n5 n2}r7c4 - {n2
n6}r7c5 ==> r8c6 <> 6
nrczt4-lr-lasso n6{r3c6 r9c6} - {n6 n2}r7c5 - {n2 n7}r6c5 - n7{r1c5
r3c5} ==> r3c6 <> 3
column c6 interaction-with-block b8 ==> r9c4 <> 3
2) Continuation of the resolution path with nrczt6-chains:
Code:
nrczt5-chain {n8 n5}r9c4 - {n5 n2}r7c4 - {n2 n6}r7c5 - n6{r7c1 r8c3}
- n4{r8c3 r9c3} ==> r9c3 <> 8
nrc6-chain {n7 n2}r6c7 - n2{r6c5 r7c5} - {n2 n5}r7c4 - n5{r9c4 r9c9}
- n5{r8c7 r3c7} - n1{r3c7 r1c7} ==> r1c7 <> 7
column c7 interaction-with-block b6 ==> r5c9 <> 7
hidden-pairs-in-a-row {n4 n7}r1{c5 c9} ==> r1c9 <> 2
hidden-pairs-in-a-row {n4 n7}r1{c5 c9} ==> r1c5 <> 8
nrczt2-chain n2{r1c3 r1c7} - n2{r4c7 r4c1} ==> r3c1 <> 2
nrczt2-chain n8{r3c5 r8c5} - n8{r8c3 r1c3} ==> r3c1 <> 8
nrc5-chain {n1 n2}r1c7 - n2{r6c7 r6c5} - {n2 n6}r7c5 - n6{r2c5 r2c1}
- n1{r2c1 r2c4} ==> r1c4 <> 1
nrczt5-lr-lasso {n3 n8}r1c4 - n8{r3c5 r8c5} - {n8 n5}r8c1 - n5{r7c2
r7c4} - {n5 n8}r9c4 ==> r1c1 <> 3
hidden-single-in-a-row ==> r1c4 = 3
row r1 interaction-with-block b1 ==> r3c3 <> 8
hidden-triplets-in-a-block {n3 n4 n5}{r3c1 r3c2 r2c2} ==> r3c1
<> 1
nrczt6-chain n2{r4c7 r5c9} - {n2 n1}r5c3 - {n1 n6}r3c3 - n6{r3c6
r9c6} - {n6 n2}r7c5 - n2{r6c5 r6c7} ==> r3c7 <> 2
nrczt6-chain n2{r4c1 r4c7} - {n2 n1}r1c7 - n1{r1c1 r2c1} - n6{r2c1
r7c1} - {n6 n2}r7c5 - n2{r7c4 r5c4} ==> r5c1 <> 2
nrczt6-lr-lasso {n5 n1}r3c7 - n1{r1c7 r1c1} - n1{r2c1 r2c4} -
n9{r2c4 r2c5} - n9{r3c4 r5c4} - {n9 n1}r5c1 ==> r2c9 <> 5
naked and hidden singles ==> r2c2 = 5, r3c1 = 3, r3c2 = 4, r7c2 =
3, r7c8 = 7, r9c1 = 7
row r9 interaction-with-block b8 ==> r8c6 <> 8, r8c5
<> 8
naked and hidden singles ==> r8c5 = 9, r8c6 = 3, r3c5 = 8
column c6 interaction-with-block b5 ==> r5c4 <> 9, r9c9
<> 4, r8c9 <> 4
xy3-chain {n1 n9}r3c4 - {n9 n2}r3c8 - {n2 n1}r1c7 ==> r3c7
<> 1
naked and hidden singles ==> r3c7 = 5, r1c7 = 1
row r1 interaction-with-block b1 ==> r3c3 <> 2
nrc4-chain {n6 n2}r5c9 - n2{r5c4 r7c4} - n5{r7c4 r7c1} - n5{r8c1
r8c9} ==> r8c9 <> 6
nrc4-chain n2{r5c3 r1c3} - n8{r1c3 r8c3} - n6{r8c3 r8c7} - n6{r9c9
r5c9} ==> r5c9 <> 2
naked and hidden singles ==> r5c9 = 6, r5c2 = 7, r4c2 = 6, r8c7 =
6
xy5-chain {n4 n6}r9c3 - {n6 n1}r3c3 - {n1 n9}r3c4 - {n9 n2}r3c8 -
{n2 n4}r8c8 ==> r9c8 <> 4
...(naked singles)...
GRID 668 SOLVED IN CONTEXT cont-0, AT DEPTH 0. MAX-DEPTH = 0. LEVEL
= L6, MOST COMPLEX RULE = NRCZT6
892345167
157962384
346187529
263459718
971238456
485671293
639524871
518793642
724816935
3) Continuation of the resolution path with nrczt chains and
bichains with components of length <= 4
In this part of the path, I've used the strict nrc notation (ie. all
the additional candidates havebeen displayed), in order to show that
all the bichains could be recast as pure nrczt-chains.
Code:
;;; the first bichain is just another view of the first nrczt5-chain
in the previous resolution path:
nrczt-bichain-3+2
*- {n8 n5}r9c4 - {n5 n2}r7c4 - {n2 n6}r7c5
*- n4{r9c3 r8c3} - n6{r8c3 r7c1 r9c3*}
==> r9c3
<> 8
;;; this is equivalent to an nrczt6-chain:
nrczt-bichain-3+3
*- n8{r5c4 r5c6} - n8{r9c6 r9c1} - n7{r9c1 r7c1}
*- n3{r1c4 r3c4} - n3{r3c2 r7c2} - {n3 n7}r7c8
==> r1c4
<> 8
;;; this is equivalent to an nrczt6-chain:
nrczt-bichain-3+3
*- n1{r1c7 r3c7} - n5{r3c7 r8c7} - n5{r9c9 r9c4}
*- {n7 n2}r6c7 - n2{r6c5 r5c4} - {n2 n5}r7c4
==> r1c7 <> 7
column c7 interaction-with-block b6 ==> r5c9 <> 7
hidden-pairs-in-a-row {n4 n7}r1{c5 c9} ==> r1c9 <> 2, r1c5
<> 8
row r1 interaction-with-block b1 ==> r3c3 <> 8, r3c1
<> 8
nrczt2-chain n2{r1c3 r1c7} - n2{r4c7 r4c1} ==> r3c1 <> 2
nrczt4-chain {n1 n6}r2c1 - {n6 n2}r3c3 - n2{r1c1 r1c7} - n1{r1c7
r3c7} ==> r3c1 <> 1
naked-triplets-in-a-block {n4 n5 n3}{r2c2 r3c1 r3c2} ==> r1c1
<> 3
naked and hidden singles ==> r1c4 = 3
;;; this is equivalent to an nrcz6-chain:
nrcz-bichain(3, 3)
*- n2{r4c1 r4c7} - {n2 n1}r1c7 - n1{r1c1 r2c1 n1r5c1*}
*- n2{r5c4 r6c5} - {n2 n6}r7c5 - n6{r2c5 r2c1}
==> r5c1
<> 2
;;; this is equivalent to an nrczt6-chain
nrczt-bichain(3, 3)
*- n2{r4c7 r5c9 r6c7*} - {n2 n1}r5c3 - {n1 n6 n2*}r3c3
*- n2{r6c7 r6c5} - {n2 n6}r7c5 - n6{r9c6 r3c6
r8c6#n6r7c5}
==> r3c7
<> 2
;;; this is equivalent to an nrczt7-chain:
nrczt-bichain(4,3)
*- {n5 n1}r3c7 - n1{r3c4 r2c4} - n9{r2c4 r2c5 r2c9*} -
n9{r3c4 r5c4 r2c4#n9r2c5}
*- {n5 n1}r3c7 - n1{r3c3 r5c3} - {n1 n9}r5c1
==>
r2c9 <> 5
naked and hidden singles ==> r2c2 = 5, r3c1 = 3, r3c2 = 4, r7c2 =
3, r7c8 = 7, r9c1 = 7
row r9 interaction-with-block b8 ==> r8c6 <> 8, r8c5
<> 8
naked and hidden singles ==> r8c5 = 9, r8c6 = 3, r3c5 = 8
column c6 interaction-with-block b5 ==> r5c4 <> 9, r9c9
<> 4, r8c9 <> 4
xy3-chain {n1 n9}r3c4 - {n9 n2}r3c8 - {n2 n1}r1c7 ==> r3c7
<> 1
naked and hidden singles ==> r3c7 = 5, r1c7 = 1
row r1 interaction-with-block b1 ==> r3c3 <> 2
nrc4-chain {n6 n2}r5c9 - n2{r5c4 r7c4} - n5{r7c4 r7c1} - n5{r8c1
r8c9} ==> r8c9 <> 6
nrc4-chain n2{r5c3 r1c3} - n8{r1c3 r8c3} - n6{r8c3 r8c7} - n6{r9c9
r5c9} ==> r5c9 <> 2
naked and hidden singles ==> r5c9 = 6, r5c2 = 7, r4c2 = 6, r8c7 =
6
;;; this is equivalent to an nrczt5-chain:
nrczt-bichain(3, 2)
*- {n2 n5}r8c9 - n5{r8c1 r7c1} - n6{r7c1 r9c3}
*- n7{r3c9 r3c6} - n6{r3c6 r3c3}
==> r3c9
<> 2
...(naked and hidden singles)...
GRID 668 SOLVED IN CONTEXT cont-0, AT DEPTH 0. MAX-DEPTH = 0. LEVEL
= L4, MOST COMPLEX RULE = NRCZT-BICHAIN(4, 3)
892345167
157962384
346187529
263459718
971238456
485671293
639524871
518793642
724816935
B2) BEYOND NRCZT-CHAINS: GROUPED-NRCZT-CHAINS
As I mentioned in a previous post, nrczt-chains (and lassos) are the
most general first order chain structure and they are enough
(together with the basic naked, hidden and super-hidden subset
rules) for solving 99.99% of the minimal puzzles. (We now know from
my second previous post that nrczt-chains subsume basic interaction
rules, so that, from a theoretical POV, we can forget these rules;
remember that they also subsume most but not all cases of the subset
rules).
I've also mentioned several times that there are two kinds of
obstructions to the possibility of solving a given puzzle based only
on nrczt-chains (and the basic subset rules above) and that these
obstructions are opposite to each other.
1) There may be too many partial chains and the useful ones are
hidden among the useless ones. We can call this the problem of the
the needle in the haystack. This is a problem for the human solver
and for the computer as well. The approach I've always had wrt to
this problem is using special cases of the most general 3D rules,
e.g. their 2D counterparts or the restricted versions of nrc(z)(t)
chains I've introduced recently. Notice that this is only a
practical problem that doesn't limit the generality of nrczt-chains.
2) There may be too few partial chains. This is a fundamental
problem, associated with the fact that there are very rare puzzles
that can't be solved using only nrczt-chains (together with the
basic subset rules above). The solution is obvioulsy to be found in
the definition of more general patterns.
Considering now this second obstruction, one can consider several
proposals (second order rules, ..., including my own nrczt-nets),
which all ignore the basic Occam's razor principle I've constantly
followed until now in my basically player oriented (although
theoretically grounded) approach: don't introduce unnecessarily
complex patterns.
What then is a good generalisation of nrczt-chains? After trying a
few possibilities, I've come to the conclusion that
grouped-nrczt-chains could be an answer.
Notice that grouped-nrczt-chains are not chains in the sense I
defined (a sequence of candidates). They are nets, but a very mild
kind of nets, in which bifurcations are the most local one can
imagine: they can occur only from a left-linking candidate and must
be resorbed by the next left-linking candidates.
Of course, one may wonder: is such a limited generalisation powerful
enough?
We'll have to consider non-empty subsets of candidates based on the
same number and whose rc-support is included in a segment (a segment
is the intersection of a row or a column with a block); call them
g-candidates; we accept subsets of cardinal 1 and identify them with
ordinary candidates.
The nrc-linked relation, already defined between 2 candidates, is
extended to g-candidates:
Definition: 2 g-candidates are nrc-linked if any candidate belonging
to one of the 2 g-candidates is nrc-linked in the already defined
sense to any candidate belonging to the other g-candidate.
The "nrc-conjugacy relation in a given nrc-unit U (cell, row, column
or block) modulo something", already defined between 2 candidates,
is extended in the following sense:
Definition: given a set S of g-candidates, a candidate n1r1c1 and a
g-candidate {n2r2c2, n'2r'2c'2,..} are nrc-conjugate modulo S if
they do not intersect any element of S, they are nrc-linked and:
- either all of n1, n2, n'2, ... are different, (r1, c1) and all the
(r2, c2), (r'2, c'2),.. are the same rc-cell, and the only
candidates for this cell are n1, n2, n'2 and possibly any other
value n such that (n, r1, c1) is nrc-linked to an element of S (in
the extended sense),
- or n1=n2=n'2=..., (r1, c1), (r2, c2), (r'2, c'2),... are different
rc-cells in the same row [or column or block] and, in this row [or
column or block], n1 appears only in n1r1c1, n1r2c2, n1r'2c'2,...,
or in cells (r, c) such that n1rc is nrc-linked to an element of S
(in the extended sense).
Definition of a grouped-nrczt-chain: take the definition of an
nrczt-chain and modify it as follows:
- instead of being a candidate, a right-linking candidate can be a
g-candidate,
- the nrc-linked relation between successive elements of the
grouped-chain must be understood in the extended sense above,
- the nrc-conjugate modulo... relation between left and
right-linking elements of the chain must be understood in the
extended sense above
Remarks:
1) we could have allowed g-candidates in the left-linking
candidates. This wouldn't provide any generalisation, but only a
grouping of "equivalent" grouped-nrczt-chains.
2) notice that groups of candidates are very far from being any
subset: they correspond to "definable formulæ" of first order
logic, and grouped-nrczt-chains, although not pure chains, remain
first order patterns;
3) this notion of group corresponds to that used in the context of
AICs or NLs.
Preliminary results:
Until now, grouped nrczt-chains have been implemented only very
partially in SudoRules. The problem is, I thought it'd be a limited
generalisation, but it proves to be a very big one. And I get so
many partial grouped-chains that I run into memory overflow before I
can get any interesting result. (I've not spent much time optimising
my implementation and this might change in an undefined future).
As an example, consider EasterMonster, already known for not having
enough nrczt-chains. At the start, there are:
- 28 nrc-bivalue relations
- 458 partial nrczt1 chains
- 3149 partial grouped-nrczt1-chains
For practical purposes, {x y} and {y x} are counted here as 2
bivalues.
Remarks:
- grouped-nrczt-chains can be specialised to grouped-nrct-chains and
grouped-nrc-chains;
- each of these grouped-chain types can be specialised to its 2D
counterpart in rc-space (notice that there are no hidden
counterparts in rn-, cn- or bn- spaces, because this notion is not
block-free);
- as nrc-chains are just a different view of the basic NLs or AICs
(i.e. NLs or AICs built on only elementary bivalue or conjugacy
relations), any example of a grouped-AIC/NL is an example of a
grouped-nrc-chain and a fortioti of a grouped-nrczt-chain. Of
course, one may expect more interesting examples, using effectively
the z- or t- extension.
**************
C) An instance of Ruud's
diagonal pattern
Here is another interesting example of an instance of Ruud's
diagonal pattern (#42 in the list of 100 provides by JPF:
http://www.sudoku.com/boards/viewtopic.php?t=4212&postdays=0&postorder=asc&start=870).
(As I mentioned previously, this pattern is very interesting and
I've already given an example of it. I haven't studied all the 100
instances provided by JPF, but the few cases I've tried show that it
allows nrczt solutions for puzzles with SER higher than usual.)
This puzzle with SER 9.4 needs nrczt-chains and lassos of length 17.
1..2..3..
....4..5.
..2..6...
7..3..5..
.4..8..7.
..9.....6
9..5..4..
....2..1.
..7..1..8
***** SudoRules version 13.4 *****
1..2..3......4..5...2..6...7..3..5...4..8..7...9.....69..5..4......2..1...7..1..8
hidden-single-in-a-column ==> r8c9 = 5
nrczt12-rl-lasso n5{r9c1 r9c2} - n5{r3c2 r3c5} - n5{r6c5 r6c6} -
n5{r1c6 r1c3} - n4{r1c3 r8c3} - n4{r9c1 r3c1} - n3{r3c1 r3c2} -
n3{r3c5 r2c6} - n3{r8c6 r8c1} - n3{r6c1 r6c8} - n4{r6c8 r6c4} -
n4{r9c4 r9c1} ==> r5c1 <> 5
nrczt16-chain n4{r9c4 r9c1} - n4{r8c3 r1c3} - n5{r1c3 r5c3} -
n6{r5c3 r5c1} - n2{r5c1 r6c1} - n5{r6c1 r3c1} - n5{r9c1 r9c2} -
n2{r9c2 r7c2} - n1{r7c2 r7c3} - {n1 n8}r4c3 - {n8 n1}r4c2 - {n1
n3}r6c2 - n3{r3c2 r3c5} - n3{r9c5 r9c8} - {n3 n7}r7c9 - {n7 n6}r7c5
==> r9c4 <> 6
nrczt17-chain n4{r8c3 r1c3} - n4{r3c1 r9c1} - {n4 n9}r9c4 - n9{r8c6
r8c7} - n7{r8c7 r7c9} - {n7 n9}r1c9 - n9{r3c8 r4c8} - n9{r4c5 r3c5}
- n9{r3c2 r2c2} - n9{r2c6 r5c6} - n5{r5c6 r5c3} - n5{r6c1 r3c1} -
n3{r3c1 r3c2} - n7{r3c2 r1c2} - n7{r1c5 r6c5} - n1{r6c5 r4c5} - {n1
n4}r6c4 ==> r8c4 <> 4
nrczt17-chain n4{r8c3 r1c3} - n4{r3c1 r9c1} - {n4 n9}r9c4 - n9{r8c4
r8c7} - n7{r8c7 r7c9} - {n7 n9}r1c9 - n9{r3c8 r4c8} - n9{r4c5 r3c5}
- n3{r3c5 r2c6} - n9{r2c6 r5c6} - n5{r5c6 r5c3} - n5{r6c1 r3c1} -
n3{r3c1 r3c2} - n9{r3c2 r2c2} - n7{r2c2 r1c2} - n7{r1c5 r6c5} -
n7{r6c6 r8c6} ==> r8c6 <> 4
hidden-single-in-a-block ==> r9c4 = 4
nrczt13-lr-lasso {n1 n7}r6c4 - {n7 n5}r6c5 - n5{r5c6 r1c6} - n5{r1c3
r5c3} - n6{r5c3 r5c1} - n6{r5c4 r4c5} - n1{r4c5 r3c5} - n3{r3c5
r2c6} - {n3 n8}r2c1 - {n8 n6}r2c3 - n6{r1c2 r1c8} - {n6 n4}r1c3 -
n8{r1c3 r1c2} ==> r5c4 <> 1
nrczt4-chain n1{r5c9 r5c3} - n5{r5c3 r5c6} - {n5 n7}r6c5 - {n7
n1}r6c4 ==> r6c7 <> 1
nrczt16-lr-lasso {n7 n1}r6c4 - n1{r4c5 r3c5} - n3{r3c5 r2c6} - {n3
n8}r7c6 - {n8 n9}r8c6 - {n9 n5}r1c6 - {n5 n2}r5c6 - {n2 n4}r4c6 -
n4{r6c6 r6c8} - n3{r6c8 r5c9} - {n3 n6}r5c1 - {n6 n8}r2c1 - {n8
n6}r2c3 - n6{r1c2 r1c8} - {n6 n4}r1c3 - n8{r1c3 r1c2} ==> r6c6
<> 7
nrczt14-chain {n7 n1}r6c4 - n1{r4c5 r3c5} - n3{r3c5 r2c6} - {n3
n8}r7c6 - {n8 n9}r8c6 - n7{r8c6 r1c6} - n5{r1c6 r1c5} - n5{r1c3
r5c3} - n5{r5c6 r6c6} - n4{r6c6 r6c8} - n3{r6c8 r5c9} - n1{r5c9
r5c7} - n9{r5c7 r5c4} - n6{r5c4 r8c4} ==> r8c4 <> 7
nrczt6-chain n3{r8c3 r8c6} - n7{r8c6 r8c7} - {n7 n2}r7c9 - n2{r2c9
r2c7} - n6{r2c7 r9c7} - {n6 n3}r7c8 ==> r7c3 <> 3
nrczt6-rl-lasso n5{r5c3 r1c3} - n4{r1c3 r8c3} - n3{r8c3 r2c3} -
n3{r2c6 r3c5} - n5{r3c5 r6c5} - n5{r5c6 r5c3} ==> r5c3 <> 6
nrczt6-rl-lasso n5{r5c3 r1c3} - n4{r1c3 r8c3} - n3{r8c3 r2c3} -
n3{r2c6 r3c5} - n5{r3c5 r6c5} - n5{r5c6 r5c3} ==> r5c3 <> 1
interaction row r5 with block b6 for number 1 ==> r4c9 <> 1
nrczt6-chain n3{r8c3 r8c6} - n7{r8c6 r8c7} - {n7 n2}r7c9 - n2{r2c9
r2c7} - n6{r2c7 r9c7} - {n6 n3}r7c8 ==> r7c2 <> 3
nrczt10-chain n3{r8c3 r8c6} - n7{r8c6 r8c7} - n9{r8c7 r8c4} - {n9
n6}r9c5 - n6{r9c7 r2c7} - n2{r2c7 r2c9} - {n2 n3}r7c9 - n3{r5c9
r5c3} - {n3 n8}r2c3 - {n8 n3}r2c1 ==> r9c1 <> 3
nrczt10-lr-lasso n6{r5c1 r5c4} - n6{r4c5 r7c5} - n6{r7c8 r1c8} -
n6{r2c7 r8c7} - n7{r8c7 r8c6} - n9{r8c6 r8c4} - n8{r8c4 r7c6} -
n3{r7c6 r2c6} - {n3 n8}r2c1 - n8{r1c2 r1c3} ==> r9c1 <> 6
nrczt15-lr-lasso n5{r9c1 r9c2} - n5{r3c2 r3c5} - n5{r1c6 r1c3} -
n4{r1c3 r8c3} - n4{r8c1 r3c1} - n3{r3c1 r3c2} - n3{r8c2 r8c1} -
n8{r8c1 r2c1} - n6{r2c1 r5c1} - n6{r5c4 r8c4} - {n6 n8}r8c2 -
n8{r8c6 r7c6} - n8{r1c6 r1c8} - n6{r1c8 r2c7} - {n6 n3}r2c3 ==>
r6c1 <> 5
nrczt10-lr-lasso {n8 n2}r6c7 - {n2 n3}r6c1 - {n3 n4}r6c8 - n4{r4c9
r4c6} - n2{r4c6 r5c6} - {n2 n6}r5c1 - {n6 n8}r2c1 - n8{r2c7 r3c7} -
n8{r3c4 r8c4} - n6{r8c4 r5c4} ==> r6c2 <> 8
nrczt17-rl-lasso n5{r1c3 r5c3} - n5{r5c6 r6c6} - n5{r6c5 r3c5} -
n3{r3c5 r2c6} - n3{r2c3 r8c3} - n4{r8c3 r1c3} - n6{r1c3 r1c8} -
n8{r1c8 r1c6} - {n8 n7}r7c6 - {n7 n9}r8c6 - {n9 n2}r5c6 - {n2
n4}r4c6 - n4{r6c6 r6c8} - n3{r6c8 r5c9} - {n3 n6}r5c1 - n6{r5c4
r8c4} - n8{r8c4 r7c6} ==> r1c2 <> 5
nrczt17-rl-lasso {n2 n8}r6c7 - {n8 n3}r6c1 - {n3 n4}r6c8 - n4{r4c9
r4c6} - n2{r4c6 r5c6} - n2{r5c1 r9c1} - n5{r9c1 r3c1} - n4{r3c1
r8c1} - n8{r8c1 r2c1} - n6{r2c1 r5c1} - n6{r5c4 r8c4} - n8{r8c4
r3c4} - {n8 n9}r3c8 - {n9 n2}r4c8 - n2{r5c7 r2c7} - n6{r2c7 r1c8} -
n8{r1c8 r3c8} ==> r6c2 <> 2
nrczt12-chain n3{r2c6 r3c5} - n3{r9c5 r9c8} - n3{r7c9 r5c9} - {n3
n5}r5c3 - {n5 n1}r6c2 - n1{r6c5 r4c5} - n6{r4c5 r5c4} - {n6 n2}r5c1
- {n2 n5}r9c1 - n5{r9c2 r3c2} - n7{r3c2 r1c2} - n9{r1c2 r2c2} ==>
r2c2 <> 3
nrczt17-lr-lasso n1{r3c4 r6c4} - n7{r6c4 r6c5} - n5{r6c5 r1c5} -
n5{r1c3 r5c3} - {n5 n3}r6c2 - n3{r6c8 r5c9} - n1{r5c9 r2c9} -
n2{r2c9 r2c7} - {n2 n8}r6c7 - {n8 n2}r6c1 - {n2 n6}r5c1 - n6{r5c4
r8c4} - {n6 n8}r8c2 - n8{r4c2 r4c3} - n8{r7c3 r7c6} - n8{r1c6 r1c8}
- n6{r1c8 r2c7} ==> r3c5 <> 1
interaction column c5 with block b5 for number 1 ==> r6c4
<> 1
naked-single ==> r6c4 = 7
nrczt15-chain n4{r3c1 r1c3} - n5{r1c3 r5c3} - n3{r5c3 r5c9} -
n3{r6c8 r6c2} - n1{r6c2 r6c5} - n5{r6c5 r6c6} - n4{r6c6 r6c8} -
n4{r3c8 r3c9} - n1{r3c9 r2c9} - n2{r2c9 r2c7} - n2{r6c7 r6c1} - {n2
n6}r5c1 - {n6 n9}r5c4 - {n9 n8}r2c4 - {n8 n3}r2c1 ==> r3c1
<> 3
nrczt10-rl-lasso n3{r3c5 r3c2} - n3{r9c2 r9c8} - n3{r6c8 r6c1} - {n3
n5}r5c3 - n5{r6c2 r9c2} - {n5 n2}r9c1 - {n2 n6}r5c1 - n6{r5c4 r4c5}
- n1{r4c5 r6c5} - {n1 n5}r6c2 ==> r7c5 <> 3
nrczt10-lr-lasso n3{r3c5 r3c2} - n5{r3c2 r3c1} - n5{r9c1 r9c2} - {n5
n1}r6c2 - {n1 n5}r6c5 - {n5 n9}r1c5 - n9{r1c2 r2c2} - n7{r2c2 r1c2}
- {n7 n4}r1c9 - n4{r1c3 r3c1} ==> r3c5 <> 7
nrczt9-chain n7{r7c9 r8c7} - n7{r3c7 r3c2} - n3{r3c2 r3c5} - n5{r3c5
r3c1} - n5{r9c1 r9c2} - n3{r9c2 r9c8} - n9{r9c8 r9c7} - n6{r9c7
r2c7} - n2{r2c7 r2c9} ==> r2c9 <> 7
nrczt9-lr-lasso n7{r3c7 r3c2} - n3{r3c2 r3c5} - n5{r3c5 r3c1} -
n5{r9c1 r9c2} - n3{r9c2 r9c8} - {n3 n2}r7c9 - n2{r2c9 r2c7} -
n6{r2c7 r1c8} - {n6 n2}r7c8 ==> r1c9 <> 7
nrczt6-chain {n4 n9}r1c9 - {n9 n8}r3c8 - {n8 n5}r3c1 - {n5 n2}r9c1 -
n2{r7c2 r4c2} - {n2 n4}r4c9 ==> r3c9 <> 4
nrczt8-lr-lasso n7{r3c9 r7c9} - n3{r7c9 r5c9} - {n3 n5}r5c3 -
n5{r1c3 r3c1} - {n5 n2}r9c1 - {n2 n6}r5c1 - n6{r5c4 r8c4} - {n6
n7}r7c5 ==> r3c2 <> 7
interaction row r3 with block b3 for number 7 ==> r2c7 <> 7
nrczt6-lr-lasso n7{r2c2 r2c6} - n7{r8c6 r8c7} - n6{r8c7 r9c7} -
n9{r9c7 r9c8} - {n9 n3}r9c5 - n3{r3c5 r2c6} ==> r2c2 <> 6
nrczt7-rl-lasso n3{r3c5 r3c2} - n5{r3c2 r3c1} - n4{r3c1 r3c8} - {n4
n9}r1c9 - n9{r1c2 r2c2} - n7{r2c2 r2c6} - n3{r2c6 r3c5} ==> r3c5
<> 9
nrczt8-lr-lasso n2{r5c1 r9c1} - n5{r9c1 r3c1} - n4{r3c1 r3c8} - {n4
n9}r1c9 - {n9 n4}r4c9 - {n4 n9}r4c6 - n9{r4c8 r9c8} - n9{r9c5 r4c5}
==> r4c2 <> 2
interaction column c2 with block b7 for number 2 ==> r9c1
<> 2
naked-single ==> r9c1 = 5
hidden-pairs-in-a-row {n3 n5}r3{c2 c5} ==> r3c2 <> 9
hidden-pairs-in-a-block {n7 n9}{r1c2 r2c2} ==> r2c2 <> 8,
r1c2 <> 8, r1c2 <> 6
hidden-pairs-in-a-row {n3 n5}r3{c2 c5} ==> r3c2 <> 8
nrczt4-chain n4{r8c3 r1c3} - n6{r1c3 r1c8} - n8{r1c8 r1c6} - n8{r7c6
r7c2} ==> r8c3 <> 8
hxyzt6-rn-chain {c8 c3}r1n6 - {c3 c6}r1n8 - {c6 c5}r1n5 - {c5
c2}r3n5 - {c2 c6}r6n5 - {c6 c8}r6n4 ==> r1c8 <> 4
nrct6-chain {n4 n9}r1c9 - {n9 n7}r1c2 - {n7 n5}r1c5 - n5{r3c5 r3c2}
- n5{r6c2 r6c6} - n4{r6c6 r6c8} ==> r4c9 <> 4
naked and hidden singles ==> r1c9 = 4, r3c1 = 4, r8c3 = 4
nrc3-chain n3{r2c3 r5c3} - n5{r5c3 r1c3} - {n5 n3}r3c2 ==> r2c1
<> 3
nrczt3-chain n4{r4c8 r4c6} - n2{r4c6 r4c9} - {n2 n8}r6c7 ==> r4c8
<> 8
interaction row r4 with block b4 for number 8 ==> r6c1 <> 8
nrczt2-chain n8{r2c1 r8c1} - n8{r8c4 r3c4} ==> r2c6 <> 8
naked-triplets-in-a-row {n2 n4 n9}r4{c6 c8 c9} ==> r4c5 <>
9
nrct3-chain n3{r2c3 r5c3} - n3{r6c1 r8c1} - n8{r8c1 r2c1} ==>
r2c3 <> 8
nrczt3-chain n9{r8c7 r9c8} - n9{r9c5 r1c5} - n9{r3c4 r3c9} ==>
r2c7 <> 9
nrczt3-chain n6{r9c2 r4c2} - {n6 n1}r4c5 - n1{r4c3 r7c3} ==> r7c3
<> 6
nrc4-chain n7{r2c6 r2c2} - {n7 n9}r1c2 - n9{r1c5 r9c5} - n3{r9c5
r3c5} ==> r2c6 <> 3
naked and hidden singles ==> r3c5 = 3, ==> r3c2 = 5, r5c3 = 5,
r2c3 = 3
naked-pairs-in-a-row {n7 n9}r2{c2 c6} ==> r2c9 <> 9, r2c4
<> 9
nrc3-chain {n9 n2}r4c9 - {n2 n1}r2c9 - n1{r5c9 r5c7} ==> r5c7
<> 9
nrczt3-chain n9{r5c6 r5c4} - n6{r5c4 r8c4} - {n6 n9}r9c5 ==> r8c6
<> 9
nrc3-chain n9{r8c4 r8c7} - n7{r8c7 r7c9} - {n7 n6}r7c5 ==> r8c4
<> 6
naked and hidden singles ==> r5c4 = 6, r4c5 = 1, r6c5 = 5, r1c6 =
5, r6c2 = 1, r7c3 = 1
interaction column c2 with block b7 for number 3 ==> r8c1
<> 3
interaction column c6 with block b8 for number 8 ==> r8c4
<> 8
naked and hidden singles
GRID 0 SOLVED. LEVEL = L17, MOST COMPLEX RULE = NRCZT17
176295384
893147652
452836197
768312549
345689271
219754836
921578463
684923715
537461928
Home(The Hidden Logic of Sudoku)
Home(Denis
Berthier)