xyz-wing: description and example

Advanced methods and approaches for solving Sudoku puzzles

xyz-wing: description and example

Postby Jeff » Wed Aug 03, 2005 3:55 pm

I first heard of this technique from Clive. I am going to share it here using similar illustration format as Nick's xy-wing.

For easy reference, the name xyz-wing is proposed to describe this technique without knowing whether the technique has already got a proper name.

Similar to the xy-wing, xyz-wing is a special case of forcing chains, and can be considered as another simplest application of such technique which involves 4 cells.

Similar to the xy-wing, the xyz-wing make use of the special property of a naked triple.

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. When this happens, the three candidates can be removed from all other cells in the same unit. Examples of naked triples are:

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

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

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

Lets generalise the definition of the xyz-wing considering the first case 'xy, xyz & xz' (the other 2 cases are simliar):

If three cells a, b, c, with a and b in the same row or column, and b and c in the same box, with candidates xy, xyz and xz respectively, then x can be removed from the candidates of all cells (different from a,b,c) contained in the intersection of the two units that contain a, b and c as defined.

The reason for that is quite simple: a contains either x or y. If a contains x, then b contains yz and c contains xz; if a contains y, then b contains xz which forms a naked pair with the xz in cell c. Therefore either a, b or c contains x. Therefore a cell located inside the intersection of two units containing a, b and c cannot contain x.

An easy example would be:

Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . xy----------------|-xyz .  *
 .  .  .  | .  .  .  | xz  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 

Since one of r2c2, r2c7 & r3c7 must contain x, r2c9 cannot contain x.

Cells b & c need not be on the same column

Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . xy----------------|-xyz .  *
 .  .  .  | .  .  .  |  . \xz .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 

r2c2 is either x or y. If it's x, r2c9 cannot be x. If it's y, r2c7 is xz which forms a naked pair with r3c8, therefore r2c9 cannot be x. In either case, r2c9 cannot be x.

Let's try it with the following puzzle:

Code: Select all
 
 6 . 3 | 1 . 8 | 9 4 2   
 . 8 . | . 3 . | 6 1 7     
 1 . 4 | . . . | 5 8 3     
-------+-------+-------
 7 . 1 | 3 . 6 | 8 9 5     
 9 6 8 | . . . | 3 2 . 
 . 3 5 | 8 . 9 | 7 6 .
-------+-------+-------
 3 . 7 | . . . | 1 5 8   
 . 1 . | . 8 3 | . 7 6 
 8 . 6 | 7 . 1 | . 3 9 


Having considered a hidden pair, 2 x-wings and colours on 2s, the candidates are reduced:

Image
Amongst these cells, two xyz-wings can be identified enabling the puzzle to be completed. Can you see them?

Hint: 2 is removed in both cases.
Last edited by Jeff on Sun Aug 07, 2005 10:37 pm, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby george-no1 » Wed Aug 03, 2005 5:39 pm

Jeff,

I was working on exactly the same theory recently and I probably would have been able to post it next week, but you got there first!

Arrrgggggghhh!

George
george-no1
 
Posts: 150
Joined: 20 May 2005

Re: xyz-wing: description and example

Postby angusj » Wed Aug 03, 2005 11:52 pm

Jeff wrote:For easy reference, the name xyz-wing is proposed to describe this technique without knowing whether the technique has already got a proper name.

No, I don't think this has been 'named' as such. However, as you've said above, the xy-wing and xyz-wing are really generalizations / variations of the 'naked triple' and I'm now wondering if the 'naked triple' definition should simply be broadened to include these patterns?
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Jeff » Thu Aug 04, 2005 12:55 am

george-no1 wrote:I was working on exactly the same theory recently and I probably would have been able to post it next week, but you got there first!

George

(123) (123) (123)
(123) (123) (12)

You can give some thoughts to the 2 remaining cases and complete the definition of naked triple.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby angusj » Thu Aug 04, 2005 3:13 am

Jeff, I forgot to say - well done!
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Jeff » Thu Aug 04, 2005 4:57 am

Well Done, Clive. I know you are listening.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: xyz-wing: description and example

Postby angusj » Fri Aug 05, 2005 6:13 am

angusj wrote:I'm now wondering if the 'naked triple' definition should simply be broadened to include these patterns?

I've had a bit more of a think about this and have discounted the idea of generalising the 'naked triple' to include xy-wing and xyz-wing.
For the 'naked triple' generalization to be valid, any one of x,y or z should be able to be excluded which is patently not possible.

