In mathematics, given a collection of subsets of a set X, an exact cover is a subcollection of such that each element in X is contained in exactly one subset in . One says that each element in X is covered by exactly one subset 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 and is one of Karp's 21 NP-complete problems. 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.
Knuth's Algorithm X is an algorithm that finds all solutions to an exact cover problem. Dancing Links, commonly known as DLX, is the technique suggested by Donald Knuth to efficiently implement his Algorithm X on a computer.
The standard exact cover problem can be generalized slightly to involve not only "exactly one" constraints but also "at-most-one" constraints.
Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems. The N queens problem is a slightly generalized exact cover problem.
Read more about Exact Cover: Formal Definition, Representations, Equivalent Problems, Exact Hitting Set, Finding Solutions, Generalizations, Noteworthy Examples
Famous quotes containing the words exact and/or cover:
“For 350 years we have been taught that reading maketh a full man, conference a ready man and writing an exact man. Football’s place is to add a patina of character, a deference to the rules and a respect for authority.”
—Walter Wellesley (Red)
“Again we have here two distinctions that are no distinctions, but made to seem so by terms invented by I know not whom to cover ignorance, and blind the understanding of the reader: for it cannot be conceived that there is any liberty greater, than for a man to do what he will.”
—Thomas Hobbes (1579–1688)