## Quick and efficient xy-wing searches

Advanced methods and approaches for solving Sudoku puzzles

### Quick and efficient xy-wing searches

Quick and efficient xy-wing searches

I use a staged search for xy-wings.

First search for two cells of an xy-wing in each box. If your two cells do not share a row or column, then this tends to be your most fruitful pairing since it maximizes your opportunities for completing the xy-wing (24 cells) and it has the maximum number of cells where a reduction can take place once the xy-wing is completed(5).

In the grids below, the starred cells in the first grid indicate where you can search for a cell containing (ac) which would complete the xy-wing, and the minus signs in the next grid indicate cells where a reduction caused by the completed xy-wing can take place.
Code: Select all
`+----------+----------+----------+  +----------+----------+----------+| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |+----------+----------+----------+  +----------+----------+----------+| ab .  .  | *  *  *  | *  *  *  |  | ab -  -  | .  ac .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  bc .  | *  *  *  | *  *  *  |  | .  bc .  | -  -  -  | .  .  .  |+----------+----------+----------+  +----------+----------+----------+| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |+----------+----------+----------+  +----------+----------+----------+`

If the first two xy-wing cells in a box share a row or column, then you only have the 12 cells perpendicular to your pair to complete the xy-wing, but you still retain 5 cells where a reduction could take place
Code: Select all
`+----------+----------+----------+  +----------+----------+----------+| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |+----------+----------+----------+  +----------+----------+----------+| ab .  .  | *  *  *  | *  *  *  |  | ab .  .  | -  -  -  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || bc .  .  | *  *  *  | *  *  *  |  | bc -  -  | .  .  ac | .  .  .  |+----------+----------+----------+  +----------+----------+----------+| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |+----------+----------+----------+  +----------+----------+----------+`

The least fruitful three-box xy-wings should be scanned for last. These xy-wings start with one bivalue cell in a box. Assuming you have already scanned for the above two types, there are 12 cells where you can find the second leg of the xy-wing, and, from there, 12 more cells where you can find the completion. From the completed xy-wing of this type there is only a single cell where a deduction might be made.
Code: Select all
`+----------+----------+----------+  +----------+----------+----------+| ab .  .  | *  *  *  | *  *  *  |  | ab .  .  | .  .  -  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |+----------+----------+----------+  +----------+----------+----------+| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || bc .  .  | *  *  *  | *  *  *  |  | bc .  .  | .  .  ac | .  .  .  |+----------+----------+----------+  +----------+----------+----------+| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  || .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |+----------+----------+----------+  +----------+----------+----------+`

Note that the three-box xy-wing must have at least one cell in boxes 1, 3, 5, 7, or 9. Thus you can restrict your initial cell searches for this final case to those five boxes (or five similarly oriented ones such as 1, 2, 4, 5, 9). You can use this limiting feature to minimize the number of starting cells you have to consider.

In all cases, as you are scanning for the completion of your xy-wing, it doesn't hurt to keep an eye open for an extra bivalue cell or an ALS which can also result in a deduction.
Myth Jellies

Posts: 593
Joined: 19 September 2005

 ignore!
Last edited by daj95376 on Sat Oct 14, 2006 7:53 pm, edited 1 time in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

MJ, nice post.

Here are two benchmarks with only xy-wings and singles.
Code: Select all
` 3...9..4..5...8....973....2......8..9..625..3..6......2....798....2...1..4..8...5..4....8.3......72......3.59...1....1..842........97..2...81.56...2....46.95.....`

Of your three "types", there are two examples each of "type 1" and "type 3" ... but none of "type 2". Perhaps someone else has a benchmark for that.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Nice post, MJ.

This is exactly what I have been doing lately. But now, I wait on even if there are extra candidates in any of the three cells and bifurcate.
Case one: if the extra candidate were true
Case two: the xy wing if the extra candidate were false
Finlip

Posts: 49
Joined: 15 July 2005

ronk wrote:... but none of "type 2". Perhaps someone else has a benchmark for that.

Type 2 is very rare. In a collection of 3000 sudokus that require only XY-Wing above basics, I found 25 containing a type 2, but each of them required an XY-Wing of one of the other two types to expose the type 2 step.

Here are a few benchmark samples:

Code: Select all
`150000000000079020030006900000000000070001000005008200048900500600013802000002070804000079000000100036000240000420000050603090000095000079000620003000000420000301502000060060005400000090700001400000008306900000001200005010000009800020070000504`

The last one is a nice benchmark puzzle. It contains all 3 types.

Ruud
Ruud

Posts: 664
Joined: 28 October 2005

Ruud wrote:In a collection of 3000 sudokus that require only XY-Wing above basics, I found 25 containing a type 2 ...

Thanks for the 3 benchmarks ... but each has a single type 2 exclusion. Multiple exclusions from a single xy-wing would make a better benchmark. If you post the other 22, I'll try to find one.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

No need to search, Ron. Here is a type 2 with 2 eliminations:

Code: Select all
`000051000050008040200000008080000427907030506425000030300000005040300090000970000`

It is the only one in my list. The rarity may be the result of my list being restricted to Sudokus that only require basics + XY-Wing.
• Type 1 is the most common and often has multiple eliminations.
• Type 3 occurs 1 in 10 and can only have a single elimination.
• Type 2 occurs 1 in 80 and multiple eliminations are not common.
I Love Sudoku Statistics
Ruud

Posts: 664
Joined: 28 October 2005

Code: Select all
`Technique Hierarchy:1) N-tuples and Locked Candidates (1) & (2)2) XY-Wing Type 23) XY-Wing Type 1/34) everything else`

Code: Select all
`# 955 puzzles with only (1-3) above in solution#  42 contained Type 2 in the solution#     but only after a Type 1/3 elimination in the head cell for the Type 2 (Ruud)#  11 Type 2 solutions performed two   eliminations#   1 Type 2 solution  performed three eliminations.5.8...3.7.6.3.8...38....2.5....7.8.1...4...2.6.5....7.1....34...5.1.2.6.2...4.7.    b7  -  3     Locked Candidate (1)    b2  -  6     Locked Candidate (1)    b2  -  7     Locked Candidate (1)r7c4    <> 9   * XY-Wing  on [r5c3]r7c5    <> 9   ~ T2-Wing  on [r7c4]r7c6    <> 9   ~ T2-Wing  on [r7c4]r9c3    <> 9   ~ T2-Wing  on [r7c4]`

[Edit:] If the hierarchy includes:

Code: Select all
`1.5) X-Wing, Swordfish, and Jellyfish`

then the above puzzle can be solved as
Code: Select all
`    b7  -  3     Locked Candidate (1)    b2  -  6     Locked Candidate (1)    b2  -  7     Locked Candidate (1)r58     -  8     X-Wingr5c6    <> 8     T2-Wing  on [r6c6]r7c5    <> 8     T2-Wing  on [r6c6]r9c5    <> 8     T2-Wing  on [r6c6]`

and we no longer need an XY-Wing Type 1/3 to preceed an XY-Wing Type 2. However, in all 42 puzzles, the value eliminated from the head cell is (still) always the value subsequently eliminated by the T2-Wing.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006