XY-wing in Simple Sudoku

Advanced methods and approaches for solving Sudoku puzzles

XY-wing in Simple Sudoku

Postby JeffInCA » Tue Jan 03, 2006 3:19 am

I'm new to this forum, so forgive me in advance if I'm not following correct board protocol.

In any case, this post is primary intended for angusj, but anyone else can feel free to answer.

I've just started with Suduko a few weeks ago and I downloaded the Simple Suduko program a few days ago (ver 4.1w).

I've read a bit on this forum about the XY-wing pattern and so I loaded the xy-wing1.ss puzzle to try it out.

I got to a stopping point and as I suspected the hint indicated two cells where exclusions can be made via the XY-wing pattern. Unfortunately I'm not really seeing the application off the bat.

My question is rather this is a classic XY-wing application as described here in the forums, or whether it is perhaps one of the variations such as XYZ-wing, etc. that may be just considered to be in the "XY-wing" class of solutions.

The puzzle is at the following state when the XY-wing is to be applied:

Code: Select all
 *-----------*
 |..6|...|198|
 |.1.|..7|364|
 |.83|...|257|
 |---+---+---|
 |297|.4.|635|
 |354|976|821|
 |168|.3.|479|
 |---+---+---|
 |.45|...|916|
 |...|61.|.43|
 |631|...|.82|
 *-----------*


Any help on this would be appreciated.

Thanks,

Jeff
JeffInCA
 
Posts: 33
Joined: 02 January 2006

Postby JeffInCA » Tue Jan 03, 2006 3:41 am

I realized I should have probably included the following with my original post, showing all of the candidates at the critical juncture

Code: Select all
 457   27    6      | 2345  25    2345   | 1     9     8
 59    1     29     | 258   2589  7      | 3     6     4
 49    8     3      | 14    6     149    | 2     5     7
--------------------+--------------------+--------------------
 2     9     7      | 18    4     18     | 6     3     5
 3     5     4      | 9     7     6      | 8     2     1
 1     6     8      | 25    3     25     | 4     7     9
--------------------+--------------------+--------------------
 78    4     5      | 2378  28    238    | 9     1     6
 789   27    29     | 6     1     58     | 57    4     3
 6     3     1      | 457   59    459    | 57    8     2


On a separate subject, I typed this in manually. Does anyone know if there is a way to generate this candidate list directly from the Simple Soduko program?
JeffInCA
 
Posts: 33
Joined: 02 January 2006

Postby ronk » Tue Jan 03, 2006 4:04 am

JeffInCA wrote:I got to a stopping point and as I suspected the hint indicated two cells where exclusions can be made via the XY-wing pattern. Unfortunately I'm not really seeing the application off the bat.

My question is rather this is a classic XY-wing application as described here in the forums, or whether it is perhaps one of the variations ...

It is a classic XY-wing pattern.
Code: Select all
 *-----------------------------------------------------------*
 | 457   27    6     | 2345  25    2345* | 1     9     8     |
 | 59    1     29    | 258   2589  7*    | 3     6     4     |
 | 49    8     3     | 14    6     149*  | 2     5     7     |
 |-------------------+-------------------+-------------------|
 | 2     9     7     | 18    4     18    | 6     3     5     |
 | 3     5     4     | 9     7     6     | 8     2     1     |
 | 1     6     8     | 25    3     25    | 4     7     9     |
 |-------------------+-------------------+-------------------|
 | 78    4     5     | 2378  28    238   | 9     1     6     |
 | 789   27    29    | 6     1*    58    | 57    4     3     |
 | 6     3     1     | 457   59*   459   | 57    8     2     |
 *-----------------------------------------------------------*

As highlighted by Simple Sudoku, the XY = 28 in r7c5, XZ = 25 in r1c5, and YZ = 58 in r8c6.

If r7c5=2, then r1c5=5
If r7c5=8, then r8c6=5

Candidate 5 (the Z) can be eliminated from all cells that "see" both the XZ and YZ cells (marked * above). Only two exist in this puzzle.

Does anyone know if there is a way to generate this candidate list directly from the Simple Soduko program?

Just cut and paste.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: XY-wing in Simple Sudoku

Postby angusj » Tue Jan 03, 2006 4:39 am

JeffInCA wrote:Any help on this would be appreciated.

Hi Jeff.

