Knuth's Algorithm X: Difference between revisions

Revision as of 22:36, 8 November 2010

Latest revision as of 06:55, 5 January 2025

(44 intermediate revisions by 32 users not shown)

Line 1:

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

[[Donald Knuth]]'s '''Algorithm X''' is a [[recursion (computer science)|recursive]], [[Nondeterministic_algorithm|nondeterministic]], [[depth-first]], [[backtracking]] [[algorithm]] that finds all solutions to the [[exact cover]] problem represented by a matrix ''A'' consisting of 0s and 1s. The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.

'''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 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''_{''r'', ''c''} = 1 ([[nondeterministic algorithm|nondeterministically]]).

Line 11 ⟶ 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 23 ⟶ 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 36 ⟶ 38:

This problem is represented by the matrix:

:{| class="wikitable"

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

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

|-

Line 66 ⟶ 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 98 ⟶ 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 120 ⟶ 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 144 ⟶ 146:

|}

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

::{| class="wikitable"

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

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

|-

Line 157 ⟶ 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 173 ⟶ 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 195 ⟶ 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 219 ⟶ 221:

|}

: 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 238 ⟶ 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 261 ⟶ 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 274 ⟶ 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 289 ⟶ 291:

|}

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

:::{| class="wikitable"

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

! !! 2 !! 7

|-

Line 300 ⟶ 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 312 ⟶ 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 319 ⟶ 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 355 ⟶ 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 ==

[[DancingKnuth's Links]],main commonlypurpose knownin asdescribing DLX,Algorithm isX thewas techniqueto suggesteddemonstrate bythe utility of [[Donalddancing Knuth|Knuthlinks]]. to efficientlyKnuth implementshowed histhat Algorithm X can be implemented efficiently on a computer. Dancingusing Linksdancing implementslinks in a process Knuth calls ''"DLX"''. DLX uses the matrix usingrepresentation circularof the [[doublyexact linkedcover]] list|problem, implemented as [[doubly- linked list]]s of the 1s inof the matrix. There is a list of 1s for: each row and each column. Each 1 in the matrixelement 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" />

== 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 372 ⟶ 388:

| pages = 187–214

| publisher = Palgrave

| isbn = 9780333922309978-0-333-92230-9

| editor1-first = Jim | editor1-last = Davies

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

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

| idarxiv = {{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}})

*[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}}

[[Category:Search algorithms]]