Exact cover

Article on other languages:

• Problem_der_exakten_Überdeckung
• Problème_de_la_couverture_exacte

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

In mathematics, given a set X and a collection of subsets of X, an exact cover is a subcollection of such that every element in X is contained in exactly one set in . An exact cover is a kind of cover.

In computer science, the exact cover problem is a decision problem to find an exact cover or else determine none exists. The exact cover problem is NP-complete^[1] and is one of Karp's 21 NP-complete problems.^[2] The exact cover problem is a kind of constraint satisfaction problem.

An exact cover problem can be represented by an incidence matrix or a bipartite graph. The exact cover problem is equivalent to the exact hitting set problem.

Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems. The N queens problem is a slightly generalized exact cover problem.

Problem definition

Given a set X and a collection of subsets of X, the exact cover problem is to find a subcollection of that satisfies two conditions:

1. The sets in are pairwise disjoint: The intersection of any two distinct sets is empty. In other words, every element in X is contained in at most one set in .
2. The union of the sets in is X: = X. In other words, every element in X is contained in at least one set in .

Thus an exact cover is "exact" in the sense that every element in X is contained in exactly one set in .

For an exact cover of X to exist, it is necessary that every element in X be contained in at least one set in . Thus it is typical to require that:

• The union of the sets in is X: = X.

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 the collection .

Examples

