| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Thu Apr 14, 2005 11:09 pm Post subject: X-Wings |
|
|
The following note on the X-Wings pattern has been copied across from the old Google Sudoku Programmers group.
Quote: | Consider the following puzzle, which is a partial-solution of the 'Very
Hard' puzzle from The Times:
Code: | . 4 3 * 9 8 . * 2 5 .
6 . . * 4 2 5 * . . .
2 . . * . . 1 * . 9 4
**********************
9 . . * . . 4 * . 7 .
3 . . * 6 . 8 * . . .
4 1 . * 2 . 9 * . . 3
**********************
8 2 . * 5 . . * . . .
. . . * . 4 . * . . 5
5 3 4 * 8 9 . * 7 1 . |
After we've made a few straightforward eliminations :
The value 3 in Box [1,3] must lie in Row 2.
The value 3 in Box [3,2] must lie in Column 6.
The value 7 in Column 5 must lie in Box [2,2].
we achieve a position where Nishio will eliminate several candidates -
however, it's possible to apply a simpler and much faster rule -
X-Wings. Note that there are two possible positions for the value 6 in
each of Row 1 and Row 9 and that, critically, the candidate positions
lie on the same columns. Consider the rectangle formed from the cells
(1,6), (1,9), (9,6) and (9,9). Clearly, 6s must occupy two of those
four cells - the pair (1,6) and (9,9) or the pair (1,9) and (9,6) - but
we don't know which at this stage. However, regardless of which pair is
occupied, we are able to eliminate the value 6 as a possibility from
each cell in Columns 6 and 9 apart from the vertices of our rectangle.
In particular, we eliminate 6 as a possibility for the cell (7,9),
which leaves 9 as the only possibility. The remainder of the problem is
now solved easily. |
|
|