Exact cover

In mathematics, given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*.One says that each element in X is covered by exactly one subset in S*.An exact cover is a kind of cover. In mathematics, given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*.One says that each element in X is covered by exactly one subset in S*.An exact cover is a kind of cover. In computer science, the exact cover problem is a decision problem to determine if an exact cover exists.The exact cover problem is NP-completeand 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. DLX is the name given to Algorithm X when it is implemented efficiently using Donald Knuth's Dancing Links technique on a computer.