Knuth's Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique. The exact cover problem is represented in Algorithm X by a matrix A consisting of 0s and 1s. The goal is to select a subset of the rows such that the digit 1 appears in each column exactly once. Algorithm X works as follows:
- Comment
- enAlgorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique. The exact cover problem is represented in Algorithm X by a matrix A consisting of 0s and 1s. The goal is to select a subset of the rows such that the digit 1 appears in each column exactly once. Algorithm X works as follows:
- Has abstract
- enAlgorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique. The exact cover problem is represented in Algorithm X by a matrix A consisting of 0s and 1s. The goal is to select a subset of the rows such that the digit 1 appears in each column exactly once. Algorithm X works as follows: # If the matrix A has no columns, the current partial solution is a valid solution; terminate successfully. 1. * Otherwise choose a column c (deterministically). 2. * Choose a row r such that Ar, c = 1 (nondeterministically). 3. * Include row r in the partial solution. 4. * For each column j such that Ar, j = 1,for each row i such that Ai, j = 1,delete row i from matrix A.delete column j from matrix A. 5. * Repeat this algorithm recursively on the reduced matrix A. The nondeterministic choice of r means that the algorithm recurses over 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, Knuth suggests that the column-choosing algorithm select a column with the smallest number of 1s in it.
- Hypernym
- Knuth
- Is primary topic of
- Knuth's Algorithm X
- Label
- enKnuth's Algorithm X
- Link from a Wikipage to an external page
- www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf
- www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
- Link from a Wikipage to another Wikipage
- Algorithm
- Backtracking
- Category:Donald Knuth
- Category:Search algorithms
- Dancing links
- Dancing Links
- Depth-first
- Deterministic algorithm
- Donald Knuth
- Doubly linked list
- Exact cover
- Nondeterministic algorithm
- Recursion (computer science)
- Search tree
- Torus
- SameAs
- 4paqU
- Algorithme X de Knuth
- Knuth's Algorithm X
- m.09qv19
- Q6424025
- X算法
- Кнутов алгоритам Икс
- Кнутов алгоритам Икс
- الگوریتم اکس کنوث
- Subject
- Category:Donald Knuth
- Category:Search algorithms
- WasDerivedFrom
- Knuth's Algorithm X?oldid=1121142608&ns=0
- WikiPageLength
- 14379
- Wikipage page ID
- 3626542
- Wikipage revision ID
- 1121142608
- WikiPageUsesTemplate
- Template:ArXiv
- Template:Citation
- Template:Donald Knuth navbox
- Template:Mathcal
- Template:Quote frame
- Template:Reflist
- Template:Short description
- Template:Sup