Fully supersymmetric chains

Advanced methods and approaches for solving Sudoku puzzles

Fully supersymmetric chains

Postby denis_berthier » Wed Aug 15, 2007 5:31 am


FULLY SUPERSYMMETRIC CHAINS
3D-CHAINS: NRC-, NRCT-, NRCZ- AND NRCZT- CHAINS


Until now, apart from c-chains, all the chains I have considered were defined and could be spotted as (pure or extended) xy-chains in either of the two dimensional rc-, rn- or cn- spaces. Surprisingly, this was enough to solve 97% of the randomly generated puzzles.
Nevertheless, for the remaining puzzles, some way of "knitting" through the two dimensional spaces is needed. c-chains are the simplest example of such a knitting. This post introduces more general three dimensional (3D) chains, which are the 3D analogues of the two dimensional xy-, xyt- and xyzt- chains.
The general idea remains the same: the presence of any candidate that is already ruled out by previous cells in the chain (or by the target cell) can be forgotten as an additional candidate whenever convenient (but it can still be used as a left linking candidate for the next cells). In order to use this idea in the 3D view, we just have to slightly adapt its formulation.


GENERAL 3D-CHAINS

3D-chains are also defined in the thread on the NRC notation (the notation which will be used here). Let me repeat the definitions here.
The basic notion underlying the 3D-chains 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, not its factual definition).
An nrc-link is written as "—".

Definition: a 3D-chain is a sequence of candidates, such that the first and the last candidates in the sequence are different (there is no global loop) and any two consecutive candidates are nrc-linked.

Notice that global loops are excluded by definition, but not internal loops. Internal loops can be shown to be useless only for some types of chains (e.g. in 2D: xy-, hxy-, c-).

Definition: a target of a 3D-chain is a candidate that does not belong to the 3D-chain and that is nrc-linked to both endpoints of the 3D-chain.

Notice that, in conformance with the approach adopted in my book, targets never belong to the chain. This allows to define specific types of chains with homogeneous patterns and this provides for the possibility of several targets for the same chain.
Of course, interesting 3D-chains (i.e. 3D-chains that allow eliminations) will impose additional conditions. For examples, see the thread on nrc-, nrct-, nrcz- and nrczt- chains.
Basically, these conditions will allow to group adjacent candidates that are related by stronger links than mere nrc-links.


NRC-CHAINS

Definition: two candidates n1r1c1 and n2r2c2 are nrc-conjugate if they are nrc-linked and:
- either n1 <> n2, (r1, c1) and (r2, c2) are the same rc-cell, and the only candidates for this cell are n1 and n2 - i.e. cell (r1, c1) is bivalue,
- or n1=n2, (r1, c1) and (r2, c2) are different rc-cells, and there is a row, a column or a block along which (r1, c1) and (r2, c2) are conjugate for n1 – i.e. in which n1 is a candidate for only these two cells.


nrc-conjugate is the most general, fully super-symmetric, synthesis of the bivalue property of cells and conjugacy property of candidates in rc-space.


Definition: an nrc-chain is a 3D-chain of even length 2n such that, for any odd k with 1 <= k <= n, n(2k-1)r(2k-1)c(2k-1) and n(2k)r(2k)c(2k) are nrc-conjugate.

Here parentheses stand for subscripts, because I can't write subscripts with the software of this forum.
Two nrc-conjugate candidates will be represented by the pattern {n1r1c1 n2r2c2}
An nrc-chain (of length 6) can be represented by the pattern:
{1 2} — {3 4} — {5 6}
where the curly braces indicate the nrc-conjugacy relation.

Theorem (nrc-chain rule): given an nrc-chain, any target candidate can be eliminated.


NRCT-CHAINS

Definition: given a set S of candidates, two candidates n1r1c1 and n2r2c2 are nrc-conjugate modulo S if they do not belong to S, they are nrc-linked and:
- either n1 <> n2, (r1, c1) and (r2, c2) are the same rc-cell, and the only candidates for this cell are n1, n2 and possibly any other value n such that (n, r2, c2) is nrc-linked to an element of S,
- or n1=n2, (r1, c1) and (r2, c2) are different rc-cells, and there is a row, a column or a block along which (r1, c1) and (r2, c2) are conjugate for n2 modulo S – i.e. in which n2 is a candidate only for these two cells and possibly for any other cell (r, c) such that n1rc is nrc-linked to an element of S.


