The New Sudoku Players' Forum

by **Myth Jellies** » Sat Oct 14, 2006 6:31 pm

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.

by **daj95376** » Sat Oct 14, 2006 7:17 pm

[Edit] ignore!

by **ronk** » Sat Oct 14, 2006 8:40 pm

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.

by **Finlip** » Sun Oct 15, 2006 12:42 pm

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

by **Ruud** » Sun Oct 15, 2006 3:17 pm

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: 150000000000079020030006900000000000070001000005008200048900500600013802000002070 804000079000000100036000240000420000050603090000095000079000620003000000420000301 502000060060005400000090700001400000008306900000001200005010000009800020070000504

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

Ruud

by **ronk** » Sun Oct 15, 2006 5:07 pm

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.

by **Ruud** » Sun Oct 15, 2006 10:00 pm

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

by **daj95376** » Mon Oct 16, 2006 12:21 am

Code: Select all: Technique Hierarchy: 1) N-tuples and Locked Candidates (1) & (2) 2) XY-Wing Type 2 3) XY-Wing Type 1/3 4) 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-Wing r5c6 <> 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.