Fully supersymmetric chains

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Tue Feb 12, 2008 7:02 am

coloin wrote:In all [hard] puzzles wont every wrong proposition clue be the culprit for producuing a varianbly long condradiction loop ?
C

As a complement to my previous answer and to Mike's, and after defining the nrczt-nets:
given a candidate, nrczt-nets are the most general first order net pattern that can allow its elimination in a single step.

This raises several questions:
- can any valid puzzle be solved using only nrczt-nets?
- does there exist first order patterns that can't be recast as nrczt-nets? If we were speaking of chains, the answer would be yes: not all quads are nrczt-chains. But I have now proven that all the classical subset patterns (naked, hidden or super-hidden) and their sushi or sashimi finned variants are nrczt-nets. Using more complex nets, it is very likely that we can prove any chain including ALSs is a special case of nrczt-nets. Now can Steve pattern be recast as an nrczt-net? I haven't tried very hard, but if it is possible it is not simple and the net would be very wide.


But I think these are mainly theoretical questions. This is because in practice we don't want to use such complex patterns as nets with their exponential behaviour (as the most general chains with ALSs). So the really interesting questions would be:
- can any valid puzzle be solved using only nrczt-nets with branching factor limited to k and length limited to l? (l ank k fixed)
- can any valid puzzle be solved using only nrczt-nets with width limited to k and length limited to l? (l ank k fixed)


These questions are intimately related to NP-completeness of sudoku(nxn).
In this context, I think the general x2y2-belts can be proven to have a maximal length for the standard puzzles Sudoku(3x3).
But for Sudoku(nxn), things get more complex:
- x2y2-belts can be longer, the shapes of the spines can a priori become very complex and the associated net (if any) would get still wider;
- as n increases, we can introduce x3y3-belts, x4y4-belts,...
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Tue Mar 04, 2008 9:52 am

GOING BEYOND THE NRCZT-CHAINS ?

I don't have much time for Sudoku this year, but once you've got the virus, can you ever shake it off completely? I still try to glean a little time from my agenda.

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 in previous posts, but (together with the standard basic rules) they still miss a few puzzles (about 1 in 10,000 minimal puzzles).

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.
In a previous post, I mentioned that if we extended the definition of an nrczt chain so as to allow hinges instead of the links that need only be mere nrc-links (i.e. all but the odd links), thus obtaining hinged nrczt-chains, this didn't seem to lead to interesting results (i.e. to more eliminations).

Another alternative is better exploiting the partial occurrences of the nrczt-chains themselves.

In another previous post, 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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Tue Mar 04, 2008 9:54 am

NRCZT-BICHAINS

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.

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 targer 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://forum.enjoysudoku.com/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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Tue Mar 04, 2008 9:58 am

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: Select all
*****  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: Select all
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: Select all
;;; 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
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Tue Mar 18, 2008 6:01 am

NRCZ CHAINS SUBSUME BROKEN WINGS

