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. 


Disclaimer