Wikipedia

Knuth's Algorithm X: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Rob Zako (talk | contribs)
328 edits
Move exampe to separate section
→Example: Fixed typo
Tags: Mobile edit Mobile web edit
 
(67 intermediate revisions by 41 users not shown)
Line 1:
{{Short description|Algorithm for exact cover problem}}
[[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.
'''Algorithm X''' is an [[algorithm]] for solving the [[exact cover]] problem. It is a straightforward [[Recursion (computer science)|recursive]], [[Nondeterministic algorithm|nondeterministic]], [[depth-first]], [[backtracking]] algorithm used by [[Donald Knuth]] to demonstrate an efficient implementation called DLX, which uses the [[dancing links]] technique.<ref name="knuth">{{cite arXiv | author = Knuth, Donald | author-link = Donald Knuth | title = Dancing links | year = 2000 | eprint = cs/0011047 }}</ref><ref>{{Cite journal |last=Banerjee |first=Bikramjit |last2=Kraemer |first2=Landon |last3=Lyle |first3=Jeremy |date=2010-07-04 |title=Multi-Agent Plan Recognition: Formalization and Algorithms |url=https://ojs.aaai.org/index.php/AAAI/article/view/7746 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |volume=24 |issue=1 |pages=1059–1064 |doi=10.1609/aaai.v24i1.7746 |issn=2374-3468|doi-access=free }}</ref>
The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.
 
==Algorithm X functions as follows:==
The exact cover problem is represented in Algorithm X by an [[incidence 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:
:{| border="1" cellpadding="5" cellspacing="0"
 
|
# If the matrix ''A'' ishas emptyno columns, the problemcurrent partial solution is solveda valid solution; terminate successfully.
# Otherwise choose a column ''c'' ([[deterministic algorithm|deterministically]]).
# Choose a row ''r'' such that ''A''<sub>''r'', ''c''</sub> = 1 ([[nondeterministic algorithm|nondeterministically]]).
# Include row ''r'' in the partial solution.
# For each column ''j'' such that ''A''<sub>''r'', ''j''</sub> = 1,
#: delete column ''j'' from matrix ''A'';
#: for each row ''i'' such that ''A''<sub>''i'', ''j''</sub> = 1,
#:: delete row ''i'' from matrix ''A''.
#: delete column ''j'' from matrix ''A''.
# Repeat this algorithm recursively on the reduced matrix ''A''.
|}
 
 
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''.
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.
 
Line 24 ⟶ 25:
 
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 lowestsmallest number of 1s in it.
 
== Example ==
For example, consider the exact cover problem representedspecified by the matrixuniverse ''U'' = {1, 2, 3, 4, 5, 6, 7} and the collection of sets {{mathcal|S}} = {''A'', ''B'', ''C'', ''D'', ''E'', ''F''}, where:
:* ''A'' = {1, 4, 7};
:* ''B'' = {1, 4};
:* ''C'' = {4, 5, 7};
:* ''D'' = {3, 5, 6};
:* ''E'' = {2, 3, 6, 7}; and
:* ''F'' = {2, 7}.
 
This problem is represented by the matrix:
:<math>
 
\begin{bmatrix}
:{| class="wikitable"
1 & 0 & 0 & 1 & 0 & 0 & 1 \\
! !! 1 &!! 02 &!! 03 & 1!! &4 0!! &5 0!! &6 0!! \\7
|-
0 & 0 & 0 & 1 & 1 & 0 & 1 \\
! ''A''
0 & 0 & 1 & 0 & 1 & 1 & 0 \\
| 1 || 0 &|| 10 &|| 1 &|| 0 &|| 0 &|| 1 & 1 \\
|-
0 & 1 & 0 & 0 & 0 & 0 & 1
! ''B''
\end{bmatrix}
| 1 || 0 || 0 || 1 || 0 || 0 || 0
</math>
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
Algorithm X with Knuth's suggested heuristic for selecting columns solves this problem as follows:
 
'''Level 0'''
 
Step 1—The matrix is not empty, so the algorithm proceeds.
 
Step 2—The lowest number of 1s in any column is two. Column 1 is the first column with two 1s and thus is selected (deterministically):
 
:{| class="wikitable"
! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
! ''A''
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 1 || 0 || 0 || 1
|-
! ''B''
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 1 || 0 || 0 || 0
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
Step 3—Rows ''A'' and ''B'' each have a 1 in column 1 and thus are selected (nondeterministically).
 
The algorithm moves to the first branch at level 1…
 
: '''Level 1: Select Row ''A'''''
 
: Step 4—Row ''A'' is included in the partial solution.
 
: Step 5—Row ''A'' has a 1 in columns 1, 4, and 7:
 
::{| class="wikitable"
! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! <span style="color:blue">7</span>
|-
! <span style="color:red">''A''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span>
|-
! ''B''
| 1 || 0 || 0 || 1 || 0 || 0 || 0
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
: Column 1 has a 1 in rows ''A'' and ''B''; column 4 has a 1 in rows ''A'', ''B'', and ''C''; and column 7 has a 1 in rows ''A'', ''C'', ''E'', and ''F''. Thus, rows ''A'', ''B'', ''C'', ''E'', and ''F'' are to be removed and columns 1, 4 and 7 are to be removed:
 
::{| class="wikitable"
! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! <span style="color:red">7</span>
|-
! <span style="color:blue">''A''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span>
|-
! <span style="color:blue">''B''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 0
|-
! <span style="color:blue">''C''</span>
| 0 || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 1 || 0 || <span style="color:red;font-weight:bold">1</span>
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! <span style="color:blue">''E''</span>
| 0 || 1 || 1 || 0 || 0 || 1 || <span style="color:red;font-weight:bold">1</span>
|-
! <span style="color:blue">''F''</span>
| 0 || 1 || 0 || 0 || 0 || 0 || <span style="color:red;font-weight:bold">1</span>
|}
 
: Row ''D'' remains and columns 2, 3, 5, and 6 remain:
 
::{| class="wikitable"
! !! 2 !! 3 !! 5 !! 6
|-
! ''D''
| 0 || 1 || 1 || 1
|}
 
: Step 1—The matrix is not empty, so the algorithm proceeds.
 
: Step 2—The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s:
 
::{| class="wikitable"
! !! <span style="color:red">2</span> !! 3 !! 5 !! 6
|-
! ''D''
| 0 || 1 || 1 || 1
|}
: Thus this branch of the algorithm terminates unsuccessfully.
 
: The algorithm moves to the next branch at level 1…
 
: '''Level 1: Select Row ''B'''''
 
: Step 4—Row ''B'' is included in the partial solution.
 
: Row ''B'' has a 1 in columns 1 and 4:
 
::{| class="wikitable"
! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! 7
|-
! ''A''
| 1 || 0 || 0 || 1 || 0 || 0 || 1
|-
! <span style="color:red">''B''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 0
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
: Column 1 has a 1 in rows ''A'' and ''B''; and column 4 has a 1 in rows ''A'', ''B'', and ''C''. Thus, rows ''A'', ''B'', and ''C'' are to be removed and columns 1 and 4 are to be removed:
 
::{| class="wikitable"
! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! 7
|-
! <span style="color:blue">''A''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 1
|-
! <span style="color:blue">''B''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 0
|-
! <span style="color:blue">''C''</span>
| 0 || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
: Rows ''D'', ''E'', and ''F'' remain and columns 2, 3, 5, 6, and 7 remain:
 
::{| class="wikitable"
! !! 2 !! 3 !! 5 !! 6 !! 7
|-
! ''D''
| 0 || 1 || 1 || 1 || 0
|-
! ''E''
| 1 || 1 || 0 || 1 || 1
|-
! ''F''
| 1 || 0 || 0 || 0 || 1
|}
 
: Step 1—The matrix is not empty, so the algorithm proceeds.
 
: Step 2—The lowest number of 1s in any column is one. Column 5 is the first column with one 1 and thus is selected (deterministically):
 
::{| class="wikitable"
! !! 2 !! 3 !! <span style="color:red">5</span> !! 6 !! 7
|-
! ''D''
| 0 || 1 || <span style="color:red;font-weight:bold">1</span> || 1 || 0
|-
! ''E''
| 1 || 1 || 0 || 1 || 1
|-
! ''F''
| 1 || 0 || 0 || 0 || 1
|}
 
: Step 3—Row ''D'' has a 1 in column 5 and thus is selected (nondeterministically).
 
: The algorithm moves to the first branch at level 2…
 
:: '''Level 2: Select Row ''D'''''
 
:: Step 4—Row ''D'' is included in the partial solution.
 
:: Step 5—Row ''D'' has a 1 in columns 3, 5, and 6:
 
:::{| class="wikitable"
! !! 2 !! <span style="color:blue">3</span> !! <span style="color:blue">5</span> !! <span style="color:blue">6</span> !! 7
|-
! <span style="color:red">''D''</span>
| 0 || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || 0
|-
! ''E''
| 1 || 1 || 0 || 1 || 1
|-
! ''F''
| 1 || 0 || 0 || 0 || 1
|}
 
:: Column 3 has a 1 in rows ''D'' and ''E''; column 5 has a 1 in row ''D''; and column 6 has a 1 in rows ''D'' and ''E''. Thus, rows ''D'' and ''E'' are to be removed and columns 3, 5, and 6 are to be removed:
 
:::{| class="wikitable"
! !! 2 !! <span style="color:red">3</span> !! <span style="color:red">5</span> !! <span style="color:red">6</span> !! 7
|-
! <span style="color:blue">''D''</span>
| 0 || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || 0
|-
! <span style="color:blue">''E''</span>
| 1 || <span style="color:red;font-weight:bold">1</span> || 0 || <span style="color:red;font-weight:bold">1</span> || 1
|-
! ''F''
| 1 || 0 || 0 || 0 || 1
|}
 
:: Row ''F'' remains and columns 2 and 7 remain:
 
:::{| class="wikitable"
! !! 2 !! 7
|-
! ''F''
| 1 || 1
|}
 
:: Step 1—The matrix is not empty, so the algorithm proceeds.
 
:: Step 2—The lowest number of 1s in any column is one. Column 2 is the first column with one 1 and thus is selected (deterministically):
 
:::{| class="wikitable"
! !! <span style="color:red">2</span> !! 7
|-
! ''F''
| <span style="color:red;font-weight:bold">1</span> || 1
|}
 
:: Row ''F'' has a 1 in column 2 and thus is selected (nondeterministically).
 
:: The algorithm moves to the first branch at level 3…
 
::: '''Level 3: Select Row ''F'''''
 
::: Step 4—Row ''F'' is included in the partial solution.
 
::: Row ''F'' has a 1 in columns 2 and 7:
 
::::{| class="wikitable"
! !! <span style="color:blue">2</span> !! <span style="color:blue">7</span>
|-
! <span style="color:red">''F''</span>
| <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span>
|}
 
::: Column 2 has a 1 in row ''F''; and column 7 has a 1 in row ''F''. Thus, row ''F'' is to be removed and columns 2 and 7 are to be removed:
 
::::{| class="wikitable"
! !! <span style="color:red">2</span> !! <span style="color:red">7</span>
|-
! <span style="color:blue">''F''</span>
| <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span>
|}
 
::: No rows and no columns remain:
 
::::{| class="wikitable"
! &nbsp;
|}
 
::: Step 1—The matrix is empty, thus this branch of the algorithm terminates successfully.
 
::: As rows ''B'', ''D'', and ''F'' have been selected (step 4), the final solution in this branch is:
 
::::{| class="wikitable"
! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
! ''B''
| 1 || 0 || 0 || 1 || 0 || 0 || 0
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
::: In other words, the subcollection {''B'', ''D'', ''F''} is an exact cover, since every element is contained in exactly one of the sets ''B'' = {1, 4}, ''D'' = {3, 5, 6}, or ''F'' = {2, 7}.
This problem is solved as follows, using 0 based notation:
The lowest number of 1s in any column is 2, and column 0 is the first column with two 1s, so column 0 is selected.
Row 0 is selected as the first row with a 1 on column 0.
Row 1 has a 1 in column 0, so is removed.
Row 2 has a 1 in column 3, so is removed.
Row 4 has a 1 in column 6, so is removed.
Row 5 has a 1 in column 6, so is removed.
Column 0 is removed.
Column 3 is removed.
Column 6 is removed.
 
::: There are no more selected rows at level 3, thus the algorithm moves to the next branch at level 2…
Iterative result:
:<math>
\begin{bmatrix}
0 & 0 &0 & 0 \\
0 & 1 &1 & 1
\end{bmatrix}
</math>
 
:: There are no more selected rows at level 2, thus the algorithm moves to the next branch at level 1…
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:
 
: There are no more selected rows at level 1, thus the algorithm moves to the next branch at level 0…
:<math>
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}
</math>
 
There are no branches at level 0, thus the algorithm terminates.
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.
Row 0 is selected as the first row with a 1 on column 0.
Row 1 has a 1 in column 3, so it is removed.
Column 0 is removed.
Column 3 is removed.
 
In summary, the algorithm determines there is only one exact cover: {{mathcal|S}}{{sup|*}} = {''B'', ''D'', ''F''}.
Iterative result:
:<math>
\begin{bmatrix}
0 & 0 &0 & 0 & 0 \\
0 & 1 &1 & 1 & 0 \\
1 & 1 &0 & 1 & 1 \\
1 & 0 &0 & 0 & 1
\end{bmatrix}
</math>
 
==Implementations==
Each column has one or more 1s, so we continue.
Knuth's main purpose in describing Algorithm X was to demonstrate the utility of [[dancing links]]. Knuth showed that Algorithm X can be implemented efficiently on a computer using dancing links in a process Knuth calls ''"DLX"''. DLX uses the matrix representation of the [[exact cover]] problem, implemented as [[doubly linked list]]s of the 1s of the matrix: each 1 element has a link to the next 1 above, below, to the left, and to the right of itself. (Technically, because the lists are circular, this forms a [[torus]]). Because exact cover problems tend to be sparse, this representation is usually much more efficient in both size and processing time required. DLX then uses dancing links to quickly select permutations of rows as possible solutions and to efficiently backtrack (undo) mistaken guesses.<ref name="knuth" />
The lowest number of 1s in any column is 1, and column 2 is the first column with one 1, so column 2 is selected.
Row 1 is selected as the first row with a 1 on column 2.
Row 2 has a 1 in column 1, so is removed.
Column 1 is removed.
Column 2 is removed.
Column 3 is removed.
 
==See also==
Iterative result:
*[[Exact cover]]
:<math>
*[[Dancing Links]]
\begin{bmatrix}
0 & 0 \\
0 & 0 \\
1 & 1
\end{bmatrix}
</math>
 
==References==
Each column has one or more 1s, so we continue.
{{Reflist}}
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.
*{{citation
Row 2 is selected as the first row with a 1 on column 0.
| first = Donald E. | last = Knuth | author-link = Donald Knuth
Column 0 is removed.
| contribution = Dancing links
Column 1 is removed.
| title = Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare
| year = 2000
| pages = 187–214
| publisher = Palgrave
| isbn = 978-0-333-92230-9
| editor1-first = Jim | editor1-last = Davies
| editor2-first = Bill | editor2-last = Roscoe
| editor3-first = Jim | editor3-last = Woodcock
| arxiv = cs/0011047 | bibcode = 2000cs.......11047K}}.
 
==External links==
The result is an empty matrix, so this is a solution. The elements represented by the selected rows are the solution set:
*[https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf Knuth's paper] - PDF file (also {{ArXiv|cs/0011047}})
:<math>
*[http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz Knuth's Paper describing the Dancing Links optimization] - Gzip'd postscript file.
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 1 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}
</math>
 
{{Donald Knuth navbox}}
[[Donald Knuth]] further suggested an implementation of this algorithm using circular [[doubly linked list]]s, and named this [[Dancing Links]], or DLX.
 
[[Category:Search algorithms]]
== References ==
* [http://www-cs-faculty.stanford.edu/~knuth/preprints.html Knuth's paper] (look for P159)
* [http://xxx.lanl.gov/PS_cache/cs/pdf/0011/0011047.pdf PDF version of Knuth's paper]
[[Category:Algorithms]]
[[Category:Donald Knuth]]
Retrieved from "https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X"