ie: this doesn't work since '*' can still be any one of x,y or z ...
Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . xyz---------------|-xyz .  *
 .  .  .  | .  .  .  | xyz .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
angusj
 
Posts: 306
Joined: 12 June 2005

Postby tso » Thu Aug 11, 2005 7:30 pm

Jeff wrote:
Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . xy----------------|-xyz .  *
 .  .  .  | .  .  .  |  . \xz .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 

r2c2 is either x or y. If it's x, r2c9 cannot be x. If it's y, r2c7 is xz which forms a naked pair with r3c8,

therefore r2c9 cannot be x. In either case, r2c9 cannot be x.


In each case below, both r2c2=1 and r2c2=2 lead to r2c89<>1.

Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . 12  .  | .  . 23  |1234 *  *
 .  .  .  | .  .  .  |  . 14  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


 .  .  .  | .  .  .  |  . 134 .
 . 12  .  | .  .  .  |1234 *  *
 .  .  .  | .  .  .  |  .  . 134
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


 .  .  .  | .  .  .  |  .  .  .
23 12 34  |45 56 67  |  .  *  *
 .  .  .  | .  .  .  |  . 18  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  9  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


 .  .  .  | .  .  .  | 189 .  .
23 21 24  |25 26 27  |  .  *  *
 .  .  .  | .  .  .  |  . 189 .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .

tso
 
Posts: 798
Joined: 22 June 2005

Postby MadOverlord » Tue Sep 20, 2005 1:49 pm

I've been thinking about XY-wings and the derivatives like XYZ-wings and I think I've come up with a simpler description:

Definition: the "buddies" of a cell are all the cells in its row, column and block (every cell has 20 buddies).

XY-Wing: Given a cell XY that has two buddies XZ and YZ, then Z cannot be a possibility for any cell that is a buddy to both XZ and YZ.

XYZ-Wing: Given a cell XYZ that has two buddies XZ and YZ, then Z cannot be a possibility for any cell that is a buddy to all three of XYZ, XZ and YZ.

The truth-table for the three possibilities of square XYZ become:

Code: Select all
XYZ  XZ  YZ  Intersection of buddies

X     Z  YZ  ~X  ~Z
 Y   XZ   Z    ~Y~Z
  Z  X   Y   ~X~Y~Z


Am I missing something or does this capture it?
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby Jeff » Tue Sep 20, 2005 3:18 pm

Seems to have captured it. Try it on the other 2 members of the xyz-wing family.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby MadOverlord » Tue Sep 20, 2005 5:15 pm

Jeff wrote:Seems to have captured it. Try it on the other 2 members of the xyz-wing family.


Okay...

Code: Select all
XYZ  XYZ  YZ  Intersection of buddies

X     YZ  YZ  ~X
 Y   X Z   Z    ~Y~Z
  Z  XY   Y     ~Y~Z


AFAICT, the key issue is that the second XYZ and the YZ, while buddies of the first XYZ, are not buddies of each other (if they were, then this would be a locked set). Thus both can be Y or both can be Z. For example:

Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . xyz-----------------xyz ?  ?
 .  .  .  | .  .  .  |  yz .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


The XYZ-XYZ-XYZ case fails for the same reason.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby Jeff » Tue Sep 20, 2005 6:38 pm

MadOverlord wrote:
Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . xyz-----------------xyz ?  ?
 .  .  .  | .  .  .  |  yz .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .

This is not an xyz-wing. Try the two members below:

Code: Select all
 .  .  .  | .  .  .  |  *   *  *
 . xy----------------|-xyz-xyz *
 .  .  .  | .  .  .  |  *   *  *
----------+----------+----------
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .

where z can be eliminated from the cells marked with *

Code: Select all
 .  .  .  | .  .  .  |  *  *  *
 . xy----------------|-xyz-yz *
 .  .  .  | .  .  .  |  *  *  *
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .

where z can be eliminated from the cells marked with *
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby MadOverlord » Tue Sep 20, 2005 9:07 pm

I would like to see an enumeration of the shapes people consider to be xyz-wings, or even better, an algorithmic statement of the pattern (as I tried to do in my original response).

To me, your example pattern:

Code: Select all
 .  .  .  | .  .  .  |  *   *  *
 . xy----------------|-xyz-xyz *
 .  .  .  | .  .  .  |  *   *  *