When re'born asked me (at the bottom of this page: http://forum.enjoysudoku.com/viewtopic.php?t=5591&postdays=0&postorder=asc&start=45) whether there was "a nice way of either subsuming broken wings into nrczt-chains, or melding them into a even slightly bigger theory", I concentrated on Rod Hagglund's definition of Broken Wings (here: http://forum.enjoysudoku.com/viewtopic.php?t=2666&highlight=) and I noticed the logic for justifying the eliminations was very different from the logic of the nrczt-chain rules.
But, recently I was again asked the same question by a friend. As I looked at Broken Wings again, instead of reading the proof, I tried to translate them into my approach.
The result is obvious and I don't understand how I can have missed this in my answer to re'born:
nrcz-chains subsume broken wings. What RodHaggund calls guardian cells can be understood as mere additional z-candidates.
There's no need of the t-extension.

Even without the t-extension, nrcz-chains are much more general than broken wings (and each of the following reasons may have misled me the first time I looked at them):
- there's no need for a closed loop
- there no need for all links to be conjugacy links (modulo the guardians): the constraint bears only on even links;
- the length can be odd or even, no matter (this is a consequence of the previous point);
- the number of additional z-candidates in any link is completely irrelevant.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby andre43 » Tue Apr 15, 2008 2:20 pm

Hi! May someone please explain to me the mechanism of Denis Berthier’s “FULLY SUPERSYMMETRIC CHAINS”? It’s the one and only technique I never comprehended even though I read many times the discussions in this forum and even I put in the solver the example included there…. What is the definite difference among this method and the so-called “Multiple Inference Nice Loops”? MINL is the central idea underlying the xyt-chains, but although D.Berthier denotes that this same idea is hidden behind the FSC too, I don’t understand how the last is functioning. So, how may I apply the “Fully Supersymmetric Chains” in a sudoku puzzle? May someone give me an example along with the rationale of application every possible nrct, nrcz or nrczt chains within a puzzle? Thanks a lot!
andre43
 
Posts: 16
Joined: 03 September 2006

Postby denis_berthier » Fri Apr 18, 2008 11:28 am

andre43 wrote:Hi! May someone please explain to me the mechanism of Denis Berthier’s “FULLY SUPERSYMMETRIC CHAINS”? It’s the one and only technique I never comprehended even though I read many times the discussions in this forum and even I put in the solver the example included there…. What is the definite difference among this method and the so-called “Multiple Inference Nice Loops”? MINL is the central idea underlying the xyt-chains, but although D.Berthier denotes that this same idea is hidden behind the FSC too, I don’t understand how the last is functioning. So, how may I apply the “Fully Supersymmetric Chains” in a sudoku puzzle? May someone give me an example along with the rationale of application every possible nrct, nrcz or nrczt chains within a puzzle? Thanks a lot!

The answer to your question is very simple: MINLs are nets (with branching and merging of different paths) while 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). And I`ve certainly never suggested that the same idea is hidden behind them and the MINLs.

In any of my chains, 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:
Code: Select all
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.

Again, you can see many examples in the threads I opened in this forum or on my web pages.

If you want to co;pare MINLs to anything I defined, You should do it with nrczt nets. But I`m so allergic to nets that I didn`t even think of programmimg them into SudoRules.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby andre43 » Mon Apr 21, 2008 2:43 pm

Thanks you, Denis, for your exceptionally informative reply...I greatly appreciate it.
andre43
 
Posts: 16
Joined: 03 September 2006

Postby denis_berthier » Thu Jul 24, 2008 10:03 am

RESTRICTED FORMS OF nrc(z)(t) CHAINS.

If you consider the most general definition of an nrczt-chain, as given in the first post of this thread, you'll 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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Fri Jul 25, 2008 5:31 am


THEOREM: NRCZ-CHAINS SUBSUME THE BASIC INTERACTIONS


This is a stronger and much more interesting assertion than the previous one about nrczt-nets subsuming these interactions (in the "concept of a resolution rule" thread)..
The proof follows the same lines as the previous one, but is simpler.

ROW INTERACTION WITH BLOCK (RiB):

First, the general pattern for a non-degenerate RiB (seen in standard rc-space) is:

Code: Select all
XXXXXX-----11-----12----(13)
            ?------?------?
            ?------?------?

the rightmost 9 cells are in the same block,
11, 12, 13 designate occurrences of the target value under consideration,
the 6 X's indicate that the target value is not allowed in the 6 cells of the row outside the block,
parens indicate an optional candidate,
? indicates a possible place for the target (in the same block as 11 12 13),
Rows and columns within a block can be permuted.
Notice that at least two occurrences of the target value must occur in the row under consideration: otherwise, we'd have a Naked Single.


First case:
Code: Select all
XXXXXX-----11-----12-----X
            ?------?-----?
            ?------?-----?

subsumed by NRC1: {11 12}


Second case:
Code: Select all
XXXXXX-----11-----12----(13)
            ?------?------?
            ?------?------?

subsumed by NRCZ1 : {11 12 13#z}



BLOCK INTERACTION WITH ROW (BiR)

First, the general pattern for a non-degenerate RiB (seen in standard rc-space) is (with the same conventions as above); here the target (?) is in the same row as 11 12 13 and outside their common block:

Code: Select all
X-------X-------X
X-------X----- X
11-----12-----(13)-------------?-------



First case:
Code: Select all
-X-----X-----X-
-X-----X-----X-
-11----12----X-----------Z

subsumed by NRC1: {11 12}


Second case:
Code: Select all
-X------X------X-
-X------X------X-
-11----12------13---------Z

subsumed by NRCZ1: {11 12 13#z}


INTERACTIONS WITH COLUMNS
the result is obtained by rc symmetry.


COMMENTS:
Most obvious things may not be those that we see immediately. In a previous post in this thread, I wondered why allowing hinges in the nrczt-chains instead of the nrc-links didn't (seem to) bring more generality. The answer is now clear: hinges (which are the usual way of introducing the basic interaction rules in the AICs and NLs) are already included in the nrczt-chains, because these subsume the basic interactions.
As the proof above shows, from a theoretical POV, allowing z-candidates in the first cell of nrcz(t) chains is essential for this theorem to be valid.
As my previous post also shows, this is rarely needed in practice.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sun Jul 27, 2008 2:09 pm


An example of how using restricted forms of nrc-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 ER 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 /Users/berthier/Documents/INT-Projets/SudoRules/SudoRules13/Puzzles/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).
Another example of this situation is given by puzzle Sudogen0 #707.

(In the opposite case of puzzles that have few partial chains, one could try to use more general chains. But, useable generalisations of nrczt-chains, which are not overly general, are not yet obvious.)

Note: when I give a solution of a puzzle, I use the unrestricted version of nrczt-chains, unless otherwise stated.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Beyond nrczt-chains: GROUPED-NRCZT-CHAINS

Postby denis_berthier » Wed Aug 20, 2008 5:55 am


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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Fri Aug 22, 2008 3:33 am

I've forgotten to say it but that should be obvious:

- 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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Aug 30, 2008 4:51 am

Here is an interesting example noticed by Caravail, in the French sudoku-factory forum, as one particularly hard among those with SE=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:
Code: Select all
     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: Select all
     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:
Code: Select all
     c1     c2     c3       c4      c5      c6        c7     c8     c9
   --------------------------------------------------------------------------
r1 ! 123    1267   367    ! 13679   8       13479   ! 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
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Thu Sep 04, 2008 4:09 am

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://forum.enjoysudoku.com/viewtopic.php?t=4212

Code: Select all
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: Select all
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: Select all
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
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques