Knuth's Algorithm X: Difference between revisions

Revision as of 08:10, 10 July 2006

Revision as of 12:58, 10 July 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 represented by a matrix ''A'' consisting of 0s amd 1s.

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.

Line 31:

|}

The nondeterministic choice of ''r'' means that the algorithm essentially clones itself into independent subalgorithms; each subalgorithm inherits the current matrix ''A'', but reduces it with respect to a different row ''r''.

If column ''c'' is entirely zero, there are no subalgorithms and the process terminates unsuccessfully.

The subalgorithms form a [[search tree]] in a natural way, with the original problem at the root and with level ''k'' containing each subalgorithm that corresponds to ''k'' chosen rows.

Backtracking is the process of traversing the tree in preorder, depth first.

Any systematic rule for choosing column ''c'' in this procedure will find all solutions, but some rules work much better than others.

To reduce the number of iterations, [[Donald Knuth|Knuth]] suggests that the column choosing algorithm select a column with the lowest number of 1s in it.