## XY-Wing: description and tips

Advanced methods and approaches for solving Sudoku puzzles

### XY-Wing: description and tips

The name XY-Wing was first proposed in this thread.

The XY-Wing is a special case of forcing chains, and can be considered the simplest application of that technique.

The XY-Wing can also be considered a generalization of a special case of naked triples.
"Uh?" I hear you say. "generalization of a special case?".

A naked triple is a group of three cells in the same unit that contain in total three candidates. Each cell can have two or three candidates, but the different candidates present in at least one of the cells must be three. When this happens, the three candidates can be removed from all other cells in the same unit. Examples of naked triples:

(123) (123) (123)
(123) (123) (12)
(123) (12) (23)
(12) (23) (13)

The last case is the one we are interested in. We can formulate the special case of a naked triple where every cell contains only two candidates.

If three cells in the same unit contain candidates xy, yz and xz respectively, then x y and z can be removed from the candidates of all other cells in the unit.

We can now generalize that definition, this way:

If three cells a, b, c, with a and b in the same unit, and a and c in the same unit, candidates xy, yz and xz 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 b and c respectively.

The reason for that is quite simple: a containes either x or y. If a contains x, then c contains z; if a contains y, then b contains z. Therefore either b or c contains z. Therefore a cell located inside the intersection of two units containing b and c cannot contain z.

An easy example would be as follows:

Code: Select all
` . . . | . . . | . . . . xy------yz. | . . . . | . | . | . | . . .---|---+---|---+------- . | . | . | . | . . . . xz------* . | . . . . . . | . . . | . . .-------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .`

Here, r5c5 cannot contain Z.

The cells need not be the vertices of a rectangle:

Code: Select all
` . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .-------+-------+------- . xy------yz. | . . . ./. . | . .\ .| . . .xz-----------* | . . .-------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .`

The cells need not be the vertices of a polygon either:

Code: Select all
` . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .-------+-------+------- . . . | *-xy------yz. . . . | |/. . | . . . . . . |xz . . | . . .-------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .`

I hope this figure is clear. r4c5 is either x or y. If it's x, r6c4 is z. If it's y, r4c8 is z. In either case, r4c4 cannot be z.

Some hints about how to locate a XY-Wing on the grid.
Let's do it with an example.

Code: Select all
`3     4     19     | 6     5     8      | 2     7     19    89    18    5      | 7     4     2      | 19    6     3     6     2     7      | 1     9     3      | 5     8     4     -------------------+--------------------+-------------------4     18    19     | 3     7     5      | 89    2     6     5     6     2      | 8     1     9      | 4     3     7     89    7     3      | 4     2     6      | 189   5     19    -------------------+--------------------+-------------------7     9     8      | 2     3     4      | 6     1     5     2     3     4      | 5     6     1      | 7     9     8     1     5     6      | 9     8     7      | 3     4     2     `

First of all, locate a cell that has only two candidates. For example r4c3=19. Look for another cell in the same unit that has two candidates, one of which is 1. While doing this, ignore cells with the same two candidates, i.e. 19, because the XY-Wing wouldn't work.

In this case we have r4c2=18. Now look for another cell in the same unit as the first one, having only two candidates: the one you didn't consider before (9), and the new one found in the second cell (8). There are two such cells: r4c7=89 and r5c1=89. The former isn't much use, because it completes a naked triple. The latter could allow to form a XY-Wing, but there is no cell where the candidate 8 would be removed. [Edit: the latter is a naked triple as well]

As an exercise, find the XY-Wing in the above board. Hint: the first cell is one of the 19 ones.

If you want to try more puzzles needing this technique, you can find some examples here.
Last edited by Nick70 on Tue Jul 26, 2005 3:09 am, edited 1 time in total.
Nick70

Posts: 156
Joined: 16 June 2005

### Re: XY-Wing: description and tips

Nick70 wrote:Examples of naked triples:

(123) (123) (123)
(123) (123) (12)
(123) (12) (23)
(12) (23) (13)

Nick,

Thank you for the explantion? Are there any known techniques involving the first 3 combinations?

George
George

Posts: 20
Joined: 20 July 2005

### Re: XY-Wing: description and tips

In this case we have r4c2=18. Now look for another cell in the same unit as the first one, having only two candidates: the one you didn't consider before (9), and the new one found in the second cell (8). There are two such cells: r4c7=89 and r6c1=89. The former isn't much use, because it completes a naked triple. The latter could allow to form a XY-Wing, but there is no cell where the candidate 8 would be removed.

Isn't r4c3-r4c2-r6c1 also a naked triple? They're all in the same unit.