XY-Wing:
Given 3 cells where -
* all cells have exactly 2 candidates
* they share the same 3 candidates in the form - xy, yz, xz
* one cell (the Y 'stem' with canidates xy) shares a group with the other 2 cells (Y 'branches' with candidates xz & yz)
Then any other cell which shares a group with both 'branch' cells can have excluded the 'z' candidate that is common to these 'branch' cells.

Proof: If a cell sharing a group with both branch cells is assigned the 'z' canididate, then neither branch can be assigned the 'z' candidate. Consequently, one branch would be the 'x' and the other the 'y' leaving the 'stem' without a candidate, an invalid state.

Note: If all 3 cells in a xy-wing pattern shared the same group, then they would be called a 'naked triple'.

With the puzzle in question -
Image
R7C5 is the 'stem' cell, and R1C5 & R8C6 are the 'branch' cells with candidate '5' common to both branches. Therefore, any cells which share a group with both these branches can safely have candidate 5 excluded (ie cells R1C6 & R9C5 as illustrated)
angusj
 
Posts: 306
Joined: 12 June 2005

Thanks!

Postby JeffInCA » Tue Jan 03, 2006 5:16 am

Thanks for your help!

I can't believe it was that easy. I guess I've just got to get used to recognizing the pattern. I'll try a couple more examples.

Jeff
JeffInCA
 
Posts: 33
Joined: 02 January 2006

Postby Shazbot » Tue Jan 03, 2006 9:28 am

and regarding your last question, Simple Sudoku makes it EASY to post a grid in this format. Just go to Edit, and Copy. Then go to your post and Paste. Add the opening and closing Code brackets, and you're done. The most I've had to do after that is delete some spaces/lines if I've got a lot of candidates and each line is split into two.

You'll get the original puzzle with its clues, if you've solved some of the puzzle already you'll get a second grid with the stage you're up to, and finally you'll get your list of candidates. You can choose what to leave in there when you post - the list of candidates is always helpful, but if someone might need to copy the puzzle into their own program to give you assistance then the others will be useful too.
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby JeffInCA » Tue Jan 03, 2006 9:45 am

Thanks Shazbot!

That's exactly what I was looking for.
JeffInCA
 
Posts: 33
Joined: 02 January 2006

Postby angusj » Tue Jan 03, 2006 9:51 am

JeffInCA wrote:That's exactly what I was looking for.

You evidently haven't realised that I did reply to your PM:D .
angusj
 
Posts: 306
Joined: 12 June 2005

Postby throbdude » Tue Jan 10, 2006 1:15 pm

I still don't see how this works ... maybe just a bit dense, but the part about the "stem" I really can't see or understand.

How do you know which is the x and which is the y? Which ones do they "see" as stated above? When I run into this, I just have no idea what I'm really doing.
throbdude
 
Posts: 8
Joined: 10 January 2006

Postby tarek » Tue Jan 10, 2006 1:24 pm

Code: Select all
*--------------------------------------------------------*
| 457   27    6    | 2345  25    2345 | 1     9     8    |
| 59    1     29   | 258   2589  7    | 3     6     4    |
| 49    8     3    | 14    6     149  | 2     5     7    |
|------------------+------------------+------------------|
| 2     9     7    | 18    4     18   | 6     3     5    |
| 3     5     4    | 9     7     6    | 8     2     1    |
| 1     6     8    | 25    3     25   | 4     7     9    |
|------------------+------------------+------------------|
| 78    4     5    | 2378  28    238  | 9     1     6    |
| 789   27    29   | 6     1     58   | 57    4     3    |
| 6     3     1    | 457   59    459  | 57    8     2    |
*--------------------------------------------------------*
Eliminating 5 From r1c6 (2 & 8 in r7c5 form an XY wing with 5 in r1c5 & r8c6)
Eliminating 5 From r9c5 (2 & 8 in r7c5 form an XY wing with 5 in r1c5 & r8c6)

X is 2, Y is 8 & Z is 5
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby throbdude » Tue Jan 10, 2006 1:36 pm

Well, yes ... I can view the pattern once it is pointed out to me, I think what I mostly looking for is a worded explanation.

According to the rules, the XY-Wing needs to be in the same row or Column, but in the above example, the YZ is in the same block but not the same row or column. Perhaps another/different example. What I don't see is the intersections that are formed.

The example located here tries to explain, but this example is different.
throbdude
 
Posts: 8
Joined: 10 January 2006

Postby tarek » Tue Jan 10, 2006 1:41 pm

