xy-chain: description and example

Advanced methods and approaches for solving Sudoku puzzles

xy-chain: description and example

Postby Jeff » Sun Aug 07, 2005 6:11 pm

xy-chain is an extension of the xy-wing.

For easy reference, the name xy-chain is proposed without knowing whether the technique has already got a proper name.

xy-chain is a special case of forcing chains, and can be considered as another simplest application of such technique which involves more than 4 cells.

Similar to the xy-wing, the xy-chain makes use of the special property of cells with 2 candidates.

If three cells A, B, C, with A-B in the same unit and B-C in the same unit, have candidates zx, xy and yz respectively, then z can be removed from the candidates of all the cells (different from A, B, C) contained in the intersection of two units that contain A and C respectively. This is the definition of an xy-wing (refer Nick's thread on xy-wing).

We can now describe the xy-chain:

If n cells A, B, C,.............X, Y, Z, with A-B in the same unit, B-C in the same unit, C-D in the same unit,................. and Y-Z in the same unit, have candidates za, ab, bc,..............wx, xy, yz respectively, then z can be removed from the candidates of all the cells (different from A, B, C,........., Z) contained in the intersection of the two units that contain A and Z respectively.

The reason for that is similar to the xy-wing: Y contains either x or y. If Y=y then Z=z. If Y=x, then X=w,................, then C=b, then B=a, then A=z. Therefore either A or Z contains z. Therefore a cell located inside the intersection of two units containing A and Z cannot contain z.

Consider the following examples:

Image

Example 1 is an xy-wing; z can be removed from r4c5.

Example 2 is an xy-chain;
r2c5=a => r8c5=z.
r2c5=b => r2c7=c => r6c7=d => r4c9=e => r4c3=z.
Therefore r8c3 not=z. Therefore, z can be removed from r8c3.

Example 3 is a very long xy-chain. Although z can be removed from r3c8, the process of searching for such long chain can be quite tedious. Long xy-chain should not be considered unless all other techniques are unsuccessful.

Let's see how a very hard puzzle can be solved by a simple xy-chain:

Image

The xy-chain is r4c2-r5c2-r5c4-r5c8-r6c8, with candidates 76-62-23-35-57.
If r5c2=6, then r4c2=7.
If r5c2=2, then r5c4=3, then r5c8=5, then r6c8=7.
As either r4c2=7 or r6c8=7, r6c2 cannot be 7.
Therefore r6c2=2 and the rest is simple.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Scott H » Wed Aug 10, 2005 4:16 am

I prefer "doubleton chain" over "xy-chain" as a name for this subset of forcing chains.

Doubleton chains are a very nice subset of forcing chains for their ease of recognition by humans.

The length of doubleton chains as humans count (steps between successive cells in the chain) is about half their length as an implication chain. This is because, when viewed as an implication chain, changing numbers in a doubleton is a separate link in the implication chain, which happens to remain in one cell. The implication "link" within a doubleton cell is also a strong link, which means all links between doubleton cells can be weak.
Scott H
 
Posts: 73
Joined: 28 July 2005

Postby Nick70 » Wed Aug 10, 2005 9:47 am

Scott H wrote:Doubleton chains are a very nice subset of forcing chains for their ease of recognition by humans.

Agreed. I like the name "xy-chain" myself.

I also like, very much, that xy-wing is just a xy-chain of length 3.

For a solver programmer, xy-chains can be found by the same algorithm that finds generic forcing chains, simply by limiting the kind of links it uses. In example 2 above, it would find this:

r2c7<>c => r2c7=b => r2c5<>b => r2c5=a => r8c5<>a => r8c5=z => r8c3<>z.
r6c7<>c => r6c7=d => r4c9<>d => r4c9=e => r4c3<>e => r4c3=z => r8c3<>z.

of course xy-chains can be represented more succintly than normal double forcing chains.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby tso » Thu Aug 11, 2005 1:01 am

As defined, the first diagram would be an xy-chain, but the second and third would not. Is there any reason to distinguish between these three?

Code: Select all
12  .  . | . 19  . | .  .  .
 .  .  . | .  .  . | .  .  .
 . 23  . | .  .  . | .  .  . 
---------+---------+--------
 . 34  . | .  .  . | .  .  .
 .  . 45 | . 15  . | .  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .

If r1c1= then r1c5=9
If r1c1=2 then ... r1c5=9
Therefore, r1c5=9


Code: Select all
12  .  . | . 19  . | .  .  .
 .  .  . | .  .  . | .  .  .
 . 23  . | .  .  . | .  .  . 
---------+---------+--------
 . 23  . | .  .  . | .  .  .
 .  . 23 | . 13  . | .  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .

If r1c1=1 then r1c5=9
If r1c1=2 then ... r1c5=9
Therefore, r1c5=9

Code: Select all
12  .  . | . 19  . | .  .  .
 .  .  . | .  .  . | .  .  .
 . 12  . | .  .  . | .  .  . 
---------+---------+--------
 . 12  . | .  .  . | .  .  .
 .  . 12 | . 12  . | .  .  .
 .  .  . | .  .  . | .  .  .
---------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .


If r1c1=1 then r1c5=9
If r1c1=2 then ... r1c5=9
Therefore, r1c5=9
tso
 
Posts: 798
Joined: 22 June 2005

Postby Jeff » Thu Aug 11, 2005 2:13 am

Tso

Examples 1 & 2 are xy-chains, but example 3 is not.

xy-chain is used to eliminate a candidate in cells contained inside the intersection of the start cell and end cell of the chain. Either the start cell or end cell must contain the condidate under consideration.

For example 1, the xy-chain is 12-23-34-45-51 of length 5, so either the start cell or end cell must be 1. This allow elimination of the 1 in r1c5.

For example 2, the xy-chain is 12-23-32-23-31 of length 5 , so either the start cell or end cell must be 1. This allow elimination of the 1 in r1c5.

Example 3 is not an xy-chain; because when the start cell is 2, the end cell is also 2. This doesn't allow elimination of the 1 in r1c5.

I understand that there is just a typing error in example 3. However, the question is answered in example 2 where za=12, ab=23, bc=32, cd=23 and dz=31. This is still considered as an xy-chain and the listed order of the numbers is how we could easily identify it within human ability.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Thu Aug 11, 2005 3:04 am

Oops. No matter how careful, that always seems to happen. So to be clear, this would still be considered an xy-chain:

Code: Select all
12  .  . | .  . 19 | .  .  .
 .  .  . | .  .  . | .  .  .
 . 12  . | .  .  . | .  .  . 
---------+---------+--------
 . 12  . | .  .  . | .  .  .
 .  . 12 | . 12  . | .  .  .
 .  .  . | .  . 12 | .  .  .
---------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .

If r1c1=1 then r1c6=9
If r1c1=2 then ... r1c6=9
Therefore, r1c5=9

Is this correct?

Is this example below what you would consider an non-xy-wing forcing chain, assuming of course, that there are exactly 2 cells in row 5 that can contain a 4?

Code: Select all
12  .  . | .  . 19 | .  .  .
 .  .  . | .  .  . | .  .  .
 . 23  . | .  .  . | .  .  . 
---------+---------+--------
 . 34  . | .  .  . | .  .  .
 .  . 489| . 134 . | .  .  .
 .  .  . | .  . 14 | .  .  .  <--[edited to correct yet another typo]
---------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .


If r1c1=1 then r1c6=9
If r1c1=2 then ... r1c6=9
Therefore, r1c5=9

Does it follow that all forcing chains that use only cells that contain exactly 2 candidates are xy-chains? So coloring and xy-chains are the two pure forms of forcing chains, and the example just above is the generic or mixed forcing chain?
Last edited by tso on Thu Aug 11, 2005 12:41 am, edited 1 time in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Jeff » Thu Aug 11, 2005 4:15 am

Tso

Typo again. Even with further assumptions that the 4s in box (2,1) and the 4s in box (2,2) are strong links:

If r1c1=2 -> r3c2=3 -> r4c2=4 -> r5c3<>4 -> r5c5=4 -> r5c6=9 -> r1c6<>9

Anyhow, the answer is yes. xy-chain is a pure form of forcing chains. Not too sure which colouring though as there are few types it. But I say that Angus' colouring is a pure form.

xy-chain is easy to use because no checking of strong link or weak link is required.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Thu Aug 11, 2005 4:43 am

Got it. I've got to try to be more careful of tyops.
tso
 
Posts: 798
Joined: 22 June 2005


Return to Advanced solving techniques

cron