Let X = {1, 2, 3, 4, 5} be a set of 5 elements and let = {N, O, E, P'} be a collection of 4 subsets of X:

• N = { },
• O = {1, 3},
• E = {2, 4}, and
• P = {2, 3}.

Then there is no exact cover—indeed, not even a cover—of X because = {1, 2, 3, 4} is a proper subset of X = {1, 2, 3, 4, 5}: None of the sets in contains the element 5.

On the other hand, there is a cover if we let X = = {1, 2, 3, 4}. In particular, the subcollection {O, E} is an exact cover, since the sets O = {1, 3} and E = {2, 4} are disjoint and their union is X = {1, 2, 3, 4}.

The subcollection {N, O, E} is also an exact cover: The inclusion of the null set N = { } makes no difference, as it is disjoint with all sets and does not change the union.

The subcollection {E, P} is not an exact cover. The sets E and P are not disjoint: Their intersection {2} is not empty. Moreover, the union of the sets E and P, {2, 3, 4}, is not X = {1, 2, 3, 4}: Neither E nor P contains the element 1.

Detailed example

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

• A = {1, 4, 7};
• B = {1, 4};
• C = {4, 5, 7};
• D = {3, 5, 6};
• E = {2, 3, 6, 7}; and
• F = {2, 7}.

Then the subcollection = {B, D, F} is an exact cover, since every element in X is contained in exactly one of the sets:

• B = {1, 4};
• D = {3, 5, 6}; or
• F = {2, 7}.

Moreover, {B, D, F} is the only exact cover, as the following argument demonstrates: An exact cover must cover 1 and A and B are the only sets containing 1, thus 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 sets have at least one element in common with A. Then D is the only set left to be part of an exact cover, but the collection {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 include A or C, as each of these sets have at least one element in common with B. Then D is the only remaining set that contains 5, so D must be part of the exact cover. If an exact cover contains D, then it doesn't contain E, as D and E have the elements 3 and 6 in common. Then F is the only set left to be part of the exact cover, and the collection {B, D, F} is indeed an exact cover. See the example in the article on Knuth's Algorithm X for a matrix-based version of this argument.

Equivalent problems

Although the canonical exact cover problem involves a collection of subsets of a set X, the logic of the problem does not depend on the presence of sets containing elements. The same logic can arise whenever there are two sets with some binary relation between them.

Given a set S, a set X, and a binary relation R S × X between S and X, one can call a subset S* of S an "abstract exact cover" of X if every element of X is R ^-1-related to exactly one element of S*. Here R ^-1 is the converse of R.

In general, R ^-1 restricted to X × S* is a function, i.e., every element in X is R ^-1-related to exactly one element of S*: the unique element of S* that "covers" the particular element of X.

In the canonical exact cover problem, X is a set of elements, S is a collection of subsets of X, R is the binary relation "contains" between sets and elements, and R ^-1 restricted to X × S* is the function "is contained in" from elements to sets.

In general, an "abstract exact cover problem" arises whenever the goal is to select some objects in a set S such that each element in another set X is related to exactly one of the selected objects. For many interesting problems, such as pentomino tiling, Sudoku or the N queens problem, the elements of S represent choices and the elements of X represent constraints on those choices.

Matrix representation

An exact cover problem can be represented by the incidence matrix of the binary relation R, as is done with Knuth's Algorithm X and its implementation Dancing Links.

If S is a set of m elements and X is a set of n elements, then the relation R can be represented by an m×n matrix containing only 0s and 1s. The i-th row represents the i-th element s_i of S and the j-th column represents the j-th element x_j of X. The entry of the matrix in the i-th row and j-th column is 1 if s_i is R-related to x_j; the entry is 0 otherwise.

In the canonical exact cover problem, the entry of the matrix in the i-th row and j-th column is 1 if i-th set S_i contains the j-th element x_j; the entry is 0 otherwise.

Given such a matrix, an "exact cover" is a selection of rows such that every column has a 1 in exactly one of the selected rows. In other words, an exact cover is a selection of rows that sum to a row containing all 1s.

The two conditions for a canonical exact cover are equivalent to:

1. The selected rows are "pairwise disjoint" in the sense that any two distinct selected rows do not have a 1 in the same column.
2. The "union" of the selected rows is X in the sense that for every column there is a selected row with a 1 in that column.

Matrix example

If in the detailed example above we represent the 6 sets in = {A, B, C, D, E, F} as rows and the 7 elements in X = {1, 2, 3, 4, 5, 6, 7} as columns, then the exact cover problem is represented by the 6×7 matrix:^[3]

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

As above, the selection = {B, D, F} of rows is a solution to this exact cover problem:

	1	2	3	4	5	6	7
B	1	0	0	1	0	0	0
D	0	0	1	0	1	1	0
F	0	1	0	0	0	0	1

The selected rows are "pairwise disjoint" in the sense that any two do not have a 1 in the same column. Also, their "union" is X in the sense that for every column there is a selected row with a 1 in that column. In brief, every constraint column is satisfied in the sense that exactly one selected row has a 1 in that column.

See the example in the article on Knuth's Algorithm X for a detailed matrix-based solution to this problem.

Graph representation

An exact cover problem can be represented by the bipartite graph for the binary relation R.

The vertices of the bipartite graph are divided into two disjoint sets, one representing the elements of S and another representing the elements of X. An edge links the vertices for s_i and x_j if they are R-related.

Given such a bipartite graph, an "exact cover" is a selection S* of vertices in the set S such that every vertex in the set X is linked to exactly one vertex in S*.

Graph example

The exact cover problem in the detailed example and the matrix example above can be represented by a bipartite graph with 6+7 = 13 vertices and 17 edges:

As above, the selection S* = {B, D, F} of vertices is a solution to this exact cover problem:

Every vertex in the set X is linked to exactly one vertex in S*.

Exact hitting set

The exact hitting set problem is to find a subset of a set of elements that are contained in, or "hit", each subset in a collection of subsets exactly once.

An exact hitting set problem is equivalent to an exact cover problem. In the terminology above of an abstract exact cover problem, S is a set of elements, X is a collection of subsets of the set S, and R is the binary relation "is contained in" between elements and sets.

Exact hitting set example

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

• A = {1, 2}
• B = {5, 6}
• C = {4, 5}
• D = {1, 2, 3}
• E = {3, 4}
• F = {4, 5}
• G = {1, 3, 5, 6}

This exact hitting set problem can be represented by a 6×7 matrix:

	A	B	C	D	E	F	G
1	1	0	0	1	0	0	1
2	1	0	0	1	0	0	0
3	0	0	0	1	1	0	1
4	0	0	1	0	1	1	0
5	0	1	1	0	0	1	1
6	0	1	0	0	0	0	1

The solution is to select the 2nd, 4th and 6th rows of the matrix:

	A	B	C	D	E	F	G
2	1	0	0	1	0	0	0
4	0	0	1	0	1	1	0
6	0	1	0	0	0	0	1

Thus S* = {2, 4, 6} is an exact hitting set because every set in contains exactly one element in S*:

• A = {1, 2}
• B = {5, 6}
• C = {4, 5}
• D = {1, 2, 3}
• E = {3, 4}
• F = {4, 5}
• G = {1, 3, 5, 6}

It should be clear that this exact hitting set example is essentially the same as the matrix example and the detailed example above. The interpretation may be different but the logic is the same.

Finding solutions

Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem.

Dancing Links, commonly known as DLX, is the technique suggested by Knuth to efficiently implement his Algorithm X on a computer. Dancing Links uses the matrix representation of the problem. Dancing Links implements the matrix 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.

Generalizations

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 exactly once but other "secondary" constraints can be satisfied optional once or not at all.

As Donald 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.^[4] 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 need not be satisfied.

Noteworthy examples

Due to its NP-completeness, any problem in NP can be reduced 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 pentominoes, and solving Sudoku can both be viewed as exact cover problems.

Pentomino tiling

Main article: Pentomino

The problem of tiling a 60-square board with pentominoes is an example of an exact cover problem, as Donald Knuth explains in his paper "Dancing links."^[5][6]

For example, consider the problem of tiling with pentominoes an 8×8 chessboard with the 4 central squares removed:

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

The matrix representing the exact cover problem has 72 columns, one for each of the 12 pentominoes and one for each of the 60 squares of the board.

The matrix representing the exact cover problem has many rows, one row representing each way to place a pentomino on the board. 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. In the case of an 8×8 chessboard with the 4 central squares removed, there are 1568 such rows.

Name the twelve pentominoes F I L P N T U V W X Y Z.^[7] Name the squares in the board ij, where i is the rank and j is the file.

For the 8×8 chessboard with the 4 central squares removed, following are some of the 1568 rows:

F	12	13	21	22	32
F	13	14	22	23	33
…
I	11	12	13	14	15
I	12	13	14	15	16
…
L	11	21	31	41	42
L	12	22	32	42	43	…

One of many solutions of this exact cover problem is the following set of 12 rows:

I	11	12	13	14	15
N	16	26	27	37	47
L	17	18	28	38	48
U	21	22	31	41	42
X	23	32	33	34	43
W	24	25	35	36	46
P	51	52	53	62	63
F	56	64	65	66	75
Z	57	58	67	76	77
T	61	71	72	73	81
V	68	78	86	87	88
Y	74	82	83	84	85

This set of rows of the exact cover matrix corresponds to the following solution to the pentomino tiling problem:

I	I	I	I	I	N	L	L
U	U	X	W	W	N	N	L
U	X	X	X	W	W	N	L
U	U	X			W	N	L
P	P	P			F	Z	Z
T	P	P	F	F	F	Z	V
T	T	T	Y	F	Z	Z	V
T	Y	Y	Y	Y	V	V	V

See also Solving Pentomino Puzzles with Backtracking.

Sudoku

Main article: Sudoku

The problem in Sudoku 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.

Solving Sudoku is an exact cover problem.

More precisely, solving Sudoku is an exact hitting set problem, which is equivalent to an exact cover problem (as in Example 5 above), when viewed as a problem to select possibilities such that every constraint set contains (i.e., is hit by) exactly one selected possibility. In the notation above for the (generalized) exact cover problem, X is the set of possibilities, Y is a set of constraint sets, and R is the binary relation "is contained in."

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

The complete 729×324 matrix is available from Bob Hanson.

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

N queens problem

Main article: N queens problem

Please help improve this section by expanding it. Further information might be found on the talk page. (July 2008)

The N queens problem is an example of an exact cover problem.

See also

• Constraint satisfaction problem
• Dancing Links
• Difference_map_algorithm
• Hitting set
• Karp's 21 NP-complete problems
• Knuth's Algorithm X
• List of NP-complete problems

References

• Dahlke, K. "Exact cover". Math Reference Project. Retrieved on 2008-06-21.