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:
“The first moments of sleep are an image of death; a hazy torpor grips our thoughts and it becomes impossible for us to determine the exact instant when the “I,” under another form, continues the task of existence.”
—Gérard De Nerval (1808–1855)
“There is nothing more poetic and terrible than the skyscrapers’ battle with the heavens that cover them. Snow, rain, and mist highlight, drench, or conceal the vast towers, but those towers, hostile to mystery and blind to any sort of play, shear off the rain’s tresses and shine their three thousand swords through the soft swan of the fog.”
—Federico García Lorca (1898–1936)