Sudoku Players' Forum (clone)

Definition of an xyt-chain, elementary example and indications for finding them

This has already been largely discussed in the UK forum
(http://www.sudoku.org.uk/discus/messages/29/4236.html?1185340042),
but since the participants are different, it may raise different reactions.
Also, since xyt-chains are a simple but very powerful extension of xy-chains, it may be of interest to a large number of players.

Contrary to complex chains, xyt-chains are, IMO, relatively easy to find (after some training, as for anything new).
In this first post, I'll define them, give a simple example and briefly say how to find them.
(If you also read my thread on Supersymmetries and hidden chains, then, combining the two ideas, you'll know how to find hxy and hxyt-chains)


1) Definition
Let me first introduce my representation of a standard xy-chain (of length 4) and some vocabulary:
{1 2} - {2 3} - {3 4} - {4 1}.
All the cells must be different (in particular, the first and the last), i.e. the chain is "open" and has no internal loops (this apparent restriction is justified, because I have proven that loops would not allow more eliminations).
Here "-" stands for any type of link (row, column or block/box as you prefer) and 1, 2, 3, 4 are any candidates (they may be considered as shorthands for variables x1, x2, x3, x4). The curly brackets indicate that the sets of candidates in each cell of the chain are limited to the instantiations of the variables displayed.
Two variables in the same cell must have different values, but, for full generality, two variables in different cells, that never appear in the same cell, may be equal.
For xy-chains, all the cells must be "bivalued" (i.e. have exactly 2 candidates).
The xy-chain rule (as I have re-formulated it) says that one can eliminate x1 from any target cell (i.e. any cell that does not belong to the chain and that shares a unit with both of its endpoints).
Candidates x2 in cell 1, x3 in cell 2, x4 in cell 4, … I call the right linking candidates of these cells, whereas candidates x1 in cell 1, x2 in cell 2, x3 in cell 3, … I call the left linking candidates of these cells.

In my book ("The Hidden Logic of Sudoku", a long excerpt of which you can find on my web pages), I have introduced xyt-chains, a simple but very powerful generalisation of xy-chains. The idea is that in an xy-chain a cell C in the chain may be allowed any additional candidate (i.e. other than the left and right linking candidates) provided that this candidate alraedy appears as the right linking candidate of a previous cell C' in the chain such that C shares a unit with C'. Note that, whereas xy-chains are symmetric (head and tail can be reversed), this is no longer the case for xyt-chains. But the underlying logic is very similar and proving the mathematical validity of the xyt-chain rule : (one can eliminate x1 from any target cell) can be done straightforwardly, along the same lines as for an xy-chain.

An xyt-chain (of length 4) is represented by the following pattern:
{1 2} - {2 3} - {3 4 (2#1)} - {4 1 (2#1)(3#2)} ,
where all the cells are still different and candidates between normal brackets inside a cell are optional and are allowed in a cell provided that this cell is linked to the cell whose number in the chain follows the # sign.
In details:
- cell 1 has exactly the 2 different values x1 and x2,
- cell 2 has exactly the 2 different values x2 and x3,
(therefore the first two cells are the same as in an xy-chain),
- cell 3 has the 2 different values x3 and x4 and it may have additional value x2, provided that cell 3 is linked to cell 1,
- cell 4 has the 2 different values x4 and x1 and it may have additional value x2 provided that it is linked to cell 1 and it may have additional value x3 provided that it is linked to cell 2.
Similar definitions and representations apply for longer chains. In any case, the farther we go towards the tail of the chain, the more additional values we may have.

Re-elaborating on a remark by Michael McWilliams in the UK forum, this can also be stated in a less formal way:
when you build an xyt-chain from head to tail, any candidate that has already been chosen as a right linking candidate of a previous cell in the chain allows you to forget its presence as an extra candidate (but not as a potential right linking value) in any cell that it sees (i.e. it is linked to) further along the same chain.
Notice that, for full generality, some care must be taken in the formulation (because the same number can reappear in different cells as a linking candidate.

2) Elementary example
(you can see much more complex ones in the UK forum or in the "online supplements" section in my web pages). (0 indicates an empty cell)
946512738
528600194
100849256
281405000
054000810
069108540
615084320
800201405
402050081

Solution path (as generated by my SudoRules solver):
number 6 : row R5 interaction with block B5
==> 6 eliminated from the candidates for R4C5
number 9 : xyt4-chain on cells R9C7*, R8C8, R8C3 and R8C2* with numbers 9, 6, 7 and 3
==> 9 eliminated from the candidates for R9C2
number 9 : hidden-single-in-block B7 ==> R8C2 = 9
number 9 : column C5 interaction with block B5
==> 9 eliminated from the candidates for R5C4
numbers 3 and 7 : naked-pairs-in-row R5: R5C1-R5C4
==> 7 eliminated from the candidates for R5C9
==> 3 eliminated from the candidates for R5C9
==> 7 eliminated from the candidates for R5C6
==> 3 eliminated from the candidates for R5C6
...(Naked-Singles and Hidden-Singles)…
946512738
528637194
137849256
281475963
754396812
369128547
615784329
893261475
472953681


3) How to find xyt-chains
Since the first two cells of an xyt-chain satisfy the same conditions as those of an xy-chain, you start the same way, and you get {1 2} - {2 3}.
Call these two cells the seed of the chain.
Once you have chosen a seed (and you therefore know x1, x2 and x3), look for the third cell among those that are linked to the second, contain x3 among their candidates, another candidate x4 (which will be the right linking candidate of the new cell) and:
- either are are bivalued,
- or are trivalued, are also linked to the first cell and contain x2 as their third candidate,
Then look for the fourth cell among those that are linked to the third, contain x4 among their candidates, another candidate x5 (which will be the right linking candidate of the new cell) and:
- either are are bivalued,
- or are trivalued, are also linked to the first cell and contain x2 as their third candidate,
- or are trivalued, are also linked to the second cell and contain x3 as their third candidate,
- or are quadrivalued, are also linked to the first cell and contain x2 as their third candidate, are also linked to the second cell and contain x3 as their fourth candidate.
Of course you can always restrict your search to cells that are bi- or tri-valued. You won't find all the xyt-chains, but most of them. Indeed, xyt-chains that have two additional candidates in a cell are rare (because of the constraints this imposes on the links with previous cells).
Notice that a right linking candidate of a previous cell may reappear as the right linking candidate of a new cell (and not only as an additional candidate), so that some care must be taken in the proper formulation of the rule and the methods used to spot its occurences.

How do you do this in practice?
Personally, I simply draw an arrow from each cell to the next, with starting point on the right linking candidate (and, this is convenient but not really necessary, arriving on the left linking candidate of the next cell).
Instead of drawing arrows, you can also use a colouring technique that has recently been devised by John MacLeod (see his original post here: http://www.sudoku.org.uk/discus/messages/29/4268.html?1185339098). I'll describe it as follows.
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 value) of any candidate that sees the same number already coloured in blue,
- colour in blue the right linking candidate of the cell you have just added to the chain.

The relationship between the two methods is obvious: blue candidates correspond to starting points of arrows.
Each method has different advantages:
- with colouring, you avoid drawing arrows on the grid, but you loose the information on the ordering of the cells,
- with arrows, you can re-use the initial part of the chain to build another one, but you overload the grid with arrows.


4) Conclusion
I think you now have all the information necessary to start using xyt-chains. But I can provide more if needed.

denis_berthier wrote:number 9 : xyt4-chain on cells R9C7*, R8C8, R8C3 and R8C2* with numbers 9, 6, 7 and 3
==> 9 eliminated from the candidates for R9C2

To answer the question from the other thread: To express this elimination as a nice loop is easy, when you have studied it. Do it yourself to get some practice (btw i am no expert in this notation, i myself use forcing nets instead of them, but what can be written in one of these notations, can also be done in the other).

ravel wrote:

denis_berthier wrote:number 9 : xyt4-chain on cells R9C7*, R8C8, R8C3 and R8C2* with numbers 9, 6, 7 and 3
==> 9 eliminated from the candidates for R9C2

To answer the question from the other thread: To express this elimination as a nice loop is easy, when you have studied it. Do it yourself to get some practice (btw i am no expert in this notation, i myself use forcing nets instead of them, but what can be written in one of these notations, can also be done in the other).

Many notations can be used to express the same thing and if you mean that, instead of my notation, I could use another one, that's likely to be true. But it doesn't prove that one rule is a particular case of another.


Let me therefore restate what I consider of practical importance for the players.
If A and B are (sets of) resolution rules, define "B can be reduced to A" as meaning two things at the same time:
- A is simpler than B (as a justification of this condition: would anybody say that a hip of stones can be reduced to Notre Dame? - yes, I live in Paris).
- one can explain B in terms of A.
This relationship is particularly interesting when it is not symmetric, i.e. when A cannot be explained in terms of B.

For instance, I have proved in my book that xy-chains with loops can be reduced to shorter xy-chains without loops plus elementary rules. But the converse is obviously false (an xy-chain cannot always be extended into an xy-loop). The practical consequence is that it is not necessary to look for xy-chains with loops (you can if you like loops, but it is not necessary).
Similarly I have proved that xyt-chains of length 3 can be reduced to xy-chains of length 3, plus simple interaction rules (between rows or columns and blocks) plus Naked Triplets.
And I have also proved that xyt-chains of any length ≥ 4 cannot in general be reduced to shorter xyt-chains and to xy or hxy chains.


I say that xyt-chains cannot be reduced to Nice Loops in this sense, simply because Nice Loops (in their general formulation) are not simpler than xyt-chains. But there is also a second reason: not all xyt-chains are Nice Loops (even though some may be).

It may be the case that one will prove some day that a known technique subsumes (i.e. is more general than) xyt-chains, but this has not yet been done and, as long as this hypothetical technique is more complex than xyt-chains, I don't think it will be a sufficient reason for forgetting about xyt-chains.

Fine, so things become clearer.
I never argued against xyt-chains or your reduction proofs.
I agree, that not all are Nice Loops. But the eliminations also can be expressed as nice loops.
Almost locked sets have been used in nice loops for a long time. See e.g. this one by Carcul dated Jan 2006.

I don't think that I understand what your xyt-chains are yet. Your example in this thread is exactly the type of situation I looked at in mypost, namely a (1,2)<9>-set. However, you wrote in your other thread that

denis_berthier wrote:re'born claims about xyt-chains are just unfounded

and

denis_berthier wrote:in your post dated 06/20/2007, you have not noticed that seeing is not enough for allowing the "obstructions" to be eliminated.

Now I'm still not sure what claim I made about xyt-chains (other than that if I understood them properly that I had independently stumbled upon them), but what does seem clear is that you don't think my post has anything to do with them, or at the very least, I miss the point.

So let me offer you the first main example of my thread:

Code: Select all

   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   * |   .  79 87(9)
   .   .   . |   .   .   . |   .   . 98(7)
 ------------+-------------+------------
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
 ------------+-------------+------------
   .   .   . |   .   .  37 |   .   .  79
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .  93 |   .   .   .


Given the way I had read about your xyt-chains, I would have thought that this would be an example. However, the rules you wrote in this topic only seem to allow me to add the 9 in r2c9, not the 7 in r3c9. However, there is no harm in adding the 7. What am I missing? Am I allowed to work right to left as well? That is can I write:
{9 3} - {3 7} - {7 9} - {9 8 (7#6)} - {8 7 (9#3)} - {7 9}

denis_berthier wrote:It may be the case that one will prove some day that a known technique subsumes (i.e. is more general than) xyt-chains, but this has not yet been done and, as long as this hypothetical technique is more complex than xyt-chains, I don't think it will be a sufficient reason for forgetting about xyt-chains.

Without understanding xyt-chains I only say this as speculation, but I think that a technique that subsumes xyt-chains is subset counting. aeb's extended subset principle gives a very short proof of what I do in my thread and it extends quite easily to xy-chains (discontinuous or continuous) with repeated links.

ravel wrote:I never argued against xyt-chains or your reduction proofs.
I agree, that not all are Nice Loops. But the eliminations also can be expressed as nice loops.

Now you have to explain that. I just don't understand. How can the eliminations of an xyt-chain that is not a Nice Loop be expressed as Nice Loops?

ravel wrote:Almost locked sets have been used in nice loops for a long time. See e.g. this one by Carcul dated Jan 2006.

But xyt-chains do not reduce to ALS or to NL with ALS.

re'born wrote:Given the way I had read about your xyt-chains, I would have thought that this would be an example. However, the rules you wrote in this topic only seem to allow me to add the 9 in r2c9, not the 7 in r3c9. However, there is no harm in adding the 7. What am I missing? Am I allowed to work right to left as well? That is can I write:
{9 3} - {3 7} - {7 9} - {9 8 (7#6)} - {8 7 (9#3)} - {7 9}

xyt-chains propagate inferences unidirectionally.

denis_berthier wrote:

ravel wrote:I never argued against xyt-chains or your reduction proofs.
I agree, that not all are Nice Loops. But the eliminations also can be expressed as nice loops.

How can the eliminations of an xyt-chain that is not a Nice Loop be expressed as Nice Loops?

Depends upon the definition of Nice Loop that one uses but, as a minimum, ravel's statement can be taken to mean an xyt-chain can be expressed in Nice Loop notation.

re'born wrote:What am I missing? Am I allowed to work right to left as well? That is can I write:
{9 3} - {3 7} - {7 9} - {9 8 (7#6)} - {8 7 (9#3)} - {7 9}

No, this is not an xyt-chain. 9#3 in cell 5 is OK, but 7#6 is not allowed in cell 4. If this is the pattern you use in your elimination, I'm very curious to know how you can justify it without Hinges.

The pattern for an xyt-chain of length 6 is:
{1 2} - {2 3} - {3 4 (2#1)} - {4 5 (2#1)(3#2)} - {5 6 (2#1)(3#2)(4#3)} - {6 1 (2#1)(3#2) (4#3) (5#4)},
from which you see that you can only work from left to right.

re'born wrote:

denis_berthier wrote:It may be the case that one will prove some day that a known technique subsumes (i.e. is more general than) xyt-chains, but this has not yet been done and, as long as this hypothetical technique is more complex than xyt-chains, I don't think it will be a sufficient reason for forgetting about xyt-chains.

Without understanding xyt-chains I only say this as speculation, but I think that a technique that subsumes xyt-chains is subset counting. aeb's extended subset principle gives a very short proof of what I do in my thread and it extends quite easily to xy-chains (discontinuous or continuous) with repeated links.

I don't know if subset counting subsumes xyt-chains, but, if such was the case, you'd still have to show that it is not more complex if you want to have it replace xyt-chains.
For the player (and this is the Players Forum), more general very rarely means better.

This gives me the occasion for some add for my book - which is also useful if you want to understand what I'm presenting in this forum.
All the rules I introduce in my book, and the extended grid as well, are player oriented. I've not tried to do a review of all the most intricate rules known as of the day of the publishing, but to find a limited set of rules that could be applied by a moderately advanced player AND could solve most (actually 97%) of the randomly generated puzzles.
By mere chance, it is the case that it can also solve some top-something puzzles (e.g. some of Ruud's top1000 as you can see from my web pages - "online supplements" section).

denis_berthier wrote:

ravel wrote:Do you have an example of an elimination, that could not be expressed with a nice loop also ?

As I said, xyt-chains are discussed in the thread for xyt-chains.
Look at the example there and, for a start, try to express it as a Nice Loop.
And please answer in the other thread.

denis_berthier wrote:number 9 : xyt4-chain on cells R9C7*, R8C8, R8C3 and R8C2* with numbers 9, 6, 7 and 3
==> 9 eliminated from the candidates for R9C2

Code: Select all

 9     4     6     | 5     1     2     | 7     3     8
 5     2     8     | 6     37    37    | 1     9     4
 1     37    37    | 8     4     9     | 2     5     6
-------------------+-------------------+------------------
 2     8     1     | 4     379   5     | 69    67    379
 37    5     4     | 379   23679 367   | 8     1     2379
 37    6     9     | 1     237   8     | 5     4     237
-------------------+-------------------+------------------
 6     1     5     | 79    8     4     | 3     2     79
 8    A379  A37    | 2     3679  1     | 4    *67    5
 4     37-9  2     | 379   5     367   |*69    8     1

 r9c2-9-r9c7-6-r8c8-7-{ALS:r8c23}-9-r9c2, implies r9c2<>9

IMO you'll need to point to a better example.

[edit: adding missing digit '7' to nice loop and corrected elim shown on grid]

ronk wrote:xyt-chains propagate inferences unidirectionally.

That's absolutely right.

ronk wrote:as a minimum, ravel's statement can be taken to mean an xyt-chain can be expressed in Nice Loop notation.

If you understand it that way, it is an innocuous matter of notation. I'm not especially tied to mine, although it is convenient.
Nevertheless, how do you express (3#2), i.e. an optional candidate whose presence is conditioned by an extra link, in NL notation?

denis_berthier wrote:If you understand it that way, it is an innocuous matter of notation. I'm not especially tied to mine, although it is convenient.
Nevertheless, how do you express (3#2), i.e. an optional candidate whose presence is conditioned by an extra link, in NL notation?

Notation is a tricky question when it comes to Nice Loops. Concidering how few people in the world actually uses this notation, it is hard to say what is right and wrong, specially since so many of the main contributors uses a very different notation.

Here is an example of my Nice Loop notation:

Code: Select all

 7      126      8       |  459    4569   4569   |  3      1456   1259 
AC469  C36      C3469    |  2     C34569  1      | -4679   45678 -5789 
 5      1236     12469   |  78     349    78     |  12469  146    129   
-------------------------+-----------------------+----------------------
A189    4        1579    |  3579  B59     3579   |  178    2      6     
 3      1267     12679   |  479    8      2469   |  147    1457   157   
 268    25678    2567    |  1      2456   24567  |  478    9      3     
-------------------------+-----------------------+----------------------
 128    9        12357   |  6      125    2358   |  127    1378   4     
 12468  12368    12346   |  3489   7      23489  |  5      1368   1289 
 12468  1235678  1234567 |  34589  12459  234589 |  12679  13678  12789

A{[r2c1]=9=[r4c1]} -9- B{[r4c5](9|5)} -5- C{[r2c5]-5-[r2c1235](5|346|9)-9-[r2c135]}

[r2c79]<>9.

A: Strong Link between the cells [r2c1] and [r4c1] for the number 9.
B: Almost Locked Set in the cells [r4c5] with the numbers (59).
C: Almost Locked Set in the cells [r2c1235] with the numbers (34569).


So as far as I am concerned, there is nothing in the example that you have given that has not been done before in Nice Loop notation. I am still intrigued to see an example of your xyt-chain that can't be expressed as a Nice Loop.

Havard

denis_berthier wrote:The pattern for an xyt-chain of length 6 is:
{1 2} - {2 3} - {3 4 (2#1)} - {4 5 (2#1)(3#2)} - {5 6 (2#1)(3#2)(4#3)} - {6 1 (2#1)(3#2) (4#3) (5#4)}

A possible way to express this as nice loop (in Carcul's sense) is to use multiple inferences (lets say the cells are named A through F, X is the cell, where 1 is eliminated):
X-1-A-2(-2-C)(-2-D)(-2-E)(-2-F)-B-3(-3-D)(-3-E)(-3-F)-C-4(-4-E)(-4-F)-D-5-(-5-F)-E-6-F-1-X
In most cases a shorter notation will be possible, often without any multiple inferences.

ravel wrote:

denis_berthier wrote:The pattern for an xyt-chain of length 6 is:
{1 2} - {2 3} - {3 4 (2#1)} - {4 5 (2#1)(3#2)} - {5 6 (2#1)(3#2)(4#3)} - {6 1 (2#1)(3#2) (4#3) (5#4)}

A possible way to express this as nice loop (in Carcul's sense) is to use multiple inferences (lets say the cells are named A through F, X is the cell, where 1 is eliminated):
X-1-A-2(-2-C)(-2-D)(-2-E)(-2-F)-B-3(-3-D)(-3-E)(-3-F)-C-4(-4-E)(-4-F)-D-5-(-5-F)-E-6-F-1-X
In most cases a shorter notation will be possible, often without any multiple inferences.

It may be a matter of taste or of habit, but for me, it obscures the fact that A is linked to B, B to C,…
Anyway, you can use the notation you prefer. xyt-chains are not a matter of notation.

ronk wrote:r9c2-9-r9c7-6-r8c8-{ALS:r8c23}-9-r9c2, implies r9c2<>9

ALS are not in general simpler than xyt-chains, even though the present case is comparable.

ronk wrote:IMO you'll need to point to a better example.

I don't miss examples.
How do you eliminate 3 from R5C1 in the following:
.784...1.
4..7.1...
1.382.6..
8.......2
.24...581
5...8...6
..1.4.96.
...613...
.4...812.

denis_berthier wrote:... it obscures the fact that A is linked to B, B to C,…

No, when you filter out the multiple inferences
A-2(-2-C)(-2-D)(-2-E)(-2-F)-B
you have the link
A-2-B.
Maybe there is also a shortcut for writing (-2-C)(-2-D)(-2-E)(-2-F), i am not sure.

As i already stated, it is not the notation i prefer. But Carculs samples are such rich of great deductions, that we cannot ignore it.