I'm using the term "constraint" here to mean what it does in dancing links: That is, the digit within a cell, or the position of a digit in a box, column, or row.
The technique goes like this: If you have a set, A, of N constraints which do not have the same placements, and they share the same N other constraints (set B), you can eliminate all choices in B which do not occur in A.
In clearer language: If for a digit you have N rows and/or boxes, whose values all occur in the same N columns, and those values do not occur twice in the pattern, you can eliminate all other values in the common columns. (The rule that a value may not occur twice is like this: If your pattern has row 2, row 4, box 5, and box 7 all intersecting columns 1, 2, 4, and 6, this technique does not work if one of the candidates in the pattern is at r4c4; it's in both row 4 and box 5.) Allow me to illustrate.
- Code: Select all
. . *|. * .|* . *
* . .|* . .|* * *
a . .|. . .|b . c
-----------------
* . *|. * .|. * .
d . .|. . .|e . f
* * *|. * *|* * *
-----------------
. . *|* * .|g . h
* * .|. . *|i . j
. * .|. . *|k . .
Let's say these are all the possibilities for digit 6. Here the pattern has row 3, row 5, and box 9. These cover columns 1, 7, and 9. No matter where a 6 appears in box 9, it will fill either column 7 or column 9. That leaves an X-wing with rows 3 and 5 in either columns 1 and 7, or 1 and 9. The end result is clear: Columns 1, 7, and 9 can be cleared of all other unlabeled values.
- Code: Select all
. . *|. * .|- . -
- . .|* . .|- * -
a . .|. . .|b . c
-----------------
- . *|. * .|. * .
d . .|. . .|e . f
- * *|. * *|- * -
-----------------
. . *|* * .|g . h
- * .|. . *|i . j
. * .|. . *|k . .
The important factor in recognizing the proof of this pattern is this: If you pin down a value in any of the boxes in the pattern, one column is filled; eventually this reduces you to a simple X-fish. Any value you pin down in one of the rows from there also fills in one column. Naturally you can do this with columns and boxes intersecting common rows, as well.
Now here's the other cool technique I mentioned: multi-box-multi-line interactions. This only occurs in sudoku, in the absence of lesser techniques, where you can have 4+ boxes lined up. That means it can happen in an 8x8 or anything larger than a 9x9. Consider the pointing pair/triple: If all possibilities for a digit in a given box are all in the same line, the rest of that line can be eliminated. You can use the logic of subsets to say: If all possibilities for a digit in 2 boxes are all in the same 2 lines, the rest of the choices in those 2 lines can be eliminated. So, you can have multiple pointing sets, or multiple box-line intersections. These too are simple constraint subsets: A standard box-line interaction is merely a constraint subset size 1.
