Setting up an XYchain

Advanced methods and approaches for solving Sudoku puzzles

Setting up an XYchain

Postby stumble » Sat Jan 05, 2008 6:23 pm

I wonder if anyone can give me any tips on logical way to start setting up an XYchain? My current method is just bumbling around, starting with a bi-value cell with a candidate that appears fairly frequently in the puzzle and that I'd like to eliminate WHEREEVER my chain happens to end up.
Case in point: here's my notes to myself on the BrainBasher1-4-08SuperHard puzzle:
Swordfish on 6=>r4c9<>6
XychainOn6 r8c7-r8c3-r7c1-r5c1-r4c1-r4c8-r9c8=>r9c7<>6, r9c9<>6
XychainOn4 r9c9-r9c8-r8c7-r8c3-r6c3-r4c1-r4c6=>r6c6<>4
XychainOn4 r6c3-r4c1-r4c6=>r6c6<>4
XychainOn4 r9c7-r9c4-r7c4-r7c1-r4c1-r5c1-r5c3=>r5c7<>4
14 16 16 16 69 19 14 (saved clps)

I think the final XYchain would have broken the puzzle in the first place, (still too lazy to start puzzle over again to find out) precluding all that thrashing around.
Any hope of aiming at the right place initially? Should I post the puzzle for you guys to analyze?
stumble
 
Posts: 52
Joined: 29 October 2007

Postby daj95376 » Sat Jan 05, 2008 7:24 pm

The only suggestion that I have is to say that you missed an important elimination in one of your XY-Chains (that also happens to be an XY-Wing).

XychainOn4 r6c3-r4c1-r4c6=>r6c46<>4
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Sped » Sun Jan 06, 2008 7:07 pm

BrainBasher 1-4-08 SuperHard:

Code: Select all
 *-----------*
 |...|.2.|9..|
 |7..|..1|.4.|
 |569|...|2..|
 |---+---+---|
 |.87|...|...|
 |...|263|...|
 |...|...|51.|
 |---+---+---|
 |..5|...|783|
 |.4.|8..|..5|
 |..3|.9.|...|
 *-----------*


After basic steps:

Code: Select all
 *-----------------------------------------------------------*
 | 4     1     8     | 3     2     6     | 9     5     7     |
 | 7     3     2     | 9     5     1     | 68*   4     68*   |
 | 5     6     9     | 47    78    48    | 2     3     1     |
 |-------------------+-------------------+-------------------|
 | 69    8     7     | 5     1     49    | 3     26   24(6)9 |
 | 19    5     14    | 2     6     3     | 48    7     489   |
 | 3     2     46*   | 47    78    489   | 5     1     469*  |
 |-------------------+-------------------+-------------------|
 | 16    9     5     | 16    4     2     | 7     8     3     |
 | 2     4     16*   | 8     3     7     | 16*   9     5     |
 | 8     7     3     | 16    9     5     | 14(6) 26   24(6)  |
 *-----------------------------------------------------------*


You could have avoided some thrasing around by recognizing that the swordfish eliminates the 6s in r9c79 as well as r4c9.

I don't like swordfish. When I solved this I used a continuous xy chain (loop?) that produced the same eliminations:

Code: Select all
 *-----------------------------------------------------------*
 | 4     1     8     | 3     2     6     | 9     5     7     |
 | 7     3     2     | 9     5     1     | 68    4     68    |
 | 5     6     9     | 47    78    48    | 2     3     1     |
 |-------------------+-------------------+-------------------|
 | 69*   8     7     | 5     1     49    | 3     26*  24(6)9 |
 | 19*   5     14    | 2     6     3     | 48    7     489   |
 | 3     2     46    | 47    78    489   | 5     1     469   |
 |-------------------+-------------------+-------------------|
 | 16*   9     5     | 16*   4     2     | 7     8     3     |
 | 2     4     16    | 8     3     7     | 16    9     5     |
 | 8     7     3     | 16*   9     5     | 14(6) 26*  24(6)  |
 *-----------------------------------------------------------*


As a nice loop (hope I got the notation right):

-1-[r5c1]-9-[r4c1]-6-[r4c8]-2-[r9c8]-6-[r9c4]-1-[r7c4]-6-[r7c1]-1-[r5c1]-9-, => r4c9,r9c79<>6

After removing the three 6s it still took a couple of xy wings to finish.

As for xy chain tips.. you're doing fine. When you find a chain, be sure not to miss any eliminations. Keep an eye out for continuous loops, like the one above.
Sped
 
Posts: 126
Joined: 26 March 2006

Postby stumble » Sun Jan 06, 2008 7:46 pm

Sped wrote:BrainBasher 1-4-08 SuperHard:

