Exact cover

In the mathematical field of combinatorics, given a collection of subsets of a set, an exact cover is a subcollection of such that each element in is contained in exactly one subset in.
One says that each element in is covered by exactly one subset in.
An exact cover is a kind of cover. In other words, is a partition of consisting of subsets contained in.
The exact cover problem to find an exact cover is a kind of constraint satisfaction problem. The elements of represent choices and the elements of represent constraints. It is NP-hard and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design.
An exact cover problem involves the relation contains between subsets and elements. But an exact cover problem can be represented by any heterogeneous relation between a set of choices and a set of constraints. For example, an exact cover problem is equivalent to an exact hitting set problem, an incidence matrix, or a bipartite graph.
In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP-complete and is one of Karp's 21 NP-complete problems. It is NP-complete even when each subset in contains exactly three elements; this restricted problem is known as exact cover by 3-sets, often abbreviated X3C.
Knuth's Algorithm X is an algorithm that finds all solutions to an exact cover problem. DLX is the name given to Algorithm X when it is implemented efficiently using Donald Knuth's Dancing Links technique on a computer.
The exact cover problem can be generalized slightly to involve not only exactly-once constraints but also at-most-once constraints.
Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems. The n queens problem is a generalized exact cover problem.

Formal definition

Given a collection of subsets of a set, an exact cover of is a subcollection of that satisfies two conditions:

The intersection of any two distinct subsets in is empty, i.e., the subsets in are pairwise disjoint. In other words, each element in is contained in at most one subset in.
The union of the subsets in is, i.e., the subsets in cover. In other words, each element in is contained in at least one subset in.

In short, an exact cover is exact in the sense that each element in is contained in exactly one subset in.
Equivalently, an exact cover of is a subcollection of that partitions.
For an exact cover of to exist, it is necessary that:

The union of the subsets in is. In other words, each element in is contained in at least one subset in.

If the empty set is contained in, then it makes no difference whether or not it is in any exact cover. Thus it is typical to assume that:

The empty set is not in. In other words, each subset in contains at least one element.
Basic examples

Let be a collection of subsets of a set such that:

,
,
, and
.

The subcollection is an exact cover of, since the subsets and are disjoint and their union is.
The subcollection is also an exact cover of.
Including the empty set makes no difference, as it is disjoint with all subsets and does not change the union.
The subcollection is not an exact cover of.
Even though the union of the subsets and is, the intersection of the subsets and,, is not empty. Therefore the subsets and do not meet the disjoint requirement of an exact cover.
The subcollection is also not an exact cover of.
Even though and are disjoint, their union is not, so they fail the cover requirement.
On the other hand, there is no exact cover—indeed, not even a cover—of because is a proper subset of : None of the subsets in contains the element 5.

Detailed example

Let = be a collection of subsets of a set = such that:

= ;
= ;
= ;
= ;
= ; and
=.

The subcollection = is an exact cover, since each element is covered by exactly one selected subset, as the highlighting makes clear.
Moreover, is the only exact cover, as the following argument demonstrates: Because and are the only subsets containing the element 1, an exact cover must contain or, but not both. If an exact cover contains, then it doesn't contain,,, or, as each of these subsets has the element 1, 4, or 7 in common with. Then is the only remaining subset, but the subcollection doesn't cover the element 2. In conclusion, there is no exact cover containing. On the other hand, if an exact cover contains, then it doesn't contain or, as each of these subsets has the element 1 or 4 in common with. Because is the only remaining subset containing the element 5, must be part of the exact cover. If an exact cover contains, then it doesn't contain, as has the elements 3 and 6 in common with. Then is the only remaining subset, and the subcollection is indeed an exact cover. See the example in the article on Knuth's Algorithm X for a matrix-based version of this argument.

Representations

An exact cover problem is defined by the heterogeneous relation contains between a collection of subsets and a set 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 ⊆ × between a set of choices and a set of constraints and the goal is to select a subset of such that each element in is -related to exactly one element in. Here is the converse of.
In general, restricted to × is a function from to, which maps each element in to the unique element in that is -related to that element in. This function is onto, unless contains an element that isn't -related to any element in.
Representations of an exact cover problem include an exact hitting set problem, an incidence matrix, and a bipartite graph.

Exact hitting set

In mathematics, given a set and a collection of subsets of, an exact hitting set is a subset of such that each subset in contains exactly one element in. One says that each subset in is hit by exactly one element in.
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 = be a set and = be a collection of subsets of such that:

Then = is an exact hitting set, since each subset in is hit by exactly one element in, 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:

∈,, ;
∈ , ;
∈,, ;
∈ , , ;
∈,,, ; and
∈ , .
Incidence matrix

The relation contains can be represented by an incidence matrix.
The matrix includes one row for each subset in and one column for each element in.
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:
Again, the subcollection = is an exact cover, since each column contains a 1 in exactly one selected row, as the highlighting makes clear.
See the example in the article on Knuth's Algorithm X for a matrix-based solution to the detailed example above.

Hypergraph

In turn, the incidence matrix can be seen also as describing a hypergraph. The hypergraph includes one node for each element in and one edge for each subset in ; each node is included in exactly one of the edges forming the cover.

Bipartite graph

The relation contains can be represented by a bipartite graph.
The vertices of the graph are divided into two disjoint sets, one representing the subsets in and another representing the elements in. 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 = is an exact cover, since the vertex corresponding to each element in is connected to exactly one selected vertex, as the highlighting makes clear.

Finding solutions

is the name Donald Knuth gave for "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem. Technically, Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm.
When Algorithm X is implemented efficiently using Donald Knuth's Dancing Links technique on a computer, Knuth calls it DLX. It uses the matrix representation of the problem, implemented as a series of doubly linked lists 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 Dancing Links technique to quickly select permutations of rows as possible solutions and to efficiently backtrack mistaken guesses.