Definition: an nrct-chain is a 3D-chain of even length 2n 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 set of previous even nrc-cells of the chain.

An nrct-chain (of length 6) can be represented by the pattern:
{1 2} — {3 4} — {5 6 (2#2)}
where the curly braces indicate the nrc-conjugacy relation and the (2#2) indicates a optional conditional candidate.

Theorem (nrct-chain rule): given an nrct-chain, any target candidate can be eliminated.


NRCZ-CHAINS

Definition: given a candidate C, an nrcz-chain built on C is a 3D-chain of even length 2n such that:
- for any odd k with 1 <= k <= n, n(2k-1)r(2k-1)c(2k-1) and n(2k)r(2k)c(2k) are nrc-conjugate modulo C,
- C is nrc-linked to both endpoints of the chain - C is thus the (nrcz-) target of the nrcz-chain.



Theorem (nrcz-chain rule): given an nrcz-chain, its target candidate can be eliminated.


NRCZT-CHAINS

Definition: given a candidate C, an nrczt-chain built on C is a 3D-chain of even length 2n such that:
- for any odd k with 1 <= k <= n, n(2k-1)r(2k-1)c(2k-1) and n(2k)r(2k)c(2k) are nrc-conjugate modulo the set consisting of C plus the previous even nrc-cells of the chain,
- C is nrc-linked to both endpoints of the chain - C is thus the (nrczt-) target of the nrczt-chain.

An nrczt-chain (of length 6) can be represented by the pattern:
{1 2 (*)} — {3 4 (*)} — {5 6 (2#2)}
where (*) indicates an optional candidate conditioned by its having an nrc-link with the target.

Theorem (nrczt-chain rule): given an nrczt-chain, its target candidate can be eliminated.



PROOFS OF THE NRC-, NRCT-, NRCZ AND NRCZT- CHAIN RULES

The proofs of the nrc- and nrct-, nrcz- and nrczt- chain rules follow the same general pattern, which is the adaptation to 3D-space of the proofs for the xy-, xyt-, xyz- and xyzt- chain rules: in any of these chains, if the first candidate is false, then all the even candidates must be true. This can easily be proven by recursion on the length of the chain.
The application to the chain rules themselves is straightforward. For any target cell C, if the first candidate is true, then the target candidate must be false; and if the first candidate is false, then the last is true, and the target candidate must be false.
In the case of nrcz- and nrczt- chains, the target cell has to be included in the proof itself. Apart from this, the rest of the proof goes along the same lines as for xyt-chains.
As I already indicated, what is difficult for these chains is not proving the validity of the associated chain rules, it is
- for the theoretician, establishing the proper definiton in their full generality,
- for the player, spotting the actual chains on an actual grid.


SUBSUMPTION RELATIONSHIPS

nrc-chains subsume xy, hxy-rn and hxy-cn- chains 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


All of the above definitions can straightforwardly be extended to AICs, which should be called in the above approach nrc chains of subsets. We can thus get AICt and AICzt chains. These have not been included in SudoRules 13.


NRC(Z)(T) COLOURING

To the nrc(z)(t)-chain resolution rules can be associated resolution techniques (see the thread on this distinction, here: http://forum.enjoysudoku.com/viewtopic.php?t=5600)
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 right 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.


EXTENSION: AICT AND AICZT

All of the above can straightforwardly be extended to AICs, what should be called in the above approach nrc chains of subsets.


RESULTS

The nrc-, nrct- and nrczt- chains have been included in the new version of SudoRules (version 13).
SudoRules 13 can solve all but one (for which it meets a memory overflow problem) of the 10,000 randomly generated puzzles in the Sudogen0 collection.
This is noticeable, since SudoRules 13 has no rule for subsets (no Hinges, no Almost Locked Sets,…) and no rule for Uniqueness.
SudoRules 13 can also solve 24 out of the first 30 puzzles in Ruud’s top10000.

Among the other puzzles that cannot be solved with only the rules described here:
- EasterMonster (BTW, has any solution been published - I mean without T&E)?


EXAMPLES

As a first simple example of nrc-chains, let me take the puzzle used by Ron Hagglund in the thread where he introduced the hinge pattern (Sudoku UK forum/ Eureka, December 25, 2005 - 11:52 pm). This will show how (at least) some hinges can be replaced by xy(z)(t) chains.
My new NRC notation of chains is used.

604352970
002470036
370690002
429536187
751284369
863719200
200160093
100040620
006020700
Code: Select all
number 8 : column C4 interaction with block B8
                              ==> 8 eliminated from the candidates for R9C6
number 8 : column C4 interaction with block B8
                              ==> 8 eliminated from the candidates for R8C6
number 8 : column C4 interaction with block B8
                              ==> 8 eliminated from the candidates for R7C6
nrc3-chain N1R9{C8 C9} - {N1 N8}R1C9 - {N8 N5}R8C9
                              ==> 5 eliminated from the candidates for R9C8
nrc3-chain {N8 N9}R9C4 - N9R8{C4 C2} - N3{R8 R9}C2
                              ==> 8 eliminated from the candidates for R9C2
nrc3-chain {N9 N5}R9C1 - {N5 N3}R9C6 - N3{R9 R8}C2
                              ==> 9 eliminated from the candidates for R8C2
number 9 : hidden-single-in-row R8           ==> R8C4 = 9
number 8 : naked-single                               ==> R9C4 = 8
nrc2-chain N8R1{C2 C9} - N8{R8 R7}C9
                              ==> 8 eliminated from the candidates for R7C2
number 4 : naked-single                               ==> R7C2 = 4
number 4 : hidden-single-in-column C7      ==> R3C7 = 4
numbers 5 and 8 : naked-pairs-in-block B9: R7C7-R8C9
                              ==> 5 eliminated from the candidates for R9C9
number 1 : xy-wing on cells R1C2*, R3C3 and R3C8* with numbers 1, 8 and 5
                              ==> 1 eliminated from the candidates for R1C9
…(Naked Singles)…

614352978
982471536
375698412
429536187
751284369
863719254
247165893
138947625
596823741
For a more complex example, with nrc-, nrct- and nrczt- chains, see the thread "Ruud's10K Problem #66" (indeed #663)


edited 08/17/07 : changed the title of the thread

edited 07/24/08 : added the following:

There is a question about the first cell of an nrcz(t) chain that I haven't answered correctly in the first posts of this thread: has the first cell to be bivalue or conjugate? I answered yes, but this is incorrect. As the pattern I gave for the nrczt6 chains ({1 2 (*)} — {3 4 (*)} — {5 6 (2#2)}) shows, there can be additional z-candidates in the first cell.
It is easy to give an example of such a situation: consider candidates in row 1 and block 1:

C1=n1r1c1, C2 = n1r1c9, additional z candidates: n1r1c2 and n1r1c3, no other n1 candidate in row1
target = n1r3c2

Surprisingly, allowing this possibility doesn't seem to lead to the solution of more puzzles than disallowing it (but it may allow solutions with shorter chains) - this remark is based on an analysis of the 10.000 puzzles in Sudogen0. In the current version of SudoRules (version 13), this is allowed.
Last edited by denis_berthier on Wed Jul 23, 2008 11:56 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Mike Barker » Sat Aug 18, 2007 11:42 am

Denis, nrct-chains are an extension of xyt-chains, but why stop there? I realized several weeks ago that xyt-chains and hxyt-chains are at one level an extension of nice loops to include "T-links" which connect multivalued cells or kraken units to the established chain. At another level they are simpler than nice loops and so fit earlier into a hierarchy of solving techniques, but just as nice loops can manifest as XY-chains, X-cycles, advanced coloring, or multi-inference nice loops so the addtion of a T-link can occur at different levels of difficultly.

I think there are several practical consequences of looking at nrct-chains as nice loops with a T-link. First, in the descriptions I've read, nrct-chains evolve from left to right with links created to the left or to the target cell. One advantage of nice loops is that the evolve in both directions. It seems that the same can be true of nrct-chains, that nodes can be added to the right with left looking T-links or to the left with right looking T-links. This makes nrct-chains much less dependent on the starting node.

Secondly, nice loops allow for eliminations within nodes of the loop. This is thus also true of nrct-chains. Eliminations can be made in the end nodes if they end with a "conjugate pair" or within nodes of the chain which see the end nodes.

Thirdly, I know you don't like to think of continuous nrct-chains, in fact its part of the definition, but from a practical standpoint recognizing that a chain is continous means that many more eliminations are immediately possible without constructing a new loop. From a theoretical point of view this doesn't make a difference since the continuous loop can be thought of as multiple discontinuous loops, but from a practical point of view continuity is a key observation

Fourth, I haven't thought this completely true, but it seems that T-links could also be used in networks, with ALS and with other almost-things. Yes this adds complexity on top of complexity, but as you've seen in progressing from xyt-chains to nrct-chains more complexity seems to be required to solve more complex problems. Your T-links are an example of a great new approach which limits the level of complexity, but there are still tougher problems out there.

Fifth, recognizing that nrct-chains can be thought of as and extension of nice loops means that we are not limited to one or the other, but both can be used as the complexity of the problem increases.

I recognize that this is a practical point of view and not a mathematically derived treatise, but I see nothing logically wrong with this perspective. FYI I use a capital "T" in T-links since I like the visual image it provides which suggests the actual nature of the links. Again this is a matter of personal perspective. Hopefully I haven't upset you too much, please remember this is just my way of looking at your contributions.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby denis_berthier » Sat Aug 18, 2007 5:01 pm

Mike Barker wrote:Denis, nrct-chains are an extension of xyt-chains, but why stop there? I realized several weeks ago that xyt-chains and hxyt-chains are at one level an extension of nice loops to include "T-links" which connect multivalued cells or kraken units to the established chain. At another level they are simpler than nice loops and so fit earlier into a hierarchy of solving techniques, but just as nice loops can manifest as XY-chains, X-cycles, advanced coloring, or multi-inference nice loops so the addtion of a T-link can occur at different levels of difficultly.


Mike, I now consider that, if we want to go beyond the 2D chains introduced in my book, there is one fundamental type of "3D chains", the nrc-chains, which exhibit the full supersymetry property.
These chains can be seen either as chains of cells, with links crossing through the rc-, rn-, cn- and bn- spaces, or as chains of candidates - unifying two apparently conflicting views of chains.

I also consider that there are two different types of independent extensions: t and z and that they can be combined into zt. Whence the nrct, nrcz and nrczt chains. All these names may be not very sexy and I'm open to any suggestions on this.

About the extensions you are mentioning, yes, that's what I alluded to in the short section "Extensions". I thought of this long ago, but I didn't want to speak of it until I had time to program it and evaluate the practical consequences. There are so many possible extensions that we need some concrete elements to help us choose the most promising ones. I started this thread when I had these elements.
The (h)xy(z)(t) chains allowed me to solve 97% of the random puzzles.
The nrc(z)(t) (which subsume the h and non h versions above) now allow me to solve 99.99%. That's what I call an interesting extension.
(BTW, I had also tried some 2D nettish extensions, that gave poor results).
This leaves 0.01% of super-hard puzzles. (Maybe those that we shall consider as possibly interesting in a few weeks.)

What we now need is some comparison between these extensions and others that add subsets in the landscape (Hinges, ALS, …), thereby introducing some nettish aspects. This morning, I opened a thread on this topic in the UK forum: http://www.sudoku.org.uk/discus/messages/29/4602.html?1187435195


Mike Barker wrote:I think there are several practical consequences of looking at nrct-chains as nice loops with a T-link. First, in the descriptions I've read, nrct-chains evolve from left to right

Yes
Mike Barker wrote:with links created to the left or to the target cell.

The target cell does not appear in the construction of an xyt- or an nrct- chain (except, of course, at the end, when we choose a target for the eliminations).
This is important in practice, because it allows several targets to be associated to the same chain.

Mike Barker wrote:One advantage of nice loops is that they evolve in both directions.

Yes, this is an advantage.
Mike Barker wrote:It seems that the same can be true of nrct-chains, that nodes can be added to the right with left looking T-links or to the left with right looking T-links. This makes nrct-chains much less dependent on the starting node.

Unfortunately, no. The left-to-right asymmetry of the xyt or the nrct chains is due to the way the chain rules can be proved; it can only proceed from one end of the chain to the other. I don't know how to proceed from both ends and I don't think it is possible: the problem is with the cell/candidate where the two parts would join. I think, if we did so, the conditions on the junction would amount to building an nrct-net.

Mike Barker wrote:Secondly, nice loops allow for eliminations within nodes of the loop. This is thus also true of nrct-chains. Eliminations can be made in the end nodes if they end with a "conjugate pair" or within nodes of the chain which see the end nodes.
Thirdly, I know you don't like to think of continuous nrct-chains, in fact its part of the definition, but from a practical standpoint recognizing that a chain is continous means that many more eliminations are immediately possible without constructing a new loop. From a theoretical point of view this doesn't make a difference since the continuous loop can be thought of as multiple discontinuous loops, but from a practical point of view continuity is a key observation


I proved that considering xy chain or Nice Loops with loops doesn't lead to more eliminations than considering only the same without loops. From a theoretical point of view, it means that the specific rules for such loops are useless. But it does not forbid to use them in practice.
The only thing I don't understand is why you need to make any difference between continuous and discontinuous NLs. In my approach (with the target not included in the chain), this is pointless.

Mike Barker wrote:Fourth, I haven't thought this completely true, but it seems that T-links could also be used in networks, with ALS and with other almost-things. Yes this adds complexity on top of complexity, but as you've seen in progressing from xyt-chains to nrct-chains more complexity seems to be required to solve more complex problems. Your T-links are an example of a great new approach which limits the level of complexity, but there are still tougher problems out there.
Fifth, recognizing that nrct-chains can be thought of as and extension of nice loops means that we are not limited to one or the other, but both can be used as the complexity of the problem increases.


Yes, the general principle of the t, z and zt extensions can be applied to lots of different chains or nets. In principle, we could mix them with lots of other extensions. My only problem with this is that I have neither a super brain nor a super computer to help me find their occurences on a real grid.

Mike Barker wrote:I recognize that this is a practical point of view and not a mathematically derived treatise, but I see nothing logically wrong with this perspective.

I can't see anything logically wrong with any of your suggestions, but we all meet the same practical point: complexity.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby re'born » Sat Aug 25, 2007 1:52 pm

Denis,

Are your nrc-chains the same as Ruud's Medusa 3D-chains? They're obviously not when (t) or (z) is added, but without, I can't spot the difference.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Sat Aug 25, 2007 2:36 pm

re'born wrote:Denis,
Are your nrc-chains the same as Ruud's Medusa 3D-chains? They're obviously not when (t) or (z) is added, but without, I can't spot the difference.


In practice, nrc-chains are what I call "basic AICs", i.e. AICs with only bivalue and conjugacy links. All I could find on Medusa is in terms of colouring. But colouring is not a resolution rule, just a resolution technique. Anyway, the relationship between nrc-chains and Medusa seems to be strong.

I've given nrc-links, nrc-conjugacy links and nrc-chains fully precise supersymmetric definitions, exhibiting the equivalence between conjugate and bivalue (in some 2D space). nrc-chains are not new, they are "basic AICs" but viewed in a different perspective, which allowed me to apply them the t and z extensions.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby re'born » Sat Aug 25, 2007 3:10 pm

denis_berthier wrote:
re'born wrote:Denis,
Are your nrc-chains the same as Ruud's Medusa 3D-chains? They're obviously not when (t) or (z) is added, but without, I can't spot the difference.


In practice, nrc-chains are what I call "basic AICs", i.e. AICs with only bivalue and conjugacy links. All I could find on Medusa is in terms of colouring. But colouring is not a resolution rule, just a resolution technique. Anyway, the relationship between nrc-chains and Medusa seems to be strong.

Perhaps someone else can provide a link with a more precise description of Medusa resolution rules. The best I know of is this (incomplete) description by Ruud.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Glyn » Sun Aug 26, 2007 12:31 am

re'born wrote:

Perhaps someone else can provide a link with a more precise description of Medusa resolution rules. The best I know of is this (incomplete) description by Ruud.


As the name Medusa was, I believe, coined by Bob Hanson you might find his website interesting.

http://www.stolaf.edu/people/hansonr/sudoku/index.htm

The online solver allows one to view the assembly process for the Medusa chains and shows some analysis on them. It's worth having a look.

All the best

Glyn
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby re'born » Sun Aug 26, 2007 11:37 am

Glyn wrote:re'born wrote:

Perhaps someone else can provide a link with a more precise description of Medusa resolution rules. The best I know of is this (incomplete) description by Ruud.


As the name Medusa was, I believe, coined by Bob Hanson you might find his website interesting.

http://www.stolaf.edu/people/hansonr/sudoku/index.htm

The online solver allows one to view the assembly process for the Medusa chains and shows some analysis on them. It's worth having a look.

All the best

Glyn

Thanks Glyn. I haven't been to Bob's site for a while, but I remember him having some really neat visualizations of 3D-chains. I should probably clarify for those who haven't been around as long that when I say "Ruud's Medusa 3D-chains", I mean the technique programmed into Ruud's excellent solver SudoCue. I do not mean to say that he invented the technique.
re'born
 
Posts: 551
Joined: 31 May 2007

MEDUSA 3D

Postby champagne » Tue Aug 28, 2007 8:40 am

Hello,

This is the first time I write in this forum, but I can, to a certain extent, give an answer to the question raised by re'born


denis wrote
All I could find on Medusa is in terms of colouring. But colouring is not a resolution rule,just a resolution technique. Anyway, the relationship between nrc-chains and Medusa seems to be strong.

re'born wrote:

Perhaps someone else can provide a link with a more precise description of Medusa resolution rules. The best I know of is this (incomplete) description by Ruud.

First of all, I am running my own solver with the same process for nearly one year now.
It can solve (without trial & error) all grids but some idenfied hundreds.

To give an example, it solves the top1465 (not so difficult)and in the gsf list (about 3000 grids), about 90% are solved, mainly in the bottom part of the list.

The process used has the same base as MEDUSA 3D. A limited number of tools have been addded. I call it "general tagging" to avoid any confusion

Solving is done exclusively thru alternate chains (after basic rules including XWINGS ....).


I don't know what is the difference between a resolution rule and a resolution technique, but I would agree that "general tagging" is only a way to ease alternate chains extraction and selection.



It seems to me that my process is much simpler that XYT_chains.... but nobody can be fully objective.

Let me describe briefly the process :

step 1 : more or less what Bob Hanson had done, with groups extension.
A significant difference with Bob Hanson use : there is no forcing chain in my process.
Theese forcing chains have been replaced by intensive use of alternate chains.


step 2 if the grid is still unsolved,
- expanding strong links and weak links thru ALS and their counterpart which I call "Almost Cells".
- looking for multi-chains starting from an Almost Cell killing candidates

step 3 if still not solved (looping process as long as you can expand)
- expanding weak links thru multi-chains starting from an Almost Cell
- restarting the search.

Nothing more, but need for some detailed explainations.

This process absorbs fully what is done thru couples of ALS, but may be ALS nets do more. It could be the fourth step.
It's likely that XZT-chain .. are also equivalent to part of that process.


more details to come if necessary

Kind regards


Champagne

ps : herebelow are the first unsolved grids of gsf's list in the bottom part of the list (supposed to be the easiest to solve)


Code: Select all
100000000006020700080005030300006800002070090040100000007030060000800500000009004,ravel-04/02,_07150
100000006020500040003000700040050000000810400000020080007000300050009020600000001,gsf-2007-05-_04519
003050000400009000080200000200004000090800000005060001000000217001000806000070503,rw-04-06,0,0_04220
100000002090400050006000700050903000000010009000800040700000600030009080002000001,gsf-2007-05-_03465
003050000400009000080200000200004000090800000005060001000000097001000806000070203,rw-04-06,0,0_03349
600000002090400050001000700050943000000105000000800040007000600030009080200000001,coloin-04-10_02805


I am highly interested in getting a solution excluding any T&E to figure out what could be the next fourth step for my solver.
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Wed Aug 29, 2007 5:48 pm

In my introductory post, I gave general definitions and a very simple 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 new nrc-notation (with some modifications of the original, suggested by David).
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
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby re'born » Wed Aug 29, 2007 9:48 pm

denis_berthier wrote: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

I'm working through the SudoRules output step by step and I'm stuck on the conclusion of the 2nd chain. Why does the chain not exclude 9 from r5c1?
Edit1:I now see that the exclusion is made two chains later by the same chain. Strange it doesn't make it all at once.
re'born
 
Posts: 551
Joined: 31 May 2007

solving the grid

Postby champagne » Wed Aug 29, 2007 10:15 pm

hello denis,

I quickly checked your grid.

My solver took 2.7 seconds to solve it.

solving needed step three of my process, ranking the grid in upper class, but not that much difficult.

Far anyway from most grids in gsf's file.

It seems really that "elementary" use of "alternate chains" covers more or less your highly sophisticated tools.

Kind regards

Champagne.
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Wed Aug 29, 2007 10:33 pm

re'born wrote:
denis_berthier wrote:nrczt6-chain {n9 n2}r6c1 - n2{r4c1 r4c7} - n2{r6c9 r2c9} - n4{r2c9 r2c7} - n9{r2c7 r3c7} - n9{r3c8 r5c8} ==> r5c3 <> n9, r5c2 <> n9

I'm working through the SudoRules output step by step and I'm stuck on the conclusion of the 2nd chain. Why does the chain not exclude 9 from r5c1?
Edit1:I now see that the exclusion is made two chains later by the same chain. Strange it doesn't make it all at once.

In nice loop notaton, Denis's "chain" looks like ...
Code: Select all
                          +=9======================+
r5c123-9-r6c1-2-r4c1=2=r4c7-2-r6c9=2=r2c9=4=r2c7=9=r3c7-9-r3c8=9=r5c8-9-r5c123
     +-9-r5c7=9====================================+


implies r5c123<>9
[edit: added missing r5c7]

Here is a much simpler alternative chain ...
Code: Select all
r5c123-9-r6c1-2-r6c9=2=r4c7=9=r5c78-9-r5c123, implies r5c123<>9
Last edited by ronk on Wed Aug 29, 2007 9:11 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby re'born » Wed Aug 29, 2007 11:00 pm

ronk wrote:
re'born wrote:
denis_berthier wrote:nrczt6-chain {n9 n2}r6c1 - n2{r4c1 r4c7} - n2{r6c9 r2c9} - n4{r2c9 r2c7} - n9{r2c7 r3c7} - n9{r3c8 r5c8} ==> r5c3 <> n9, r5c2 <> n9

I'm working through the SudoRules output step by step and I'm stuck on the conclusion of the 2nd chain. Why does the chain not exclude 9 from r5c1?
Edit1:I now see that the exclusion is made two chains later by the same chain. Strange it doesn't make it all at once.

In nice loop notaton, Denis's "chain" looks like ...
Code: Select all
                          +=9======================+  +-9---------------+
r5c123-9-r6c1-2-r4c1=2=r4c7-2-r6c9=2=r2c9=4=r2c7=9=r3c7-9-r3c8=9=r5c8-9-r5c123

implies r5c123<>9

Here is a much simpler alternative chain ...
Code: Select all
r5c123-9-r6c1-2-r6c9=2=r4c7=9=r5c78-9-r5c123, implies r5c123<>9

Exactly! It was this last chain that I saw and figured it must make equivalent deductions to Denis' chain. Alas, it does. It just seems that SudoRules breaks up the deduction for some reason.


Edit1:If we remove the 9 from r5c1, what happens to the next nrczt6-chain which happens to use that 9:?:
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Thu Aug 30, 2007 5:54 am

Ronk, Re'born it should not be a surprise that a puzzle has several solution paths.
In the present case, it is not true that, for my chain
nrczt6-chain {n9 n2}r6c1 - n2{r4c1 r4c7} - n2{r6c9 r2c9} - n4{r2c9 r2c7} - n9{r2c7 r3c7} - n9{r3c8 r5c8} ==> r5c3 <> n9, r5c2 <> n9
your alternative:
r5c123-9-r6c1-2-r6c9=2=r4c7=9=r5c78-9-r5c123, implies r5c123<>9
is much simpler: you are using ALS, when I am not. If you count the candidates involved, you get 12, as in my chain (not counting the targets).
SudoRules has no rule for ALS. At the present time, I can see no reason for adding ALSs, because nrc(z)(t) chains are so general that I have no example of a puzzle that I can't solve with them but that could be solved with ALS. This topic is currently under discussion on the UK forum, where we are looking for such puzzles.

As for the fact that the same chain is used twice to produce 2 deductions it could have produced at the same time, this is only an artifact of SudoRules and of the fact that the target is not attached to the chain: when two steps have the same complexity (here 2 xyzt6 chains), their order is arbitrary.[/quote]
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Next

Return to Advanced solving techniques