/ Ulf
ulfn

Posts: 1
Joined: 25 July 2005

### Re: XY-Wing: description and tips

ulfn wrote:Isn't r4c3-r4c2-r6c1 also a naked triple? They're all in the same unit.

Yes, of course you are right, thanks for noticing this.
Nick70

Posts: 156
Joined: 16 June 2005

I started playing with implementing an XY-wing deducer in the Susser, and came up with what I *think* is a slick restatement of the rule that makes them very easy to find. However, since it contradicts this statement (above)...

As an exercise, find the XY-Wing in the above board. Hint: the first cell is one of the 19 ones

...I am wondering if I'm wrong, or the above example is wrong! I note that it has a minor typo; R4C7 can be 189, not 89.

Here's my restatement:

* The "buddies" of a cell are the 20 cells in its row, column or block.

* For any cell with value XY, if you can find two buddies with values XZ and YZ, then no cell in the intersection of the buddies of the XZ and YZ cells can be Z.

I reproduce the puzzle from the previous example:

Code: Select all
`+-------+-------+-------+| 3 4 . | 6 5 8 | 2 7 . | | . . 5 | 7 4 2 | . 6 3 | | 6 2 7 | 1 9 3 | 5 8 4 | +-------+-------+-------+| 4 . . | 3 7 5 | . 2 6 | | 5 6 2 | 8 1 9 | 4 3 7 | | . 7 3 | 4 2 6 | . 5 . | +-------+-------+-------+| 7 9 8 | 2 3 4 | 6 1 5 | | 2 3 4 | 5 6 1 | 7 9 8 | | 1 5 6 | 9 8 7 | 3 4 2 | +-------+-------+-------+also in expanded format, so the possibilities are more clear:+-----------------------+-----------------------+-----------------------+|       .       .       |       .       .       |       .       .       || ##### . #   # . 1 9   | ##### . ##### . ##### | ##### . ##### . 1 9   ||     # . #   # .       | #     . #     . #   # |     # .     # .       ||  #### . ##### .       | ##### . ##### . ##### | ##### .     # .       ||     # .     # .       | #   # .     # . #   # | #     .     # .       || ##### .     # .       | ##### . ##### . ##### | ##### .     # .       ||.......................|.......................|.......................||       .       .       |       .       .       |       .       .       || 8 9   . 1 8   . ##### | ##### . #   # . ##### | 1 9   . ##### . ##### ||       .       . #     |     # . #   # .     # |       . #     .     # ||       .       . ##### |     # . ##### . ##### |       . ##### .  #### ||       .       .     # |     # .     # . #     |       . #   # .     # ||       .       . ##### |     # .     # . ##### |       . ##### . ##### ||.......................|.......................|.......................||       .       .       |       .       .       |       .       .       || ##### . ##### . ##### |   #   . ##### . ##### | ##### . ##### . #   # || #     .     # .     # |   #   . #   # .     # | #     . #   # . #   # || ##### . ##### .     # |   #   . ##### .  #### | ##### . ##### . ##### || #   # . #     .     # |   #   .     # .     # |     # . #   # .     # || ##### . ##### .     # |   #   .     # . ##### | ##### . ##### .     # |+-----------------------+-----------------------+-----------------------+|       .       .       |       .       .       |       .       .       || #   # . 1 8   . 1 9   | ##### . ##### . ##### | 1 8 9 . ##### . ##### || #   # .       .       |     # .     # . #     |       .     # . #     || ##### .       .       |  #### .     # . ##### |       . ##### . ##### ||     # .       .       |     # .     # .     # |       . #     . #   # ||     # .       .       | ##### .     # . ##### |       . ##### . ##### ||.......................|.......................|.......................||       .       .       |       .       .       |       .       .       || ##### . ##### . ##### | ##### .   #   . ##### | #   # . ##### . ##### || #     . #     .     # | #   # .   #   . #   # | #   # .     # .     # || ##### . ##### . ##### | ##### .   #   . ##### | ##### .  #### .     # ||     # . #   # . #     | #   # .   #   .     # |     # .     # .     # || ##### . ##### . ##### | ##### .   #   .     # |     # . ##### .     # ||.......................|.......................|.......................||       .       .       |       .       .       |       .       .       || 8 9   . ##### . ##### | #   # . ##### . ##### | 1 8 9 . ##### . 1 9   ||       .     # .     # | #   # .     # . #     |       . #     .       ||       .     # .  #### | ##### . ##### . ##### |       . ##### .       ||       .     # .     # |     # . #     . #   # |       .     # .       ||       .     # . ##### |     # . ##### . ##### |       . ##### .       |+-----------------------+-----------------------+-----------------------+|       .       .       |       .       .       |       .       .       || ##### . ##### . ##### | ##### . ##### . #   # | ##### .   #   . ##### ||     # . #   # . #   # |     # .     # . #   # | #     .   #   . #     ||     # . ##### . ##### | ##### .  #### . ##### | ##### .   #   . ##### ||     # .     # . #   # | #     .     # .     # | #   # .   #   .     # ||     # .     # . ##### | ##### . ##### .     # | ##### .   #   . ##### ||.......................|.......................|.......................||       .       .       |       .       .       |       .       .       || ##### . ##### . #   # | ##### . ##### .   #   | ##### . ##### . ##### ||     # .     # . #   # | #     . #     .   #   |     # . #   # . #   # || ##### .  #### . ##### | ##### . ##### .   #   |     # . ##### . ##### || #     .     # .     # |     # . #   # .   #   |     # .     # . #   # || ##### . ##### .     # | ##### . ##### .   #   |     # .     # . ##### ||.......................|.......................|.......................||       .       .       |       .       .       |       .       .       ||   #   . ##### . ##### | ##### . ##### . ##### | ##### . #   # . ##### ||   #   . #     . #     | #   # . #   # .     # |     # . #   # .     # ||   #   . ##### . ##### | ##### . ##### .     # |  #### . ##### . ##### ||   #   .     # . #   # |     # . #   # .     # |     # .     # . #     ||   #   . ##### . ##### |     # . ##### .     # | ##### .     # . ##### |+-----------------------+-----------------------+-----------------------+Running my algorithm, I get the following debugging trace:R1C3 = <19>; x = <1>, y = <9>  XZ R2C2 = <18>  YZ R2C1 = <89>  XZ R2C2 = <18> so YZ must be <89>    Found YZ @ R2C1; Z = <8>    Intersection R2C3 = <5>    Intersection R2C4 = <7>    Intersection R2C5 = <4>    Intersection R2C6 = <2>    Intersection R2C7 = <19>    Intersection R2C8 = <6>    Intersection R2C9 = <3>    Intersection R1C1 = <3>    Intersection R3C1 = <6>    Intersection R1C2 = <4>    Intersection R1C3 = <19>    Intersection R3C2 = <2>    Intersection R3C3 = <7>R1C9 = <19>; x = <1>, y = <9>R2C1 = <89>; x = <8>, y = <9>  XZ R2C2 = <18>  YZ R2C7 = <19>  YZ R1C3 = <19>  XZ R2C2 = <18> so YZ must be <19>    Found YZ @ R2C7; Z = <1>    Intersection R2C1 = <89>    Intersection R2C3 = <5>    Intersection R2C4 = <7>    Intersection R2C5 = <4>    Intersection R2C6 = <2>    Intersection R2C8 = <6>    Intersection R2C9 = <3>    Found YZ @ R1C3; Z = <1>    Intersection R1C1 = <3>    Intersection R1C2 = <4>    Intersection R2C3 = <5>    Intersection R3C3 = <7>    Intersection R2C1 = <89>    Intersection R3C1 = <6>    Intersection R3C2 = <2>R2C2 = <18>; x = <1>, y = <8>  XZ R2C7 = <19>  XZ R1C3 = <19>  YZ R2C1 = <89>  XZ R2C7 = <19> so YZ must be <89>    Found YZ @ R2C1; Z = <9>    Intersection R2C2 = <18>    Intersection R2C3 = <5>    Intersection R2C4 = <7>    Intersection R2C5 = <4>    Intersection R2C6 = <2>    Intersection R2C8 = <6>    Intersection R2C9 = <3>  XZ R1C3 = <19> so YZ must be <89>    Found YZ @ R2C1; Z = <9>    Intersection R2C2 = <18>    Intersection R2C3 = <5>    Intersection R1C1 = <3>    Intersection R3C1 = <6>    Intersection R1C2 = <4>    Intersection R3C2 = <2>    Intersection R3C3 = <7>R2C7 = <19>; x = <1>, y = <9>  XZ R2C2 = <18>  YZ R2C1 = <89>  XZ R2C2 = <18> so YZ must be <89>    Found YZ @ R2C1; Z = <8>    Intersection R2C3 = <5>    Intersection R2C4 = <7>    Intersection R2C5 = <4>    Intersection R2C6 = <2>    Intersection R2C7 = <19>    Intersection R2C8 = <6>    Intersection R2C9 = <3>    Intersection R1C1 = <3>    Intersection R3C1 = <6>    Intersection R1C2 = <4>    Intersection R1C3 = <19>    Intersection R3C2 = <2>    Intersection R3C3 = <7>R4C2 = <18>; x = <1>, y = <8>  XZ R4C3 = <19>  YZ R6C1 = <89>  XZ R4C3 = <19> so YZ must be <89>    Found YZ @ R6C1; Z = <9>    Intersection R6C2 = <7>    Intersection R6C3 = <3>    Intersection R4C1 = <4>    Intersection R5C1 = <5>    Intersection R4C2 = <18>    Intersection R5C2 = <6>    Intersection R5C3 = <2>R4C3 = <19>; x = <1>, y = <9>  XZ R4C2 = <18>  YZ R6C1 = <89>  XZ R4C2 = <18> so YZ must be <89>    Found YZ @ R6C1; Z = <8>    Intersection R6C2 = <7>    Intersection R6C3 = <3>    Intersection R4C1 = <4>    Intersection R5C1 = <5>    Intersection R4C3 = <19>    Intersection R5C2 = <6>    Intersection R5C3 = <2>R6C1 = <89>; x = <8>, y = <9>  XZ R4C2 = <18>  YZ R6C9 = <19>  YZ R4C3 = <19>  XZ R4C2 = <18> so YZ must be <19>    Found YZ @ R6C9; Z = <1>    Intersection R6C1 = <89>    Intersection R6C2 = <7>    Intersection R6C3 = <3>    Intersection R4C9 = <6>    Intersection R4C7 = <189> REDUCTION!    Intersection R4C8 = <2>    Found YZ @ R4C3; Z = <1>    Intersection R4C1 = <4>    Intersection R4C4 = <3>    Intersection R4C5 = <7>    Intersection R4C6 = <5>    Intersection R4C7 = <189> REDUCTION!    Intersection R4C8 = <2>    Intersection R4C9 = <6>    Intersection R5C3 = <2>    Intersection R6C3 = <3>    Intersection R5C1 = <5>    Intersection R5C2 = <6>    Intersection R6C1 = <89>    Intersection R6C2 = <7>R6C9 = <19>; x = <1>, y = <9>  YZ R6C1 = <89>`

