Revision as of 07:30, 30 June 2008 edit Rob Zako (talk \| contribs) 328 edits Algorithm X is a backtracking algorithm, not a brute-force algorithm ← Previous edit		Revision as of 07:52, 12 August 2008 edit undo Sunnan (talk \| contribs) 358 edits it's older than 2000, c.f. Knuth's paper on dancing links among others (where k. refers to dlx being used in 1999). it's just knuth's name for "trial-and-error" Next edit →
Line 1: [[Donald Knuth]]'s '''Algorithm X'''~~, first presented in November of 2000,~~ is a [[recursion (computer science)\|recursive]], [[Nondeterministic_algorithm\|nondeterministic]], [[depth-first]], [[backtracking]] [[algorithm]] that finds all solutions to the [[exact cover]] problem represented by a matrix ''A'' consisting of 0s and 1s. The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.

Knuth's Algorithm X: Difference between revisions