Exact Cover Examples
This page shows how the "exact cover" paradigm can be used to
describe some of the common "Rules of Sudoku".
An actual exact cover matrix is a binary matrix -- all 1s and 0s. This version uses digits 1-9
simply for easier reading.
Sorry about the need to scroll -- there are 324 columns here!
Consider a naked pair. In the exact cover matrix, this amounts to four candidate-rows
still having two candidates in a certain pair of cells. In this case, the two are in the same Sudoku grid row (row 1):
cell constraints (only one of value in each of 81 cells)------------------------- row constraints (only one of 1-9 in each of 9 rows)------------------------------ column constraints (only one of 1-9 in each of 9 columns------------------------- block constraints (only one of 1-9 in each of 9 blocks)--------------------------
0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
123456789012345678901234567890123456789012345678901234567890123456789012345678901 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c2#1 1 |1 | 1 |1 |
r1c2#2
r1c2#3 3 | 3 | 3 | 3 |
r1c2#4
r1c2#5
r1c2#6
r1c2#7
r1c2#8
r1c2#9
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c3#1 1 |1 | 1 |1 |
r1c3#2
r1c3#3 3 | 3 | 3 | 3 |
r1c3#4
r1c3#5
r1c3#6
r1c3#7
r1c3#8
r1c3#9
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
These four are incompatible because they conflict in those cell constraints.
"A cell can only hold one candidate value." Only two possibilities exist:
Either r1c2 is 1 and r1c3 is 3, or vice-versa:
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c2#1 1 |1 | 1 |1 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c3#3 3 | 3 | 3 | 3 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
or
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c2#3 3 | 3 | 3 | 3 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c3#1 1 |1 | 1 |1 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Note that either case, the "row 1", and "block 1" constraints are both covered for 1 and 3.
We can remove anything that would "overcover" these columns. This includes all of the following, for instance:
r1c9#1 1 |1 | 1 | 1 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r2c1#1 1 | 1 |1 |1 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r3c3#1 1 | 1 | 1 |1 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
hidden pairs
This hypothetical situation corresponds to a first row of cells:
{12345 234 12 125 126} (already determined cells not indicated).
cell constraints (only one of value in each of 81 cells)------------------------- row constraints (only one of 1-9 in each of 9 rows)------------------------------ column constraints (only one of 1-9 in each of 9 columns------------------------- block constraints (only one of 1-9 in each of 9 blocks)--------------------------
0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
123456789012345678901234567890123456789012345678901234567890123456789012345678901 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789
r1c1#1 1 |1 |1 |1 |
r1c1#2 2 | 2 | 2 | 2 |
r1c1#3 3 | 3 | 3 | 3 |
r1c1#4 4 | 4 | 4 | 4 |
r1c1#5 5 | 5 | 5 | 5 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c2#2 2 | 2 | 2 | 2 |
r1c2#3 3 | 3 | 3 | 3 |
r1c2#4 4 | 4 | 4 | 4 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c3#1 1 |1 | 1 |1 |
r1c3#2 2 | 2 | 2 | 2 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c4#1 1 |1 | 1 | 1 |
r1c4#2 2 | 2 | 2 | 2 |
r1c4#5 5 | 5 | 5 | 5 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c5#1 1 |1 | 1 | 1 |
r1c5#2 2 | 2 | 2 | 2 |
r1c5#6 6 | 6 | 6 | 6 |
The key is the row constraints again. Only two possibilities
involving the four lines r1c1#3, r1c1#4, r1c2#3 and r1c2#4 are compatible:
r1c1#3 3 | 3 | 3 | 3 |
r1c2#4 4 | 4 | 4 | 4 |
or
r1c1#4 4 | 4 | 4 | 4 |
r1c2#3 3 | 3 | 3 | 3 |
One of these has to be the case. Once again, the cell, row, and block constraints are all
"covered" -- they have exactly one mark in two of their columns. We can eliminate any
possibility that would increment this number of marks. Specifically, this includes:
r1c1#1 1 |1 |1 |1 |
r1c1#2 2 | 2 | 2 | 2 |
r1c1#5 5 | 5 | 5 | 5 |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
r1c2#2 2 | 2 | 2 | 2 |
any of which would increment the cell mark count above 1.
X-Wings
How about X-Wings? Say we focus on the digit 4, which all told could show up any one of 81 places:
cell constraints (only one of value in each of 81 cells)------------------------- row constraints (only one of 1-9 in each of 9 rows)------------------------------ column constraints (only one of 1-9 in each of 9 columns------------------------- block constraints (only one of 1-9 in each of 9 blocks)--------------------------
0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
123456789012345678901234567890123456789012345678901234567890123456789012345678901 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789
r1c1#4 4 | 4 | 4 | 4 |
r1c2#4 4 | 4 | 4 | 4 |
r1c3#4 4 | 4 | 4 | 4 |
r1c4#4 4 | 4 | 4 | 4 |
r1c5#4 4 | 4 | 4 | 4 |
r1c6#4 4 | 4 | 4 | 4 |
r1c7#4 4 | 4 | 4 | 4 |
r1c8#4 4 | 4 | 4 | 4 |
r1c9#4 4 | 4 | 4 | 4 |
r2c1#4 4 | 4 | 4 | 4 |
r2c2#4 4 | 4 | 4 | 4 |
r2c3#4 4 | 4 | 4 | 4 |
r2c4#4 4 | 4 | 4 | 4 |
r2c5#4 4 | 4 | 4 | 4 |
r2c6#4 4 | 4 | 4 | 4 |
r2c7#4 4 | 4 | 4 | 4 |
r2c8#4 4 | 4 | 4 | 4 |
r2c9#4 4 | 4 | 4 | 4 |
r3c1#4 4 | 4 | 4 | 4 |
r3c2#4 4 | 4 | 4 | 4 |
r3c3#4 4 | 4 | 4 | 4 |
r3c4#4 4 | 4 | 4 | 4 |
r3c5#4 4 | 4 | 4 | 4 |
r3c6#4 4 | 4 | 4 | 4 |
r3c7#4 4 | 4 | 4 | 4 |
r3c8#4 4 | 4 | 4 | 4 |
r3c9#4 4 | 4 | 4 | 4 |
r4c1#4 4 | 4 | 4 | 4 |
r4c2#4 4 | 4 | 4 | 4 |
r4c3#4 4 | 4 | 4 | 4 |
r4c4#4 4 | 4 | 4 | 4 |
r4c5#4 4 | 4 | 4 | 4 |
r4c6#4 4 | 4 | 4 | 4 |
r4c7#4 4 | 4 | 4 | 4 |
r4c8#4 4 | 4 | 4 | 4 |
r4c9#4 4 | 4 | 4 | 4 |
r5c1#4 4 | 4 | 4 | 4 |
r5c2#4 4 | 4 | 4 | 4 |
r5c3#4 4 | 4 | 4 | 4 |
r5c4#4 4 | 4 | 4 | 4 |
r5c5#4 4 | 4 | 4 | 4 |
r5c6#4 4 | 4 | 4 | 4 |
r5c7#4 4 | 4 | 4 | 4 |
r5c8#4 4 | 4 | 4 | 4 |
r5c9#4 4 | 4 | 4 | 4 |
r6c1#4 4 | 4 | 4 | 4 |
r6c2#4 4 | 4 | 4 | 4 |
r6c3#4 4 | 4 | 4 | 4 |
r6c4#4 4 | 4 | 4 | 4 |
r6c5#4 4 | 4 | 4 | 4 |
r6c6#4 4 | 4 | 4 | 4 |
r6c7#4 4 | 4 | 4 | 4 |
r6c8#4 4 | 4 | 4 | 4 |
r6c9#4 4 | 4 | 4 | 4 |
r7c1#4 4 | 4 | 4 | 4 |
r7c2#4 4 | 4 | 4 | 4 |
r7c3#4 4 | 4 | 4 | 4 |
r7c4#4 4 | 4 | 4 | 4 |
r7c5#4 4 | 4 | 4 | 4 |
r7c6#4 4 | 4 | 4 | 4 |
r7c7#4 4 | 4 | 4 | 4 |
r7c8#4 4 | 4 | 4 | 4 |
r7c9#4 4 | 4 | 4 | 4 |
r8c1#4 4 | 4 | 4 | 4 |
r8c2#4 4 | 4 | 4 | 4 |
r8c3#4 4 | 4 | 4 | 4 |
r8c4#4 4 | 4 | 4 | 4 |
r8c5#4 4 | 4 | 4 | 4 |
r8c6#4 4 | 4 | 4 | 4 |
r8c7#4 4 | 4 | 4 | 4 |
r8c8#4 4 | 4 | 4 | 4 |
r8c9#4 4 | 4 | 4 | 4 |
r9c1#4 4 | 4 | 4 | 4 |
r9c2#4 4 | 4 | 4 | 4 |
r9c3#4 4 | 4 | 4 | 4 |
r9c4#4 4 | 4 | 4 | 4 |
r9c5#4 4 | 4 | 4 | 4 |
r9c6#4 4 | 4 | 4 | 4 |
r9c7#4 4 | 4 | 4 | 4 |
r9c8#4 4 | 4 | 4 | 4 |
r9c9#4 4| 4 | 4 | 4 |
But here we are going to consider a point in the solution where not that many are possible.
Specifically, suppose there are only two locations for 4 in both rows 2 and 3 (and also in blocks and columns) :
cell constraints (only one of value in each of 81 cells)------------------------- row constraints (only one of 1-9 in each of 9 rows)------------------------------ column constraints (only one of 1-9 in each of 9 columns------------------------- block constraints (only one of 1-9 in each of 9 blocks)--------------------------
0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
123456789012345678901234567890123456789012345678901234567890123456789012345678901 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789
r2c6#4 4 | 4 | 4 | 4 |
r3c7#4 4 | 4 | 4 | 4 |
or
r2c7#4 4 | 4 | 4 | 4 |
r3c6#4 4 | 4 | 4 | 4 |
[no other 4s in rows 2 or 3, presumably]
Then we can see that columns 6 and 7 are both "covered for 4" by either possibility.
We can eliminate any possibility that would "overcover" these two columns -- any other 4 in these two columns.
This X-Wing rule would read: "If there is a set of two rows for which a certain candidate is restricted
to two specific columns, then that candidate is not possible in the same columns in any other row."
Similar rules would focus on two candidates restricted to two columns, and a generalization
would include "N" rows and "N" columns.
What about blocks? Could we say the following?
"If there is a set of two blocks for which a certain candidate is restricted
to two specific columns, then that candidate is not possible in the same columns in any other blocks."
Let's see. Imagine a situation where these are the ONLY possible occurances of 4 in blocks 1 and 4:
cell constraints (only one of value in each of 81 cells)------------------------- row constraints (only one of 1-9 in each of 9 rows)------------------------------ column constraints (only one of 1-9 in each of 9 columns------------------------- block constraints (only one of 1-9 in each of 9 blocks)--------------------------
0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
123456789012345678901234567890123456789012345678901234567890123456789012345678901 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456789123456789123456789
r1c1#4 4 | 4 | 4 | 4 |
r1c2#4 4 | 4 | 4 | 4 |
r4c1#4 4 | 4 | 4 | 4 |
r5c1#4 4 | 4 | 4 | 4 |
r5c2#4 4 | 4 | 4 | 4 |
[no more 4s in blocks 1 or 4]
What are the possibilities? There are three, based on those column constraints:
r1c1#4 4 | 4 | 4 | 4 |
r5c2#4 4 | 4 | 4 | 4 |
r1c2#4 4 | 4 | 4 | 4 |
r4c1#4 4 | 4 | 4 | 4 |
r1c2#4 4 | 4 | 4 | 4 |
r5c1#4 4 | 4 | 4 | 4 |
The columns are both covered. The rule works! We could eliminate any of:
r7c1#4 4 | 4 | 4 | 4 |
r7c2#4 4 | 4 | 4 | 4 |
r8c1#4 4 | 4 | 4 | 4 |
r8c2#4 4 | 4 | 4 | 4 |
r9c1#4 4 | 4 | 4 | 4 |
r9c2#4 4 | 4 | 4 | 4 |
This rule turns out to be just another version of a simpler "locked candidate" rule, so
it isn't typically invoked, but it is a valid rule, nonetheless.
My point
My point is that, as other have said, all these rules simply amount to finding
situations that force eliminations that would "overcover" one of the constraints.