Exact 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] An exact cover problem involves the relation contains between subsets and elements.

DLX is the name given to Algorithm X when it is implemented efficiently using Donald Knuth's Dancing Links technique on a computer.

Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems.

Because D is the only remaining subset containing the element 5, D must be part of the exact cover.

See the example in the article on Knuth's Algorithm X for a matrix-based version of this argument.

An exact cover problem is defined by the heterogeneous relation contains between a collection S of subsets and a set X of 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*.

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: 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.

For example, the relation contains in the detailed example above can be represented by a 6×7 incidence matrix: 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.

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.

Algorithm X is the name Donald Knuth gave for "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem.

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 (undo) mistaken guesses.

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.

[6] 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 N queens problem 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.

In the case of an 8×8 chessboard with the 4 central squares removed, there are 1568 such choices, for example: One of many solutions of this exact cover problem is the following set of 12 choices: 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.

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.

Using the matrix, a computer can find all solutions relatively quickly, for example, using Dancing Links.

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 The fact that each kind of constraint involves exactly one of something is what makes Sudoku an exact hitting set problem.

[8] Note that 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.

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.

A solution requires that no two queens share the same row, column, or diagonal.