Exact cover

In the mathematical field of combinatorics, given a collection ${\displaystyle {\mathcal {S}}}$ of subsets of a set ${\displaystyle X}$, an exact cover is a subcollection ${\displaystyle {\mathcal {S}}^{*}}$ of ${\displaystyle {\mathcal {S}}}$ such that each element in ${\displaystyle X}$ is contained in exactly one subset in ${\displaystyle {\mathcal {S}}^{*}}$. One says that each element in ${\displaystyle X}$ is covered by exactly one subset in ${\displaystyle {\mathcal {S}}^{*}}$.^[1] An exact cover is a kind of cover. It is non-deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design.^[2]

In other words, ${\displaystyle {\mathcal {S}}^{*}}$ is a partition of ${\displaystyle X}$ consisting of subsets contained in ${\displaystyle {\mathcal {S}}}$.

The exact cover problem to find an exact cover is a kind of constraint satisfaction problem. The elements of ${\displaystyle {\mathcal {S}}}$ represent choices and the elements of ${\displaystyle X}$ represent constraints.

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^[3] and is one of Karp's 21 NP-complete problems.^[4] It is NP-complete even when each subset in S contains exactly three elements; this restricted problem is known as exact cover by 3-sets, often abbreviated X3C.^[3]

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.^[5]

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.