----------+----------+----------
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .


seems to me to be very different in nature from the original pattern in this thread:

Code: Select all
 .  .  .  | .  .  .  |  .  .  .
 . xy----------------|-xyz .  *
 .  .  .  | .  .  .  |  . \xz .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


Here are the exemplars of your pattern (did I miss any)?

Code: Select all
 .  .  .  | .  .  .  |  *  *  *
 . xy----------------|-xyz-yz *
 .  .  .  | .  .  .  |  *  *  *
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .

 .  .  .  | .  .  .  |  *  *  *
 . xy----------------|-xyz-xz *
 .  .  .  | .  .  .  |  *  *  *
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .

 .  .  .  | .  .  .  |  *   *  *
 . xy----------------|-xyz-xyz *
 .  .  .  | .  .  .  |  *   *  *
----------+----------+-----------
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
----------+----------+-----------
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .
 .  .  .  | .  .  .  |  .   .  .

For convenience below, I'll refer to the key squares as:

 .  .  .  | .  .  .  |  *  *  *
 .  C----------------|--A--B  *
 .  .  .  | .  .  .  |  *  *  *
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


The conditions on these patterns seem to be:

1) A, B and C must be in the same row or column.

2) A and B must be in the same block

3) C cannot be in the same block (if it is, it degenerates to a locked set

4) C must be xy; B can be xz or xyz

5) Affects all squares in the block containing A and B (actually, including the degenerate case of the locked set, it affects all squares in the union of the buddies of A and B)

Now lets consider the other pattern you came up with:

Code: Select all
The general form:

 .  .  .  | .  .  .  |  .  .  .
 .  C----------------|--A  *  *
 .  .  .  | .  .  .  |  . \B  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


 .  .  .  | .  .  .  |  .  .  .
 . xz----------------|-xyz *  *  OK (as described in the
 .  .  .  | .  .  .  |  . \yz .  other XYZ-wings thread)
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


 .  .  .  | .  .  .  |  .  .  .
 . xy----------------|-xyz *  *  This is the pattern you mention
 .  .  .  | .  .  .  |  . \xz .  at the top of this thread, and was
----------+----------+---------- the source of some confusion, because
 .  .  .  | .  .  .  |  .  .  .  your original example eliminated z
 .  .  .  | .  .  .  |  .  .  .  but this example eliminates x!
 .  .  .  | .  .  .  |  .  .  .  In any case, they're equivalent.
----------+----------+----------
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .
 .  .  .  | .  .  .  |  .  .  .


So the rules for this pattern seem to be:

1) B and C must be "buddies of A"

2) A and B must be in the same block

3) C cannot be in the same block (if it is, it degenerates to a locked set)

4) B must be xz and C yz, or vice-versa.

5) Affects all squares in the union of the buddies of A, B and C

I hope I'm explaining myself clearly, because I want to implement these properly in the Susser. Reading the other XYZ-wings thread, it seems to me that the "straight" XYZ-wing degenerates to a locked set in the row, which then generates an intersection exclusion in the box. Isn't this so?

If so, then the "bent" XYZ-wing is the only one that really needs to be dealt with. If not, then I personally think that the patterns are different enough to be given different names, maybe XYZ-Wings for the "bent" pattern and XYZ-lines for the "straight" one? Or maybe, because they affect an entire block, XYZ-Hammers?

Here's an example of the graphical display of the "bent" XYZ-Wings in my current test version of the Susser:

Image

and here's a Jellyfish:

Image

I'm trying to find ways to visualize these better for people; suggestions most cordially accepted.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby Jeff » Wed Sep 21, 2005 7:07 am

I didn't want to introduce too many names to similar techniques that deal with the 2 cases of naked triples, namely (xyz, xyz, xy) and (xyz, xz, yz); each case has 3 combinations, eg. (xyz, xyz, yz) and so forth. I refer all three patterns as members of the xyz-wing family, similar to the four cases of turbot fish. You might like to differentiate them for your own purpose.:)

This thread from Nick70 may help. Refer here.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby MadOverlord » Wed Sep 21, 2005 10:46 am

Jeff wrote:This thread from Nick70 may help. Refer here.


Yeah, I ran into it yesterday. But am I correct in assuming a straight XYZ-wing can be handled as a locked set in the row/column + a r/c-block exclusion? If so, then the "bent" case is the only one that the deducer needs to worry about.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Next

Return to Advanced solving techniques