Code: Select all
 *-----------*
 |...|.2.|9..|
 |7..|..1|.4.|
 |569|...|2..|
 |---+---+---|
 |.87|...|...|
 |...|263|...|
 |...|...|51.|
 |---+---+---|
 |..5|...|783|
 |.4.|8..|..5|
 |..3|.9.|...|
 *-----------*


After basic steps:

Code: Select all
 *-----------------------------------------------------------*
 | 4     1     8     | 3     2     6     | 9     5     7     |
 | 7     3     2     | 9     5     1     | 68*   4     68*   |
 | 5     6     9     | 47    78    48    | 2     3     1     |
 |-------------------+-------------------+-------------------|
 | 69    8     7     | 5     1     49    | 3     26   24(6)9 |
 | 19    5     14    | 2     6     3     | 48    7     489   |
 | 3     2     46*   | 47    78    489   | 5     1     469*  |
 |-------------------+-------------------+-------------------|
 | 16    9     5     | 16    4     2     | 7     8     3     |
 | 2     4     16*   | 8     3     7     | 16*   9     5     |
 | 8     7     3     | 16    9     5     | 14(6) 26   24(6)  |
 *-----------------------------------------------------------*


You could have avoided some thrasing around by recognizing that the swordfish eliminates the 6s in r9c79 as well as r4c9.

I don't like swordfish. When I solved this I used a continuous xy chain (loop?) that produced the same eliminations:

Code: Select all
 *-----------------------------------------------------------*
 | 4     1     8     | 3     2     6     | 9     5     7     |
 | 7     3     2     | 9     5     1     | 68    4     68    |
 | 5     6     9     | 47    78    48    | 2     3     1     |
 |-------------------+-------------------+-------------------|
 | 69*   8     7     | 5     1     49    | 3     26*  24(6)9 |
 | 19*   5     14    | 2     6     3     | 48    7     489   |
 | 3     2     46    | 47    78    489   | 5     1     469   |
 |-------------------+-------------------+-------------------|
 | 16*   9     5     | 16*   4     2     | 7     8     3     |
 | 2     4     16    | 8     3     7     | 16    9     5     |
 | 8     7     3     | 16*   9     5     | 14(6) 26*  24(6)  |
 *-----------------------------------------------------------*


As a nice loop (hope I got the notation right):

-1-[r5c1]-9-[r4c1]-6-[r4c8]-2-[r9c8]-6-[r9c4]-1-[r7c4]-6-[r7c1]-1-[r5c1]-9-, => r4c9,r9c79<>6

After removing the three 6s it still took a couple of xy wings to finish.

As for xy chain tips.. you're doing fine. When you find a chain, be sure not to miss any eliminations. Keep an eye out for continuous loops, like the one above.

I read, or attempted to read, the definition of nice statements and gave up on it. I can follow your loop 'nicely' but don't understand the cancellations. Anyway, what I wanted to know if there was if there was a better aiming point for my XYchains then shooting in the dark the way I'm doing now. Thanks all.
stumble
 
Posts: 52
Joined: 29 October 2007

Postby daj95376 » Sun Jan 06, 2008 9:50 pm

stumble wrote:Anyway, what I wanted to know if there was if there was a better aiming point for my XYchains then shooting in the dark the way I'm doing now. Thanks all.

Okay, here's a few suggestions for finding XY-Chains.

1) Choose a starting cell, e.g. [r2c2], and an ending cell, e.g. [r8c8], that have 2-3 candidates between them.

2) If all of the cells they mutually see fail to contain the common candidate, e.g. 6, then return to (1).

3) When possible, see if eliminating the common candidate is (obviously) beneficial before searching for a chain.

4) Now, you need to find a chain of (currently existing) bi-value cells that force the common candidate to be true in either the starting or ending cell. This chain will always start with the non-common candidate being assumed true; e.g. [r2c2]=4 or [r8c8]=8. I don't have any suggestions on how to shortcut finding a chain.

5) Once you find a chain, remember to eliminate the common candidate from all of the cells the starting cell and ending cell mutually see.

6) Some starting cells work with multiple ending cells. Don't assume that you're done with a starting cell once you find an XY-Chain for it.

7) One XY-Chain may eliminate a candidate in a cell with three candidates. This may allow a subsequent XY-Chain that didn't exist prior to the elimination. Go back and check!

8) Finally, there's no reason that a starting cell can't have a separate XY-Chain for each candidate. Don't stop after finding an XY-Chain based on one candidate in the starting cell.

Code: Select all
 +-----------------------------------+
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  . 46  .  |  .  .  .  |  . *** .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |-----------+-----------+-----------|
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |-----------+-----------+-----------|
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  . *** .  |  .  .  .  |  . 68  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 +-----------------------------------+

[Edited]
Last edited by daj95376 on Mon Jan 07, 2008 4:39 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby stumble » Mon Jan 07, 2008 4:24 pm