you are correct in saying that this one shares the BOX rather that the Row or Column. The XY wing pattern does not specify the "row or column" only but also the BOX. so basically the term should say "SECTOR" to include all 3 possibilities. I'll try to find another example with a BOX & post it here.

regards,

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby ronk » Tue Jan 10, 2006 1:46 pm

throbdude wrote:... in the above example, the YZ is in the same block but not the same row or column.
...
The example located here tries to explain, but this example is different.

Scroll down the page at your link and you'll see a 2nd example, this one with a "block".

And when comparing examples, keep in mind the X and Y may be interchanged.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Tue Jan 10, 2006 1:55 pm

This is from the Sudoku forum contest (#534)
Code: Select all
 . . 6 | 8 5 3 | . . . 
 . . . | . . . | . 3 . 
 . . 8 | . . . | 1 . . 
-------+-------+------
 . 3 1 | 4 . . | . . 2 
 2 9 . | . . . | . . . 
 . . . | . 9 . | . . . 
-------+-------+------
 . 4 . | . 1 . | . . . 
 1 . 3 | . 2 . | . 9 8 
 . 6 . | . . 8 | 3 7 .

*--------------------------------------------------------*
| 79    1     6    | 8     5     3    | 2     4     79   |
| 457   257   4579 | 12    67    129  | 8     3     567  |
| 3     257   8    | 29    67    4    | 1     56    5679 |
|------------------+------------------+------------------|
| 567   3     1    | 4     8     567  | 9     56    2    |
| 2     9     57   | 1567  3     1567 | 567   8     4    |
| 4567  8     457  | 2567  9     2567 | 567   1     3    |
|------------------+------------------+------------------|
| 8     4     79   | 3     1     79   | 56    2     56   |
| 1     57    3    | 567   2     567  | 4     9     8    |
| 59    6     2    | 59    4     8    | 3     7     1    |
*--------------------------------------------------------*
Eliminating 5 From r4c1 (7 & 9 in r7c3 form an XY wing with 5 in r5c3 & r9c1)
Eliminating 5 From r6c1 (7 & 9 in r7c3 form an XY wing with 5 in r5c3 & r9c1)
*--------------------------------------------------------*
| 79    1     6    | 8     5     3    | 2     4     79   |
| 457   257   479  | 12    67    129  | 8     3     567  |
| 3     257   8    | 29    67    4    | 1     56    5679 |
|------------------+------------------+------------------|
| 67    3     1    | 4     8     567  | 9     56    2    |
| 2     9     57   | 1567  3     1567 | 567   8     4    |
| 467   8     457  | 2567  9     2567 | 567   1     3    |
|------------------+------------------+------------------|
| 8     4     79   | 3     1     79   | 56    2     56   |
| 1     57    3    | 567   2     567  | 4     9     8    |
| 59    6     2    | 59    4     8    | 3     7     1    |
*--------------------------------------------------------*
Eliminating 5 From r5c7 (6 & 7 in r4c1 form an XY wing with 5 in r4c8 & r5c3)
*--------------------------------------------------------*
| 79    1     6    | 8     5     3    | 2     4     79   |
| 457   257   479  | 12    67    129  | 8     3     567  |
| 3     257   8    | 29    67    4    | 1     56    5679 |
|------------------+------------------+------------------|
| 67    3     1    | 4     8     567  | 9     56    2    |
| 2     9     57   | 1567  3     1567 | 67    8     4    |
| 467   8     457  | 2567  9     2567 | 567   1     3    |
|------------------+------------------+------------------|
| 8     4     79   | 3     1     79   | 56    2     56   |
| 1     57    3    | 567   2     567  | 4     9     8    |
| 59    6     2    | 59    4     8    | 3     7     1    |
*--------------------------------------------------------*
Eliminating 7 From r2c2 (9 & 5 in r9c1 form an XY wing with 7 in r1c1 & r8c2)
Eliminating 7 From r3c2 (9 & 5 in r9c1 form an XY wing with 7 in r1c1 & r8c2)

Most of XY wings have one of the braches having a Box relationship with the Stem, fewer examples invlove a strictly "Line" relationship for both branches, or a "Box" relationship for both:D
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby ronk » Tue Jan 10, 2006 2:33 pm

tarek wrote:Most of XY wings have one of the braches having a Box relationship with the Stem, fewer examples invlove a strictly "Line" relationship for both branches, or a "Box" relationship for both:D

Do you have an example of a "Box" relationship for both?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques