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.

Comments

[Britney]

Excellent site - do keep up the good work.c

[sveta]

i love this site..

[Hillary]

I have your site for its useful and funny content and simple design.

[Bill]

I have been looking for sites like this for a long time. Thank you!e

[Helga]

Thank for making this valuable information available to the public.

[sveta]

Very interesting website. Keep up the outstanding work and thank you...

[sveta]

Cool!.. Nice work...

[sveta]

daite na pivo

[Britney]

Very interesting website. Keep up the outstanding work and thank you...t

[Bush]

Greetings!..o

[Britney]

s prazdnikov vasn

[Bill]

Just wanted to say hellol

[apennaMog]

http://www.hyip-catalog.com

I invested money in some programs which are placed on this site.
On a site written that it is the program which helps make money at home.



It really works?

This site:
http://www.hyip-catalog.com

[Helga]

Very good site! I like it! Thanks!5

[Bush]

Great site. I will bookmark for my sons to view as well!!!o

[Bill]

This is very interesting site...r

[Robert]

Managed Hosting, Colocation and Data Center Services by victoryushchenkonashpresudent ...

[Helga]

Very good web site, great work and thank you for your service.

[Hillary]

Thank for making this valuable information available to the public.

[vlad]

I'd like to invite you to visit our Sudoku site and play thousands of games for free at: http://www.mysudo.com

[Bill]

Check out my new site:)

[Britney]

Great Site - really useful information!

[Hillary]

This website is Great! I will recommend you to all my friends. I found so much useful things here. Thank you.

[steveEffono]

Very useful and informative blog. Recommended for all to see.
http://medsdrugs.blogspot.com/

[Helga]

I like it and the background and colors make it easy to read