Nice loops for elementary level players - the xy-chain

Advanced methods and approaches for solving Sudoku puzzles

Nice loops for elementary level players - the xy-chain

Postby Jeff » Sun Jan 22, 2006 12:22 pm

An xy-chain is a chain in which all cells are linked by bivalue cells except for the cell(s) where the elimination(s) take(s) place. It can be of any length. It can be continuous or discontinuous.

xy-chain is equivalent to all current techniques that use bivalue cells as placeholders:

    xy-ring - Continuous xy-chain of length 4
    xy-wing - Discontinuous xy-chain of length 4
Due to its simplicity, like x-cycle, xy-chain is a subset of nice loops that can be identified without the need of a bilocation/bivalue plot.

In an xy-chain, nice loop propagation always follows pure links with 'weak inference' (drawn as broken lines, each with a -ve label) connected by bivalue cells (refer definitions of 'link', 'strong link', 'strong inference' and 'weak inference' here), eg.

.........[cell 1]-a-[cell 2]-b-[cell 3]-c-[cell 4]-d-[cell 5]-e-[cell 6]-f-[cell 7].........

where the notation :
'-x-' is a link with weak inference of -ve label x
[cell N] is a bivalue cell

In an xy-chain nice loop, if the links propagate in a cyclic manner (ie. no adjacent links are of same label), the loop is said to be 'continuous'.

With continuous xy-chain, the labelled candidate of a link can be eliminated outside the loop but within the unit of the link as demonstrated below:

Nice loop notation:
example 1 - xy-ring: -[r2c2]-3-[r2c5]-6-[r6c5]-4-[r6c2]-2-[r2c2]-
example 2 : -[r1c2]-4-[r1c6]-1-[r5c6]-8-[r4c6]-9-[r6c8]-2-[r4c8]-6-[r4c2]-1-[r1c2]-

Image

A 'discontinuous' xy-chain nice loop has exactly one pair of adjacent links carrying the same label; the discontinuity is located between these 2 links.

At the discontinuity between 2 adjacent links of same label, the labelled candidate can be eliminated from the node as demonstrated below:

Nice loop notation always starts from the discontinuity:
example 3 - xy-wing: [r8c6]-2-[r3c6]-7-[r1c4]-6-[r1c6]-2-[r8c6] => r8c6<>2
example 4: [r8c3]-5-[r4c3]-4-[r4c9]-1-[r6c7]-7-[r2c7]-8-[r2c5]-2-[r8c5]-5-[r8c3] => r8c3<>5

Image

You may have noticed that in box 2, the naked triple is just a continuous xy-chain that concludes the rest of the cells in box 2 must not be 2, 6 and 7.

An xy-chain can be proven by double implications. Consider example 4 above:

Nice loop notation: [r8c3]-5-[r4c3]-4-[r4c9]-1-[r6c7]-7-[r2c7]-8-[r2c5]-2-[r8c5]-5-[r8c3] => r8c3<>5

Proof (Implications can start from any node in the nice loop):
r6c7=1 => r4c9<>1 => r4c9=4 => r4c3<>4 => r4c3=5 => r8c3<>5
r6c7=7 => r2c7<>7 => r2c7=8 => r2c5<>8 => r2c5=2 => r8c5<>2 =>r8c5=5 => r8c3<>5
Therefore r8c3<>5
Last edited by Jeff on Mon Jan 23, 2006 3:37 am, edited 4 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Nice loops for elementary level players - the xy-chain

Postby ronk » Sun Jan 22, 2006 1:37 pm

Jeff wrote:An xy-chain is a chain in which all cells are linked by bivalue cells except for the cell(s) where the elimination(s) take(s) place. It can be of any length. It can be continuous or discontinuous.

Jeff, that's an excellent post with great graphics IMO. On the one hand, I wonder if many people look for an xy-wing within a 3x3 box. OTOH, perhaps making people think "inside the box" (pun:) ) was your intent.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Nice loops for elementary level players - the xy-chain

Postby Jeff » Sun Jan 22, 2006 1:44 pm

ronk wrote:OTOH, perhaps making people think "inside the box" (pun:) ) was your intent.

Just tried to make the xy-wing looks like a wing.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby jdm » Sun Jan 22, 2006 4:08 pm

Lovely, Jeff! Just to make sure I've got this right, couldn't the following also be said about your examples:?

1. In your second continuous example, we can exclude 2 from the rest of box 6.

2. The first discontinuous example could also be viewed as an example of a continous xy-chain.
jdm
 
Posts: 7
Joined: 22 January 2006

Postby Carcul » Sun Jan 22, 2006 4:25 pm

Hi Jdm.

I will answer for Jeff, if you and Jeff don't mind.

Jdm wrote:1. In your second continuous example, we can exclude 2 from the rest of box 6.

2. The first discontinuous example could also be viewed as an example of a continous xy-chain.


Both observations are correct.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby CathyW » Sun Jan 22, 2006 4:33 pm

Thanks Jeff - I think this answers a query I raised in this post: http://forum.enjoysudoku.com/viewtopic.php?t=2594 about eliminations made in a puzzle posted by Tarek.

The position, having made a few entries and identified two swordfishes (4s) was :

Code: Select all
 *-----------*
 |659|.31|.82|
 |...|...|9..|
 |4..|.9.|.5.|
 |---+---+---|
 |...|3..|.4.|
 |1..|...|...|
 |.6.|..8|..3|
 |---+---+---|
 |.1.|.7.|..5|
 |..5|1..|...|
 |28.|945|.71|
 *-----------*


