Rare new technique: XYZ-wing

Lummox JR · Posted: Thu Sep 22, 2005 5:29 am Post subject: Rare new technique: XYZ-wing

Today I implemented XY-wing in my solver. I was pondering it and realized that there's actually a special case where XY-wing would not apply, but the same principle can make some of the same eliminations.

This case is quite rare. It will occur when you have cells with candidates XZ, XYZ, and YZ; they must have no others. XZ and XYZ must appear in the same box, and XYZ and YZ must share a column or row. When this occurs, Z can be eliminated from two cells in the XZ/XYZ box.

Ruud · Site Admin

I made a sample puzzle for the XYZ-Wing (it contains one in box 1)
with X=1, Y=2, Z=3

Lummox JR · Posted: Thu Sep 22, 2005 7:39 pm Post subject:

Most of the cases I've found where even XY-wing is available, another technique will do just as well. One puzzle I've tested a lot of my algorithms on cracks wide open if you use remote pairs, but otherwise you can do either coloring or fishy cycles and then follow up with an XY.

I suspect that finding a puzzle for this is quite rare. Most of this territory seems to be. I noticed remote pairs, XY-wing, XYZ-wing, and the uniqueness test (which are all constructed similarly) seem to have that trait in common. They don't typically appear in most puzzles, but when they do they can be a huge help.

Lummox JR · Posted: Fri Sep 23, 2005 2:21 am Post subject:

Well foo, I just found out this technique isn't new after all. Someone else already discovered it and gave it the same name. And it turns out his technique is a lot more robust: It is allowable for the XYZ and XZ cells to share a row or column. Observe:

Lummox JR · Posted: Fri Sep 23, 2005 9:29 pm Post subject:

Well, this one may not be my discovery, but at least I got in a nice solver algorithm for it. My solver was not only able to solve this technique, but identify a puzzle with one. Here's a puzzle that near the end stalls on other techniques (except obviously forcing chains).

Bob Hanson · Posted: Mon Oct 24, 2005 3:53 pm Post subject:

This is an interesting find. In the parlance of Medusa chains, you have:

a) two strong chains (XZ and YZ)
b) multiple weak corners connecting these chains (* and XYZ) via Z.
c) one weak corner that can "force" the others to be NOT Z when it is NOT Z.

As you point out, this is because when the weak corner XYZ cell is NOT Z, then it must be either X or Y, which forces one or the other chains to NOT be X or Y. Thus, one of the chains MUST be Z.

Usually, weak corners in the NOT state can't influence the state of the associated chains, but here we can. Super!

I've added this as checkWeakCorners() in my Sudoku Assistant

http://www.stolaf.edu/people/hansonr/sudoku

To see it, you have to enable "Full" Medusa -- because I've added it as a weak field check.

This does advance the solution of two of top95s. Here's an example:

http://www.stolaf.edu/people/hansonr/sudoku?,-3,-2tt-5,-8,-5,,-3t-9t-9,-6,-4,-2,-8,-5,-3,-7,-1t,-4t,-3,-9t,-6t,-5tt-1t,,-4,-2t,-6,-7,,-8tt-4,-5t,-9,-5t,,-6

or

.32 ... ..5
85. 3.. 9..
964 285 371
... 4.. .39
... 6.. .5.
... .1. ...
42. ..6 7.8
... ..4 5..
.95 ... .6.

but it doesn't provide the key to solve them.

To see the action, first try to SOLVE this puzzle only to the "strong+weak" level, then click "full" and STEP once. You will see that a 1 in row 8, column 1, can be eliminated because Chains 1 and 12 interact in this way. Z=1, X=7, Y=4. The "XYZ" cell is row 9, column 1.

A screen dump is at

http://www.stolaf.edu/people/hansonr/sudoku/xyz-wing.jpg
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

noeldillabough · Posted: Mon Oct 24, 2005 9:22 pm Post subject:

I was in the process of adding uniqueness testing to my solver using this example:

Ruud · Site Admin

This is the definition MadOverlord gave on the players forum:

Bob Hanson · Posted: Mon Oct 24, 2005 10:09 pm Post subject:

Maybe, but I don't see it.

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?,-6,-9,-1,-4,-3,-8,,7t-7,-9t,,-4,-4t-7t,-9,,-9t-8,-5,-7,-3,-6,-1,-7t-2,-1,-6,-9,-4,-5,-6,-1,-5,-3,-9,-4,2,7,-8,,-7,,-5,-8,-9,-4,1,,-8t-6,-7,-1,-5tt-4,-3,-2,7,-8

solves this without need for XYZ-wing analysis. It's finding weak corners that it can eliminate because they are connected to weakly-linked strong chains. Chain 1 in this case is huge. (Check the 3D.)

Here's what I read:

9 weak links
97 weak corners
r8c2 ISN'T 3: weak 0/0 corner between linked 1/1 strong chains 1 and 3
r7c3 ISN'T 2: weak 1/0 corner between linked 0/1 strong chains 1 and 4
r8c9 ISN'T 3: weak 1/0 corner between linked 0/1 strong chains 1 and 6
r8c3 ISN'T 3: weak 0/0 corner between linked 1/1 strong chains 3 and 4

These are just corners that can't be the stated candidates no matter what parity their associated strong chains have.

A bit like a XYZ-wing, but really a different idea -- the chains themselves are directly eliminating the corner's possibility. This is basically like "puzzle x-2", third cycle, at
http://www.research.att.com/~gsf/sudoku/, although the chains here are combinations of X-like and Y-like strong edges.

The XYZ-wing thing is the situation of a weak corner NOT being the connecting candidate value forcing the chain itself to also require elimination of that value. I saw just those two examples in top95.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr