Exact cover

<h2 id="formal-definition">Formal definition</h2>
Given a collection 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
 of <a href="/facts/Subset/SJGERmbA">subsets</a> of a set 
 
 
 
 X
 
 
 {\displaystyle X}
 
, an exact cover of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a subcollection 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
 of 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
 that satisfies two conditions:

<ul><li>The <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> of any two distinct subsets in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
 is <a href="/facts/Empty_set/ffEk3eA6">empty</a>, i.e., the subsets in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
 are <a href="/facts/Pairwise_disjoint/nLr8XRVd">pairwise disjoint</a>. In other words, each element in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is contained in at most one subset in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
.</li>
<li>The <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a> of the subsets in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
 is 
 
 
 
 X
 
 
 {\displaystyle X}
 
, i.e., the subsets in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
 <a href="/facts/Cover_(topology)/2VUdelA4">cover</a> 
 
 
 
 X
 
 
 {\displaystyle X}
 
. In other words, each element in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is contained in at least one subset in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
.</li></ul>
In short, an exact cover is exact in the sense that each element in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is contained in exactly one subset in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
.
Equivalently, an exact cover of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a subcollection 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
 of 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
 that <a href="/facts/Partition_of_a_set/VeP9g8CA">partitions</a> 
 
 
 
 X
 
 
 {\displaystyle X}
 
.
For an exact cover of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 to exist, it is necessary that:

<ul><li>The union of the subsets in 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
 is 
 
 
 
 X
 
 
 {\displaystyle X}
 
. In other words, each element in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is contained in at least one subset in 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
.</li></ul>
If the <a href="/facts/Empty_set/ffEk3eA6">empty set</a> 
 
 
 
 ∅
 
 
 {\displaystyle \emptyset }
 
 is contained in 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
, then it makes no difference whether or not it is in any exact cover. Thus it is typical to assume that:

<ul><li>The empty set is not in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
. In other words, each subset in 
 
 
 
 
 
 
 S
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathcal {S}}^{*}}
 
 contains at least one element.</li></ul>
<h2 id="basic-examples">Basic examples</h2>
Let 
 
 
 
 
 
 S
 
 
 =
 {
 N
 ,
 O
 ,
 P
 ,
 E
 }
 
 
 {\displaystyle {\mathcal {S}}=\{N,O,P,E\}}
 
 be a collection of subsets of a set 
 
 
 
 X
 =
 {
 1
 ,
 2
 ,
 3
 ,
 4
 }
 
 
 {\displaystyle X=\{1,2,3,4\}}
 
 such that:

<ul><li>
 
 
 
 N
 =
 {
 }
 
 
 {\displaystyle N=\{\}}
 
,</li>
<li>
 
 
 
 O
 =
 {
 1
 ,
 3
 }
 
 
 {\displaystyle O=\{1,3\}}
 
,</li>
<li>
 
 
 
 P
 =
 {
 1
 ,
 2
 ,
 3
 }
 
 
 {\displaystyle P=\{1,2,3\}}
 
, and</li>
<li>
 
 
 
 E
 =
 {
 2
 ,
 4
 }
 
 
 {\displaystyle E=\{2,4\}}
 
.</li></ul>
The subcollection 
 
 
 
 {
 O
 ,
 E
 }
 
 
 {\displaystyle \{O,E\}}
 
 is an exact cover of 
 
 
 
 X
 
 
 {\displaystyle X}
 
, since the subsets 
 
 
 
 O
 =
 {
 1
 ,
 3
 }
 
 
 {\displaystyle O=\{1,3\}}
 
 and 
 
 
 
 E
 =
 {
 2
 ,
 4
 }
 
 
 {\displaystyle E=\{2,4\}}
 
 are disjoint and their union is 
 
 
 
 X
 =
 {
 1
 ,
 2
 ,
 3
 ,
 4
 }
 
 
 {\displaystyle X=\{1,2,3,4\}}
 
.
The subcollection 
 
 
 
 {
 N
 ,
 O
 ,
 E
 }
 
 
 {\displaystyle \{N,O,E\}}
 
 is also an exact cover of 
 
 
 
 X
 
 
 {\displaystyle X}
 
.
Including the empty set 
 
 
 
 N
 =
 {
 }
 
 
 {\displaystyle N=\{\}}
 
 makes no difference, as it is disjoint with all subsets and does not change the union.
The subcollection 
 
 
 
 {
 E
 ,
 P
 }
 
 
 {\displaystyle \{E,P\}}
 
 is not an exact cover of 
 
 
 
 X
 
 
 {\displaystyle X}
 
.
Even though the union of the subsets 
 
 
 
 E
 
 
 {\displaystyle E}
 
 and 
 
 
 
 P
 
 
 {\displaystyle P}
 
 is 
 
 
 
 {
 1
 ,
 2
 ,
 3
 ,
 4
 }
 =
 X
 
 
 {\displaystyle \{1,2,3,4\}=X}
 
, the intersection of the subsets 
 
 
 
 E
 
 
 {\displaystyle E}
 
 and 
 
 
 
 P
 
 
 {\displaystyle P}
 
, 
 
 
 
 {
 2
 }
 
 
 {\displaystyle \{2\}}
 
, is not empty. Therefore the subsets 
 
 
 
 E
 
 
 {\displaystyle E}
 
 and 
 
 
 
 P
 
 
 {\displaystyle P}
 
 do not meet the disjoint requirement of an exact cover.
The subcollection 
 
 
 
 {
 N
 ,
 P
 }
 
 
 {\displaystyle \{N,P\}}
 
 is also not an exact cover of 
 
 
 
 X
 
 
 {\displaystyle X}
 
.
Even though 
 
 
 
 N
 
 
 {\displaystyle N}
 
 and 
 
 
 
 P
 
 
 {\displaystyle P}
 
 are disjoint, their union is not 
 
 
 
 X
 
 
 {\displaystyle X}
 
, so they fail the cover requirement.
On the other hand, there is no exact cover—indeed, not even a cover—of 
 
 
 
 Y
 =
 {
 1
 ,
 2
 ,
 3
 ,
 4
 ,
 5
 }
 
 
 {\displaystyle Y=\{1,2,3,4,5\}}
 
 because 
 
 
 
 ⋃
 
 
 S
 
 
 =
 {
 1
 ,
 2
 ,
 3
 ,
 4
 }
 
 
 {\displaystyle \bigcup {\mathcal {S}}=\{1,2,3,4\}}
 
 is a proper subset of 
 
 
 
 Y
 
 
 {\displaystyle Y}
 
: None of the subsets in 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
 contains the element 5.

<h3>Detailed example</h3>

Let S = {A, B, C, D, E, F} be a collection of subsets of a set X = {1, 2, 3, 4, 5, 6, 7} such that:

<ul><li>A = {1, 4, 7};</li>
<li>B = {1, 4};</li>
<li>C = {4, 5, 7};</li>
<li>D = {3, 5, 6};</li>
<li>E = {2, 3, 6, 7}; and</li>
<li>F = {2, 7}.</li></ul>
The subcollection S* = {B, D, F} is an exact cover, since each element is covered by (contained in) exactly one selected subset, as the highlighting makes clear.
Moreover, {B, D, F} is the only exact cover, as the following argument demonstrates: Because A and B are the only subsets containing the element 1, an exact cover must contain A or B, but not both. If an exact cover contains A, then it doesn't contain B, C, E, or F, as each of these subsets has the element 1, 4, or 7 in common with A. Then D is the only remaining subset, but the subcollection {A, D} doesn't cover the element 2. In conclusion, there is no exact cover containing A. On the other hand, if an exact cover contains B, then it doesn't contain A or C, as each of these subsets has the element 1 or 4 in common with B. Because D is the only remaining subset containing the element 5, D must be part of the exact cover. If an exact cover contains D, then it doesn't contain E, as E has the elements 3 and 6 in common with D. Then F is the only remaining subset, and the subcollection {B, D, F} is indeed an exact cover. See the <a href="/facts/Knuth%2527s_Algorithm_X/bWDAEgKj">example</a> in the article on <a href="/facts/Knuth%2527s_Algorithm_X/bWDAEgKj">Knuth's Algorithm X</a> for a matrix-based version of this argument.

<h2 id="representations">Representations</h2>
An exact cover problem is defined by the <a href="/facts/Heterogeneous_relation/r9BwGgaK">heterogeneous relation</a> contains between a collection S of subsets and a set X of elements. But there is nothing fundamental about subsets and elements.
A representation of an exact cover problem arises whenever there is a heterogeneous relation R ⊆ S × X between a set S of choices and a set X of constraints and the goal is to select a subset S* of S such that each element in X is RT-related to exactly one element in S*. Here RT is the <a href="/facts/Converse_relation/EVGlRSz7">converse</a> of R.
In general, RT <a href="/facts/Restriction_(mathematics)/JV59DhKy">restricted</a> to X × S* is a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> from X to S*, which maps each element in X to the unique element in S* that is R-related to that element in X. This function is <a href="/facts/Onto/KezhLpCb">onto</a>, unless S* contains an element (akin to the empty set) that isn't R-related to any element in X.
Representations of an exact cover problem include an exact hitting set problem, an incidence matrix, and a bipartite graph. 

<h3>Exact hitting set</h3>
In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, given a set S and a collection X of subsets of S, an exact hitting set S* is a subset of S such that each subset in X contains exactly one element in S*. One says that each subset in X is hit by exactly one element in S*.
The exact hitting set problem is a representation of an exact cover problem involving the relation is contained in rather than contains.
For example, let S = {a, b, c, d, e, f} be a set and X = {I, II, III, IV, V, VI, VII} be a collection of subsets of S such that:

<ul><li>I = {a, b}</li>
<li>II = {e, f}</li>
<li>III = {d, e}</li>
<li>IV = {a, b, c}</li>
<li>V = {c, d}</li>
<li>VI = {d, e}</li>
<li>VII = {a, c, e, f}</li></ul>
Then S* = {b, d, f} is an exact hitting set, since each subset in X is hit by (contains) exactly one element in S*, as the highlighting makes clear.
This exact hitting set example is essentially the same as the detailed example above. Displaying the relation is contained in (∈) from elements to subsets makes clear that we have simply replaced lettered subsets with elements and numbered elements with subsets:

<ul><li>a ∈ I, IV, VII;</li>
<li>b ∈ I, IV;</li>
<li>c ∈ IV, V, VII;</li>
<li>d ∈ III, V, VI;</li>
<li>e ∈ II, III, VI, VII; and</li>
<li>f ∈ II, VII.</li></ul>
<h3>Incidence matrix</h3>
The relation contains can be represented by an <a href="/facts/Incidence_matrix/eMXGWQBw">incidence matrix</a>.
The matrix includes one row for each subset in S and one column for each element in X.
The entry in a particular row and column is 1 if the corresponding subset contains the corresponding element, and is 0 otherwise.
In the matrix representation, an exact cover is a selection of rows such that each column contains a 1 in exactly one selected row. Each row represents a choice and each column represents a constraint.
For example, the relation contains in the detailed example above can be represented by a 6×7 incidence matrix:

<table><tbody><tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr><tr><th>A</th><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>B</th><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>C</th><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><th>D</th><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>E</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><th>F</th><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr></tbody></table>
Again, the subcollection S* = {B, D, F} is an exact cover, since each column contains a 1 in exactly one selected row, as the highlighting makes clear.
See the <a href="/facts/Knuth%2527s_Algorithm_X/bWDAEgKj">example</a> in the article on <a href="/facts/Knuth%2527s_Algorithm_X/bWDAEgKj">Knuth's Algorithm X</a> for a matrix-based solution to the detailed example above.

<h3>Hypergraph</h3>
In turn, the incidence matrix can be seen also as describing a <a href="/facts/Hypergraph/qIR2o2I3">hypergraph</a>. The hypergraph includes one node for each element in X and one edge for each subset in S; each node is included in exactly one of the edges forming the cover.

<h3>Bipartite graph</h3>
The relation contains can be represented by a <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a>.
The vertices of the graph are divided into two disjoint sets, one representing the subsets in S and another representing the elements in X. If a subset contains an element, an edge connects the corresponding vertices in the graph.
In the graph representation, an exact cover is a selection of vertices corresponding to subsets such that each vertex corresponding to an element is connected to exactly one selected vertex.
For example, the relation contains in the detailed example above can be represented by a bipartite graph with 6+7 = 13 vertices:

Again, the subcollection S* = {B, D, F} is an exact cover, since the vertex corresponding to each element in X is connected to exactly one selected vertex, as the highlighting makes clear.

<h2 id="finding-solutions">Finding solutions</h2>
<a href="/facts/Knuth%2527s_Algorithm_X/bWDAEgKj">Algorithm X</a> is the name <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a> gave for "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> Technically, Algorithm X is a <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursive</a>, <a href="/facts/Nondeterministic_algorithm/UubLdp3D">nondeterministic</a>, <a href="/facts/Depth-first/luxJKVph">depth-first</a>, <a href="/facts/Backtracking/Jm9vDUk8">backtracking</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a>.
When Algorithm X is implemented efficiently using <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a>'s <a href="/facts/Dancing_Links/WpaSJyuV">Dancing Links</a> technique on a computer, Knuth calls it DLX. It uses the matrix representation of the problem, implemented as a series of <a href="/facts/Doubly_linked_list/vFpCq7q2">doubly linked lists</a> of the 1s of the matrix: each 1 element has a link to the next 1 above, below, to the left, and to the right of itself. Because exact cover problems tend to be sparse, this representation is usually much more efficient in both size and processing time required. DLX then uses the <a href="/facts/Dancing_Links/WpaSJyuV">Dancing Links</a> technique to quickly select <a href="/facts/Permutation/JSw9ukmv">permutations</a> of rows as possible solutions and to efficiently backtrack (undo) mistaken guesses.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="generalized-exact-cover">Generalized exact cover</h2>
In a standard exact cover problem, each constraint must be satisfied exactly once.
It is a simple generalization to relax this requirement slightly and allow for the possibility that some primary constraints must be satisfied by exactly one choice but other secondary constraints can be satisfied by at most one choice.
As Knuth explains, a generalized exact cover problem can be converted to an equivalent exact cover problem by simply appending one row for each secondary column, containing a single 1 in that column.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> If in a particular candidate solution a particular secondary column is satisfied, then the added row isn't needed.
But if the secondary column isn't satisfied, as is allowed in the generalized problem but not the standard problem, then the added row can be selected to ensure the column is satisfied.
But Knuth goes on to explain that it is better working with the generalized problem directly, because the generalized algorithm is simpler and faster: A simple change to his Algorithm X allows secondary columns to be handled directly.
The <a href="/facts/N_queens_problem/XDx2HwlB">N queens problem</a> is an example of a generalized exact cover problem, as the constraints corresponding to the diagonals of the chessboard have a maximum rather than an exact queen count.

<h2 id="noteworthy-examples">Noteworthy examples</h2>
Due to its NP-completeness, any problem in NP can be <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduced</a> to exact cover problems, which then can be solved with techniques such as Dancing Links. However, for some well known problems, the reduction is particularly direct. For instance, the problem of tiling a board with <a href="/facts/Pentominoes/wGV39ULc">pentominoes</a>, and solving <a href="/facts/Sudoku/I5Savmhf">Sudoku</a> can both be viewed as exact cover problems.

<h3>Pentomino tiling</h3>
Main article: <a href="/facts/Pentomino/wGV39ULc">Pentomino</a>
The problem of tiling a 60-square board with the 12 different free <a href="/facts/Pentominoes/wGV39ULc">pentominoes</a> is an example of an exact cover problem, as <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a> explains in his paper "Dancing links."<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
For example, consider the problem of tiling with pentominoes an 8×8 chessboard with the 4 central squares removed:

<table><tbody><tr><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td></tr><tr><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td></tr><tr><td>31</td><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td></tr><tr><td>41</td><td>42</td><td>43</td><td></td><td></td><td>46</td><td>47</td><td>48</td></tr><tr><td>51</td><td>52</td><td>53</td><td></td><td></td><td>56</td><td>57</td><td>58</td></tr><tr><td>61</td><td>62</td><td>63</td><td>64</td><td>65</td><td>66</td><td>67</td><td>68</td></tr><tr><td>71</td><td>72</td><td>73</td><td>74</td><td>75</td><td>76</td><td>77</td><td>78</td></tr><tr><td>81</td><td>82</td><td>83</td><td>84</td><td>85</td><td>86</td><td>87</td><td>88</td></tr></tbody></table>
The problem involves two kinds of constraints:

Pentomino: For each of the 12 pentominoes, there is the constraint that it must be placed exactly once. Name these constraints after the corresponding pentominoes: F I L P N T U V W X Y Z.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Square: For each of the 60 squares, there is the constraint that it must be covered by a pentomino exactly once. Name these constraints after the corresponding squares in the board: ij, where i is the rank and j is the file.
Thus there are 12+60 = 72 constraints in all.
As both kinds of constraints are exactly-once constraints, the problem is an exact cover problem.
The problem involves many choices, one for each way to place a pentomino on the board.
It is convenient to consider each choice as satisfying a set of 6 constraints: 1 constraint for the pentomino being placed and 5 constraints for the five squares where it is placed.
In the case of an 8×8 chessboard with the 4 central squares removed, there are 1568 such choices, for example:

<ul><li>{F, 12, 13, 21, 22, 32}</li>
<li>{F, 13, 14, 22, 23, 33}</li>
<li>…</li>
<li>{I, 11, 12, 13, 14, 15}</li>
<li>{I, 12, 13, 14, 15, 16}</li>
<li>…</li>
<li>{L, 11, 21, 31, 41, 42}</li>
<li>{L, 12, 22, 32, 42, 43}</li>
<li>…</li></ul>
One of many solutions of this exact cover problem is the following set of 12 choices:

<ul><li>{I, 11, 12, 13, 14, 15}</li>
<li>{N, 16, 26, 27, 37, 47}</li>
<li>{L, 17, 18, 28, 38, 48}</li>
<li>{U, 21, 22, 31, 41, 42}</li>
<li>{X, 23, 32, 33, 34, 43}</li>
<li>{W, 24, 25, 35, 36, 46}</li>
<li>{P, 51, 52, 53, 62, 63}</li>
<li>{F, 56, 64, 65, 66, 75}</li>
<li>{Z, 57, 58, 67, 76, 77}</li>
<li>{T, 61, 71, 72, 73, 81}</li>
<li>{V, 68, 78, 86, 87, 88}</li>
<li>{Y, 74, 82, 83, 84, 85}</li></ul>
This set of choices corresponds to the following solution to the pentomino tiling problem:

A pentomino tiling problem is more naturally viewed as an exact cover problem than an exact hitting set problem, because it is more natural to view each choice as a set of constraints than each constraint as a set of choices.
Each choice relates to just 6 constraints, which are easy to enumerate. On the other hand, each constraint relates to many choices, which are harder to enumerate.
Whether viewed as an exact cover problem or an exact hitting set problem, the matrix representation is the same, having 1568 rows corresponding to choices and 72 columns corresponding to constraints. Each row contains a single 1 in the column identifying the pentomino and five 1s in the columns identifying the squares covered by the pentomino.
Using the matrix, a computer can find all solutions relatively quickly, for example, using <a href="/facts/Dancing_Links/WpaSJyuV">Dancing Links</a>.

<h3>Sudoku</h3>
 Main articles: <a href="/facts/Sudoku/I5Savmhf">Sudoku</a>, <a href="/facts/Mathematics_of_Sudoku/fcJqLklG">Mathematics of Sudoku</a>, <a href="/facts/Sudoku_solving_algorithms/eu186U5t">Sudoku solving algorithms</a>
The problem in <a href="/facts/Sudoku/I5Savmhf">Sudoku</a> is to assign numbers (or digits, values, symbols) to cells (or squares) in a grid so as to satisfy certain constraints.
In the standard 9×9 Sudoku variant, there are four kinds of constraints:

Row-Column: Each intersection of a row and column, i.e, each cell, must contain exactly one number.
Row-Number: Each row must contain each number exactly once
Column-Number: Each column must contain each number exactly once.
Box-Number: Each box must contain each number exactly once.
While the first constraint might seem trivial, it is nevertheless needed to ensure there is only one number per cell. Naturally, placing a number into a cell prohibits placing any other number into the now occupied cell.
Solving Sudoku is an exact cover problem.
More precisely, solving Sudoku is an <a href="/facts/Exact_hitting_set/C7QcbDcN">exact hitting set</a> problem, which is equivalent to an exact cover problem, when viewed as a problem to select possibilities such that each constraint set contains (i.e., is hit by) exactly one selected possibility.
Each possible assignment of a particular number to a particular cell is a possibility (or candidate). When Sudoku is played with pencil and paper, possibilities are often called pencil marks.
In the standard 9×9 Sudoku variant, in which each of 9×9 cells is assigned one of 9 numbers, there are 9×9×9=729 possibilities.
Using obvious notation for rows, columns and numbers, the possibilities can be labeled

R1C1#1, R1C1#2, …, R9C9#9.
The fact that each kind of constraint involves exactly one of something is what makes Sudoku an exact hitting set problem. The constraints can be represented by constraint sets. The problem is to select possibilities such that each constraint set contains (i.e., is hit by) exactly one selected possibility.
In the standard 9×9 Sudoku variant, there are four kinds of constraints sets corresponding to the four kinds of constraints:

Row-Column: A row-column constraint set contains all the possibilities for the intersection of a particular row and column, i.e., for a cell. For example, the constraint set for row 1 and column 1, which can be labeled R1C1, contains the 9 possibilities for row 1 and column 1 but different numbers:
R1C1 = { R1C1#1, R1C1#2, R1C1#3, R1C1#4, R1C1#5, R1C1#6, R1C1#7, R1C1#8, R1C1#9 }.
Row-Number: A row-number constraint set contains all the possibilities for a particular row and number. For example, the constraint set for row 1 and number 1, which can be labeled R1#1, contains the 9 possibilities for row 1 and number 1 but different columns:
R1#1 = { R1C1#1, R1C2#1, R1C3#1, R1C4#1, R1C5#1, R1C6#1, R1C7#1, R1C8#1, R1C9#1 }.
Column-Number: A column-number constraint set contains all the possibilities for a particular column and number. For example, the constraint set for column 1 and number 1, which can be labeled C1#1, contains the 9 possibilities for column 1 and number 1 but different rows:
C1#1 = { R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, R9C1#1 }.
Box-Number: A box-number constraint set contains all the possibilities for a particular box and number. For example, the constraint set for box 1 (in the upper lefthand corner) and number 1, which can be labeled B1#1, contains the 9 possibilities for the cells in box 1 and number 1:
B1#1 = { R1C1#1, R1C2#1, R1C3#1, R2C1#1, R2C2#1, R2C3#1, R3C1#1, R3C2#1, R3C3#1 }.
Since there are 9 rows, 9 columns, 9 boxes and 9 numbers, there are 9×9=81 row-column constraint sets, 9×9=81 row-number constraint sets, 9×9=81 column-number constraint sets, and 9×9=81 box-number constraint sets: 81+81+81+81=324 constraint sets in all.
In brief, the standard 9×9 Sudoku variant is an exact hitting set problem with 729 possibilities and 324 constraint sets.
Thus the problem can be represented by a 729×324 matrix.
Although it is difficult to present the entire 729×324 matrix, the general nature of the matrix can be seen from several snapshots:

<table><tbody><tr><td>Row-Column Constraints<table><tbody><tr><th></th><th>R1C1</th><th>R1C2</th><th>…</th></tr><tr><th>R1C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#2</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#3</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#4</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#5</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#6</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#7</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#8</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#9</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C2#1</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#3</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#4</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#5</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#6</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#7</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#8</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>R1C2#9</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr></tbody></table></td><td>Row-Number Constraints<table><tbody><tr><th></th><th>R1#1</th><th>R1#2</th><th>…</th></tr><tr><th>R1C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C2#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C2#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C3#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C3#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C4#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C4#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C5#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C5#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C6#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C6#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C7#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C7#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C8#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C8#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C9#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C9#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr></tbody></table></td><td>Column-Number Constraints<table><tbody><tr><th></th><th>C1#1</th><th>C1#2</th><th>…</th></tr><tr><th>R1C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R2C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R2C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R3C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R3C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R4C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R4C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R5C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R5C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R6C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R6C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R7C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R7C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R8C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R8C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R9C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R9C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr></tbody></table></td><td>Box-Number Constraints<table><tbody><tr><th></th><th>B1#1</th><th>B1#2</th><th>⋯</th></tr><tr><th>R1C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C2#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C2#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R1C3#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R1C3#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R2C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R2C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R2C2#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R2C2#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R2C3#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R2C3#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R3C1#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R3C1#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R3C2#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R3C2#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr><tr><th>R3C3#1</th><td>1</td><td>0</td><td>⋯</td></tr><tr><th>R3C3#2</th><td>0</td><td>1</td><td>⋯</td></tr><tr><th>⋮</th><td>⋮</td><td>⋮</td><td>⋱</td></tr></tbody></table></td></tr></tbody></table>
The complete 729×324 matrix is available from Robert Hanson.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
The set of possibilities RxCy#z can be arranged as a 9×9×9 cube in a 3-dimensional space with coordinates x, y, and z. Then each row Rx, column Cy, or number #z is a 9×9×1 "slice" of possibilities; each box Bw is a 9x3×3 "tube" of possibilities; each row-column constraint set RxCy, row-number constraint set Rx#z, or column-number constraint set Cy#z is a 9x1×1 "strip" of possibilities; each box-number constraint set Bw#z is a 3x3×1 "square" of possibilities; and each possibility RxCy#z is a 1x1×1 "cubie" consisting of a single possibility. Moreover, each constraint set or possibility is the <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> of the component sets. For example, R1C2#3 = R1 ∩ C2 ∩ #3, where ∩ denotes set intersection.
Although other Sudoku variations have different numbers of rows, columns, numbers and/or different kinds of constraints, they all involve possibilities and constraint sets, and thus can be seen as exact hitting set problems.

<h3>N queens problem</h3>
 Main article: <a href="/facts/N_queens_problem/XDx2HwlB">N queens problem</a>The <a href="/facts/N_queens_problem/XDx2HwlB">N queens problem</a> is the problem of placing n <a href="/facts/Chess/47ykvkHF">chess</a> <a href="/facts/Queen_(chess)/sHWc1RMX">queens</a> on an n×n <a href="/facts/Chessboard/BmECnjVp">chessboard</a> so that no two queens threaten each other. A solution requires that no two queens share the same row, column, or diagonal. It is an example of a generalized exact cover problem.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

The problem involves four kinds of constraints:

Rank: For each of the N ranks, there must be exactly one queen.
File: For each of the N files, there must be exactly one queen.
Diagonals: For each of the 2N − 1 diagonals, there must be at most one queen.
Reverse diagonals: For each of the 2N − 1 reverse diagonals, there must be at most one queen.
The 2N ranks and files form the primary constraints, while the 4N − 2 diagonal and reverse diagonals form the secondary constraints. Further, because each of first and last diagonals and reverse diagonals involves only one square on the chessboard, these can be omitted and thus one can reduce the number of secondary constraints to 4N − 6. The matrix for the N queens problem then has N2 rows and 6N − 6 columns, each row for a possible queen placement on each square on the chessboard, and each column for each constraint.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Constraint_satisfaction_problem/oKCeIV2L">Constraint satisfaction problem</a></li>
<li><a href="/facts/Dancing_Links/WpaSJyuV">Dancing Links</a></li>
<li><a href="/facts/Difference_map_algorithm/nkhgPmWU">Difference map algorithm</a></li>
<li><a href="/facts/Karp%2527s_21_NP-complete_problems/dqu5bBh0">Karp's 21 NP-complete problems</a></li>
<li><a href="/facts/Knuth%2527s_Algorithm_X/bWDAEgKj">Knuth's Algorithm X</a></li>
<li><a href="/facts/List_of_NP-complete_problems/pmR9Dlym">List of NP-complete problems</a></li>
<li><a href="/facts/Partition_of_a_set/VeP9g8CA">Partition of a set</a></li>
<li><a href="/facts/Perfect_matching/LmtRYLgK">Perfect matching</a> and <a href="/facts/3-dimensional_matching/WFr6DxFj">3-dimensional matching</a> are special cases of the exact cover problem</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://github.com/blynn/dlx">Free Software implementation of an Exact Cover solver in C</a> - uses Algorithm X and Dancing Links. Includes examples for Sudoku and logic grid puzzles.</li>
<li><a href="https://github.com/thomasjungblut/go-dancing-links">Exact Cover solver in Golang</a> - uses Algorithm X and Dancing Links. Includes examples for Sudoku and N queens.</li>
<li><a href="https://www.mathreference.com/lan-cx-np,excov.html">Exact cover</a> - Math Reference Project</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation

Pradheebha Surendiran, Christoph Robert Meinecke, Aseem Salhotra, Georg Heldt, Jingyuan Zhu, Alf Månsson, Stefan Diez, Danny Reuter, Hillel Kugler, Heiner Linke, and Till Korten

2022 2 (5), 396-403

DOI: 10.1021/acsnanoscienceau.2c00013 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Korten, Till; Diez, Stefan; Linke, Heiner; Nicolau, Dan V; Kugler, Hillel (2021-08-01). "Design of network-based biocomputation circuits for the exact cover problem". New Journal of Physics. 23 (8): 085004. Bibcode:2021NJPh...23h5004K. doi:10.1088/1367-2630/ac175d. ISSN 1367-2630. <a href="https://doi.org/10.1088%2F1367-2630%2Fac175d" target="_blank">https://doi.org/10.1088%2F1367-2630%2Fac175d</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">M.R. Garey; D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. This book is a classic, developing the theory, then cataloguing many NP-Complete problems. <a href="0-7167-1045-5" target="_blank">0-7167-1045-5</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Richard M. Karp (1972). "Reducibility among combinatorial problems" (PDF). In R.E. Miller; J.W. Thatcher (eds.). Complexity of Computer Computations. Proc. of a Symp. on the Complexity of Computer Computations. New York: Plenum. pp. 85–103. ISBN 0-3063-0707-3. Archived from the original (PDF) on 2011-06-29. Retrieved 2008-06-27. <a href="0-3063-0707-3" target="_blank">0-3063-0707-3</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">M.R. Garey; D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. This book is a classic, developing the theory, then cataloguing many NP-Complete problems. <a href="0-7167-1045-5" target="_blank">0-7167-1045-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047. <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047. <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047. <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Donald Knuth explains this simple generalization in his paper "Dancing Links," in particular, in explaining the tetrastick and N queens problems. <a href="/wiki/N_queens_problem" target="_blank">/wiki/N_queens_problem</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047. <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Golomb, Solomon W. (1994). Polyominoes: Puzzles, Patterns, Problems, and Packings (2nd ed.). Princeton, New Jersey: Princeton University Press. p. 7. ISBN 0-691-02444-8. <a href="0-691-02444-8" target="_blank">0-691-02444-8</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Hanson, Robert M. "Exact Cover Problem". www.stolaf.edu. St. Olaf College. Retrieved 20 August 2020. <a href="https://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm" target="_blank">https://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047. <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

Exact cover open-in-new

Exact cover