Dan Rice's Sudoku Blog: X-Wings

November 2005

August 18, 2005

Sun	Mon	Tue	Wed	Thu	Fri	Sat
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

X-Wings

Last time I discussed a pattern involving an interaction between a box and a row or column that passes through that box. If the only places left in the box for a particular value all lie in the same row or column, it's possible to eliminate the value from the part of the row or column that lies outside the box. By localizing a value in one type of group, we manage to localize it in an intersecting group.

Today I'm going to write about a pattern that involves the intersections between rows and columns, specifically where we know something about four cells that share two rows and two columns (i.e., they lie at the corners of a rectangle).

Consider this grid (you may want to try to solve it before reading further):

Without using any new rules, we can get to this situation:

In column 2, the number 3 can only appear in the cell (2, 2) or (2, 5). Similarly, in column 5, 3 can only appear in (5, 2) or (5, 5). I‘ve circled the possible cells in red, and highlighted the columns in red as well.

Suppose cell (2, 2) has the value 3. Then (5, 2) can't take a 3 because it is in the same row as (2, 2); thus (5, 5) is the only place left in column 5 that can take a 3. Conversely, if (2, 5) has the 3 for column 2 then (5, 2) must have the 3 for column 5. So either (2, 2) and (5, 5) contain 3's, or else (2, 5) and (5, 2) contain 3's. In short, there must be 3's at two opposite corners of the "X" formed by (2, 2), (2, 5), (5, 2), and (5, 5). This is the "X-Wings" (or "X-Wing") pattern, named for the way the values appear at the corners of an "X" shape. By coincidence, I'm writing this entry from the Electronic Theater at Siggraph 2005 , where a replica of a Star Wars T-65 X-Wing Starfighter is sitting in the lobby a couple of hundred feet away.

Now that we know that there are 3's at two opposite corners, we have accounted for the 3's in row 2 and row 3. We can remove all the other 3's in row 2 and row 5. I've highlighted the pencil marks that we can now erase in blue.

Note that we started out knowing that a number can be located at two places within each of two columns, and we ended up determining that it can occur in only two places in each of two rows. Again, localizing within one group or set of groups (the columns) enables us to localize in a related group or group (the rows). The key is that the cells involved form the corners of a rectangle.

Another example occurs later in the solution of the same grid (I won't draw circles around the corners anymore in order to simplify the diagrams a bit):

The corners of the red rectangle show the only places for a 5 in columns 2 and 3. The blue squares show where we can remove 5's in row 2. There's yet another X-Wing hidden in the grid:

Columns 5 and 7 have only two places for the number 9, which are in rows 2 and 3 for each column. We can remove 9's from the rest of those rows.

We can also start by locating a value in two cells of a each of two rows, and use this information to eliminate values up and down the columns. I call this type "horizontal X-Wings," as opposed to the "vertical X-Wings" discussed above.

This board contains a couple of examples of horizontal X-Wings:

Take a look at this stage in the solution:

The only places for the number 8 in row 1 and row 2 are in columns 2 and 4, so we remove the other remaining 8 in column 4.

The same grid also contains this pattern:

Note that we remove 6's from all of column 3, apart from rows 2 and 4 that make up the X-Wing pattern. So the 6 at (3, 3) is removed, along with the 6 at (3, 9). Don‘t be fooled by the "box" shape — only two rows and two columns are involved in the X-Wing pattern itself.

Next time I'll show how to extend the same reasoning to a more difficult (but rarer) pattern known as the Swordfish.

August 18, 2005 in Sudoku Tips | Permalink

Comments

Hi Dan,
If I am understanding the X-Wings correctly then the only criteria for isolating a number using this method is that it must appear in each corner of a oblong.
If that is so, then in the first example you gave there is another oblong with 3 at each corner. That is the one bounded by 1,2 - 4,2 - 1,5 - 4,5.

Can you please either correct my misunderstanding of the method or tell me why the x-wings cannot work for the 3s in the oblong in column 1 and 5 but can with the one adjacent to it.
Thanks

Posted by: Larry | October 25, 2005 at 12:16 AM

Hi Larry -

It's not enough that the numbers form the corners of an oblong. In the first example, note the red vertical lines. These are there to indicate that 3 can only appear in the circled places in each of those columns. In columns 1 and 4, 3 can appear in more than 2 places. The X-Wings rule takes advantage of this knowledge of the columns in order to eliminate other values in the same rows.

Make sure you understand why the rule works before you try to apply it -- otherwise it's likely to lead you to an incorrect solution.

Posted by: sudokublog | October 25, 2005 at 09:09 AM

I have been working Sudoku puzzles for the last couple of months. I have yet to find one in a newspaper or book that I can't solve using only logic. I have found some on-line that I haven't been able to solve using logic, so I researched some of these complex pattern recognition methods. I was able to solve your X-wing example without using your X-wing process. Are there any puzzles that must use this type of reduction to solve logically, or is X-wing just a more efficient way to eliminate some numbers?

Posted by: Steve Hauenstein | January 09, 2006 at 10:58 AM