Knuth's Algorithm X: Difference between revisions

Revision as of 12:48, 27 March 2015

Latest revision as of 06:55, 5 January 2025

(26 intermediate revisions by 20 users not shown)

Line 1:

{{Short description|Algorithm for exact cover problem}}

"Algorithm X" is the name [[Donald Knuth]] used in his paper "Dancing Links" to refer to "the most obvious trial-and-error approach" for finding all solutions to the [[exact cover]] problem.<ref name="knuth" /> Technically, Algorithm X is a [[Recursion (computer science)|recursive]], [[Nondeterministic algorithm|nondeterministic]], [[depth-first]], [[backtracking]] [[algorithm]]. While Algorithm X is generally useful as a succinct explanation of how the [[exact cover]] problem may be solved, Knuth's intent in presenting it was merely to demonstrate the utility of the [[dancing links]] technique via an efficient implementation he called DLX.<ref name="knuth">{{cite arxiv | author = [[Donald Knuth|Knuth, Donald]] | title = Dancing links | year = 2000 | eprint = cs/0011047 }}</ref>

'''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>

==Algorithm==

The [[exact cover]] problem is represented in Algorithm X usingby aan [[incidence matrix]] ''A'' consisting of 0s and 1s. The goal is to select a subset of the rows sosuch that the digit 1 appears in each column exactly once.

Algorithm X functionsworks as follows:

:{| border="1" cellpadding="5" cellspacing="0"

|

# If the matrix ''A'' has no columns, the current partial solution is a valid solution; terminate successfully.

# Otherwise choose a column ''c'' ([[deterministic algorithm|deterministically]]).

Line 13:

# For each column ''j'' such that ''A''_{''r'', ''j''} = 1,

#: for each row ''i'' such that ''A''_{''i'', ''j''} = 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 essentiallyrecurses clones itself intoover 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 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 specified by the universe ''U'' = {1, 2, 3, 4, 5, 6, 7} and the collection of sets <math>\mathcal{{mathcal|S}</math>} = {''A'', ''B'', ''C'', ''D'', ''E'', ''F''}, where:

:* ''A'' = {1, 4, 7};

:* ''B'' = {1, 4};

Line 38:

This problem is represented by the matrix:

:{| class="wikitable"

:{| border="1" cellpadding="5" cellspacing="0"

! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7

|-

Line 68:

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"

:{| border="1" cellpadding="5" cellspacing="0"

! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7

|-

Line 100:

: Step 5—Row ''A'' has a 1 in columns 1, 4, and 7:

::{| class="wikitable"

::{| border="1" cellpadding="5" cellspacing="0"

! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! <span style="color:blue">7</span>

|-

Line 122:

|}

: 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"

::{| border="1" cellpadding="5" cellspacing="0"

! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! <span style="color:red">7</span>

|-

Line 148:

: Row ''D'' remains and columns 2, 3, 5, and 6 remain:

::{| class="wikitable"

::{| border="1" cellpadding="5" cellspacing="0"

! !! 2 !! 3 !! 5 !! 6

|-

Line 159:

: Step 2—The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s:

::{| class="wikitable"

::{| border="1" cellpadding="5" cellspacing="0"

! !! <span style="color:red">2</span> !! 3 !! 5 !! 6

|-

Line 175:

: Row ''B'' has a 1 in columns 1 and 4:

::{| class="wikitable"

::{| border="1" cellpadding="5" cellspacing="0"

! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! 7

|-

Line 197:

|}

: 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"

::{| border="1" cellpadding="5" cellspacing="0"

! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! 7

|-

Line 223:

: Rows ''D'', ''E'', and ''F'' remain and columns 2, 3, 5, 6, and 7 remain:

::{| class="wikitable"

::{| border="1" cellpadding="5" cellspacing="0"

! !! 2 !! 3 !! 5 !! 6 !! 7

|-

Line 240:

: 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"

::{| border="1" cellpadding="5" cellspacing="0"

! !! 2 !! 3 !! <span style="color:red">5</span> !! 6 !! 7

|-

Line 263:

:: Step 5—Row ''D'' has a 1 in columns 3, 5, and 6:

:::{| class="wikitable"

:::{| border="1" cellpadding="5" cellspacing="0"

! !! 2 !! <span style="color:blue">3</span> !! <span style="color:blue">5</span> !! <span style="color:blue">6</span> !! 7

|-

Line 276:

|}

:: 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"

:::{| border="1" cellpadding="5" cellspacing="0"

! !! 2 !! <span style="color:red">3</span> !! <span style="color:red">5</span> !! <span style="color:red">6</span> !! 7

|-

Line 293:

:: Row ''F'' remains and columns 2 and 7 remain:

:::{| class="wikitable"

:::{| border="1" cellpadding="5" cellspacing="0"

! !! 2 !! 7

|-

Line 302:

:: 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).

Line 314 ⟶ 321:

::: Row ''F'' has a 1 in columns 2 and 7:

::::{| borderclass="1" cellpadding="5" cellspacing="0wikitable"

! !! <span style="color:blue">2</span> !! <span style="color:blue">7</span>

|-

Line 321 ⟶ 328:

|}

::: 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:

::::{| borderclass="1" cellpadding="5" cellspacing="0wikitable"

! !! <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'' arehave been selected (step 4), the final solution in this branch is:

::::{| borderclass="1" cellpadding="5" cellspacing="0wikitable"

! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7

|-

Line 357 ⟶ 370:

There are no branches at level 0, thus the algorithm terminates.

In summary, the algorithm determines there is only one exact cover: <math>\mathcal{{mathcal|S}^}{{sup|*</math>}} = {''B'', ''D'', ''F''}.

== Implementations ==

[[Donald Knuth]]'s main purpose in describing Algorithm X was to demonstrate the utility of [[Dancingdancing Linkslinks]]. Knuth showed that Algorithm X can be implemented efficiently on a computer using [[Dancingdancing Links]]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 [[Dancingdancing Links]]links to quickly select permutations of rows as possible solutions and to efficiently backtrack (undo) mistaken guesses.<ref name="knuth" />

== See also ==

* [[Exact cover]]

* [[Dancing Links]]

== References ==

{{Reflist}}

*{{citation

| first = Donald E. | last = Knuth | authorlinkauthor-link = Donald Knuth

| contribution = Dancing links

| title = Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare

Line 378 ⟶ 392:

| editor2-first = Bill | editor2-last = Roscoe

| editor3-first = Jim | editor3-last = Woodcock

| arxiv = cs/0011047 | bibcode = 2000cs.......11047K}}.

==External links==

*[https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf Knuth's paper] - PDF file (also {{ArXiv|cs/0011047}})

* [https://github.com/blynn/dlx Free Software implementation of Algorithm X in C] - uses the Dancing Links optimization. Includes examples for using the library to solve sudoku and logic grid puzzles.

* [http://github.com/mlepage/polycube-solver Polycube solver] Program (with Lua source code) to fill boxes with polycubes using [[Algorithm X]].

*[http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz Knuth's Paper describing the Dancing Links optimization] - Gzip'd postscript file.

{{Donald Knuth navbox}}