Knuth's Algorithm X: Difference between revisions

Revision as of 02:13, 14 January 2006

Revision as of 02:20, 14 January 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 search|brute -force]] [[algorithm]] whichthat 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.

:<math>

Line 14 ⟶ 13:

\end{bmatrix}

</math>

The goal is to iteratively partition each row from their initial subset (unselected) into the selected or rejected subsets.

Algorithm X functions as follows:

*# Using any [[deterministic algorithm]], choose a column, c.

*# Nondeterministically choose any row, r, which has a 1 in column c, and add that row to the solution set.

*# Remove any unselected rows which have a 1 in any column which r has a 1 in.

*# Remove from the matrix any columns for which row r has a 1.

*# Repeat the algorithm on this reduced matrix.

When the matrix is empty, you have a solution. 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.

The example above is solved as follows, using 0 based notation:

Line 39 ⟶ 35:

Column 3 is removed.

Column 6 is removed.

Iterative result:

Line 48 ⟶ 43:

\end{bmatrix}

</math>

Column 0 has no 1s, so this potential solution is rejected, and we backtrack. The previously selected row, 0, can now safely be removed from consideration of this submatrix. Result:

Line 61 ⟶ 55:

\end{bmatrix}

</math>

The lowest number of 1s in any column is 1, and column 0 is the first column with one 1, so column 0 is selected.

Line 68 ⟶ 61:

Column 0 is removed.

Column 3 is removed.

Iterative result:

Line 79 ⟶ 71:

\end{bmatrix}

</math>

Each column has one or more 1s, so we continue.

Line 88 ⟶ 79:

Column 2 is removed.

Column 3 is removed.

Iterative result:

Line 98 ⟶ 88:

\end{bmatrix}

</math>

Each column has one or more 1s, so we continue.

Line 107 ⟶ 96:

The result is an empty matrix, so this is a solution. The elements represented by the selected rows are the solution set.

[[Donald Knuth]] further suggested an implementation of this algorithm using circular [[doubly linked list]]s, and named this [[Dancing Links]], or DLX.