{6}      {5}      {9}      {47}     {3}      {1}      {47}     {8}      {2}     
{378}    {237}    {12378}  {25678}  {2568}   {2467}   {9}      {13}     {467}   
{4}      {237}    {12378}  {2678}   {9}      {267}    {13}     {5}      {67}     
{5789}   {279}    {278}    {3}      {1256}   {2679}   {125678} {4}      {6789}   
{1}      {23479}  {2378}   {2567}   {256}    {24679}  {25678}  {269}    {6789}   
{579}    {6}      {247}    {2457}   {125}    {8}      {1257}   {129}    {3}     
{39}     {1}      {346}    {268}    {7}      {236}    {23468}  {2369}   {5}     
{379}    {3479}   {5}      {1}      {268}    {236}    {2368}   {2369}   {4689}   
{2}      {8}      {36}     {9}      {4}      {5}      {36}     {7}      {1}   


In box 7, we have two bivalue cells at r7c1 and r9c3. Therefore 3s in other cells of box 7 were eliminated. Simple Sudoku did not declare this invalid so I carried on and eliminated the 4 in r7c7 from the bivalue cells r7c3 and r1c7.

Are these xy-chains?
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby Jeff » Sun Jan 22, 2006 5:17 pm

CathyW wrote:In box 7, we have two bivalue cells at r7c1 and r9c3. Therefore 3s in other cells of box 7 were eliminated. ...........Are these xy-chains?

Hi Cathy, In order to eliminate all 3s in other cells in box 7, you need to identify a continuous xy-chain in which one of the links is [r7c1]-3-[r9c3]. Can you list a continuous xy-chain to meet this condition?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby CathyW » Sun Jan 22, 2006 6:06 pm

Jeff wrote:Can you list a continuous xy-chain to meet this condition?

Not at that point - there aren't enough bivalue cells! There's a discontinuous one, if I've understood this correctly, which allows elimination of 3 in r3c3. Cells marked with *.
Code: Select all
{6}      {5}      {9}      {47}     {3}      {1}      {47}     {8}      {2}     
{378}    {237}    {12378}  {25678}  {2568}   {2467}   {9}      {13}     {467}   
{4}      {237}    {123*78}  {2678}   {9}      {267}    {13*}     {5}      {67}     
{5789}   {279}    {278}    {3}      {1256}   {2679}   {125678} {4}      {6789}   
{1}      {23479}  {2378}   {2567}   {256}    {24679}  {25678}  {269}    {6789}   
{579}    {6}      {247}    {2457}   {125}    {8}      {1257}   {129}    {3}     
{39}     {1}      {346}    {268}    {7}      {236}    {23468}  {2369}   {5}     
{379}    {3479}   {5}      {1}      {268}    {236}    {2368}   {2369}   {4689}   
{2}      {8}      {36*}     {9}      {4}      {5}      {36*}     {7}      {1} 


I'm just trying to work out how and why it was possible to eliminate the other 3s in box 7 at the particular stage I'd reached. The bivalue cells must be part of it, but evidently there's something else in the equation. Can anyone analyse this a bit further please?
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby Jeff » Sun Jan 22, 2006 6:18 pm

CathyW wrote:
Jeff wrote:Can you list a continuous xy-chain to meet this condition?

Not at that point - there aren't enough bivalue cells! I'm just trying to work out how and why it was possible to eliminate the other 3s in box 7 at the particular stage I'd reached.

If you cannot list the continuous xy-chain, then the eliminations would have been a happy coincidence.

CathyW wrote:There's a discontinuous one, if I've understood this correctly, which allows elimination of 3 in r3c3.

Likewise, could you list this xy-chain for us?
Last edited by Jeff on Sun Jan 22, 2006 3:27 pm, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby CathyW » Sun Jan 22, 2006 6:57 pm

r9c3(36) -3- r9c7(36) -3- r3c7(13) -3- r3c3(12378) -3- (r9c3)

So, 3 can be eliminated in r3c3 leaving (1278) as candidates in that cell.
Am I right?
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby Jeff » Sun Jan 22, 2006 7:38 pm

CathyW wrote:r9c3(36) -3- r9c7(36) -3- r3c7(13) -3- r3c3(12378) -3- (r9c3)

Sorry Cathy, my description wasn't clear enough.

A 'discontinuous' xy-chain nice loop has exactly one discontinuity between 2 adjacent links with weak inference of the same label.

This means in a discontinuous xy-chain, exactly one pair of adjacent links can have the same label, and this labelled candidate can be eliminated from the cell between these 2 links.

Your chain above has more than one pair of links with the same label and is therefore not valid.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby CathyW » Sun Jan 22, 2006 9:00 pm

So how come I could still "validly" eliminate 3 from r3c3? Was this another "happy coincidence" or is there another technique involving bivalue cells that permits the elimination? I can see I shall have to study these xy-chains more closely.
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby emm » Sun Jan 22, 2006 9:52 pm

Cathy - this interested me - the closest I could get are these chains.

r8c2=3 => r9c3=6
r8c2=7 => 39 39 pair => r9c3=6
r8c2=9 => r7c1=3 => r9c3=6
r8c2=4 => 36 36 pair => ?

I wondered if one of bennys ALSs was in there but I just can't get my head around those.

I expect if Jeff says it's a happy accident then it probably is - nice description of nice loops BTW, Jeff!:D
emm
 
Posts: 987
Joined: 02 July 2005

Postby Jeff » Mon Jan 23, 2006 7:14 am

em wrote:- nice description of nice loops BTW, Jeff!:D

Thanks Em.
Jeff
 
Posts: 708
Joined: 01 August 2005


Return to Advanced solving techniques