This indicates that there are two XY-Wings, both starting at R6C1, and both removing 1 from R4C7.

Note that this algorithm also finds all the locked set reductions.

So am I on the right track, have I missed something, or found a superset?

Posts: 81
Joined: 10 June 2005

This intriguing thread discusses generalizing naked triples.
I wonder if naked quads can be generalized in a similar way?

This example looks promising:

Code: Select all
` . . . | . . . | . . . . wx--|---xy.-|-. yz. . | . | . . . | . | .---|---+-------+------- . | . | . . . | . | . . wz----------|---* . . . . | . . . | . . .-------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .`

If r2c2=x, then r2c5=y and r2c8=z.
If r2c2=w, then r5c2=z.

So we can eliminate z from the candidates of r5c8.

I believe this is an example of an xy- chain, so it's not new.

But, maybe the idea of generalizing a naked quad can
be pushed farther than I have done here.
Nick67

Posts: 113
Joined: 24 August 2007

Nick67 wrote:But, maybe the idea of generalizing a naked quad can be pushed farther than I have done here.

Refer this thread for an wxyz-wing which covers a few cases of the generalised naked quad.

Naked quad can be generalised in the same way as naked triple, but the application will be very limited for sure.
Jeff

Posts: 708
Joined: 01 August 2005

and for the excellent discussion there.
Nick67

Posts: 113
Joined: 24 August 2007

### XYZ-wing

Just thought you'd like to know I've discovered an extension of the XY-wing logic that will work in certain rare cases. The cell that normally has XY has XYZ, and must share a box but not a column or row with XZ. For any candidate of the XYZ cell, it will eliminate Z in any other cells that share a house with XZ, XYZ, and YZ.
Code: Select all
` *  XYZ  *   | .   YZ  . .   .   .   | .   .   .XZ   .   .   | .   .   .`

The cells marked with asterisks are where Z can be eliminated. I call this technique XYZ-wing. There may be more ongoing discussion of it here.

Well crap. I should read this forum more often. I had no idea a technique with the same name and pretty much the same logic had already been discovered. What's more, it looks a little more solid than mine. Doh!
Lummox JR

Posts: 125
Joined: 22 September 2005

So am I on the right track, have I missed something, or found a superset?

The 1 in R4C7 will disappear anyway as the only 1's in Box 4 are in R4.

No need for any flashy stuff.

And then two simple chains arising from R6C1 force R1C9 to be a 9.

stuartn
stuartn

Posts: 211
Joined: 18 June 2005