Knuth's Algorithm X: Difference between revisions

Revision as of 03:13, 6 May 2006

Revision as of 03:13, 6 May 2006

Line 1:

[[Donald Knuth|Donald Knuth's]] '''Algorithm X''', first presented in November of 2000, is a [[recursive function|recursive]], [[nondeterministic]], [[depth-first]], [[brute-force]] [[algorithm]] that finds all solutions to the [[exact cover]] problem.

For example, the following matrix represents an [[exact cover]] problem in which the goal is to choose a subset of the rows so that the digit 1 appears in each column exactly once. You just lost the game.

:<math>