Dan Rice's Sudoku Blog: X-Wings

July 2008

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	31

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