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:
“Hunger makes you restless. You dream about food—not just any food, but perfect food, the best food, magical meals, famous and awe-inspiring, the one piece of meat, the exact taste of buttery corn, tomatoes so ripe they split and sweeten the air, beans so crisp they snap between the teeth, gravy like mother’s milk singing to your bloodstream.”
—Dorothy Allison (b. 1953)
“See, there is a place by me where you shall stand on the rock; and while my glory passes by I will put you in a cleft of the rock, and I will cover you with my hand until I have passed by;
then I will take away my hand, and you shall see my back; but my face shall not be seen.””
—Bible: Hebrew, Exodus 33:21-23.