Knuth's Algorithm X: Difference between revisions

Revision as of 22:25, 11 July 2006

Revision as of 22:44, 13 July 2006

Line 1:

[[Donald Knuth|Donald Knuth's]] '''Algorithm X''', first presented in November of 2000, is a [[recursion (computer science)|recursive]], [[nondeterministic]], [[depth-first]], [[brute-force]] [[algorithm]] that finds all solutions to the [[exact cover]] problem represented by a matrix ''A'' consisting of 0s amdand 1s.

The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.