Thanks daj, your suggestions are immortalized in my Sudoku notebook and I'll reread them next time I try to create an XYchain.
stumble
 
Posts: 52
Joined: 29 October 2007

Postby daj95376 » Mon Jan 07, 2008 8:34 pm

Here's a nice puzzle from Mike Barker's zoo collection. It's also a nice example of why I included step (2).

Code: Select all
..65.....18..4.9.5......3....846.5....2.....4.59.8..6......614..3....6.......7.83

 *--------------------------------------------------*
 | 279  279  6    | 5    3    19   | 4    12   8    |
 | 1    8    3    | 6    4    2    | 9    7    5    |
 | 259  249  45   | 179  179  8    | 3    12   6    |
 |----------------+----------------+----------------|
 | 37   17   8    | 4    6    19   | 5    39   2    |
 | 36   16   2    | 179  179  5    | 8    39   4    |
 | 4    5    9    | 2    8    3    | 7    6    1    |
 |----------------+----------------+----------------|
 | 8    29   57   | 3    25   6    | 1    4    79   |
 | 29   3    17   | 8    12   4    | 6    5    79   |
 | 56   46   145  | 19   159  7    | 2    8    3    |
 *--------------------------------------------------*

Note: I edited my step (1) above, but the change doesn't apply to this puzzle.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Setting up an XYchain

Postby keith » Sat Apr 05, 2008 11:05 pm

stumble wrote:I wonder if anyone can give me any tips on logical way to start setting up an XYchain?


You might check out the discussion at Daily Sudoku:

http://www.dailysudoku.com/sudoku/forums/index.php

They are using methods like W-wings, M-wings, and half-M-wings to do exactly what you ask: Find a pattern to help look for an XY-chain.

Something new (to me) came up today: The LA Times / Detroit Free Press (Freep) Friday puzzle:
Code: Select all
Puzzle: FP040408
+-------+-------+-------+
| 2 . . | . 4 . | . . 5 |
| . . . | 5 . . | . 7 . |
| . 5 . | . . 1 | . 3 . |
+-------+-------+-------+
| . . 7 | 8 1 . | 6 . . |
| . . 9 | . 5 . | 2 . . |
| . . 1 | . 3 2 | 7 . . |
+-------+-------+-------+
| . 9 . | 4 . . | . 1 . |
| . 6 . | . . 5 | . . . |
| 8 . . | . 6 . | . . 7 |
+-------+-------+-------+

Basic moves get you to here:
Code: Select all
+----------------+----------------+----------------+
| 2    7    8    | 3    4    9    | 1    6    5    |
| 1349 134  346  | 5    28   68   | 48   7    29   |
| 49   5    46   | 267  278  1    | 48   3    29   |
+----------------+----------------+----------------+
| 5    2    7    | 8    1    4    | 6    9    3    |
| 34   348  9    | 67   5    67   | 2    48   1    |
| 6    48   1    | 9    3    2    | 7    5    48   |
+----------------+----------------+----------------+
| 37   9    23   | 4    278  78   | 5    1    6    |
| 17   6    24   | 17   9    5    | 3    248  48   |
| 8    14   5    | 12   6    3    | 9    24   7    |
+----------------+----------------+----------------+

A skyscraper on <4> in R69 takes out <4> in R8C9, leading to:
Code: Select all
+----------------+----------------+----------------+
| 2    7    8    | 3    4    9    | 1    6    5    |
| 1349 134  346  | 5    28   68   | 48   7    29   |
| 49   5    46   | 267  278  1    | 48   3    29   |
+----------------+----------------+----------------+
| 5    2    7    | 8    1    4    | 6    9    3    |
| 34   34   9    | 67   5    67   | 2    8    1    |
| 6    8    1    | 9    3    2    | 7    5    4    |
+----------------+----------------+----------------+
| 37   9    23   | 4    278  78   | 5    1    6    |
| 17   6    24   | 17   9    5    | 3    24   8    |
| 8    14   5    | 12   6    3    | 9    24   7    |
+----------------+----------------+----------------+


Steve R. pointed out that in C1B7, the cells <37> and <17> must contain <1> or <3>. Therefore, there are pincer cells R5C1 and R9C2, one of which must be <4>. The <4> in R5C2 is toast!.

In trying to understand Steve's contribution, I observed that one of R8C1 and R9C2 must contain <47>. Leading to the pincer cells R7C1 and R5C2, one of which must be <3>. R5C1 is solved as <4>!

These turn out to be 5-link* XY-chains. As Steve observed, sort of an extended XY-wing.

http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2455

Best wishes,

Keith

* edit: I originally said "4-link". An XY-wing is four links, if you include the links to the target cell. This is one more.
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006


Return to Advanced solving techniques