Knuth's Algorithm X: Difference between revisions

Revision as of 18:26, 10 January 2022

Latest revision as of 06:55, 5 January 2025

(10 intermediate revisions by 7 users not shown)

Line 1:

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

'''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 by aan [[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 functionsworks as follows:

{{quote frame|quote=

# 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 15 ⟶ 16:

#: delete column ''j'' from matrix ''A''.

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

Line 27 ⟶ 28:

==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 37 ⟶ 38:

This problem is represented by the matrix:

:{| class="wikitable"

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

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

|-

Line 67 ⟶ 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 99 ⟶ 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 123 ⟶ 124:

: 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 147 ⟶ 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 158 ⟶ 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 174 ⟶ 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 198 ⟶ 199:

: 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 222 ⟶ 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 239 ⟶ 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 262 ⟶ 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 277 ⟶ 278:

:: 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 292 ⟶ 293:

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

:::{| class="wikitable"

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

! !! 2 !! 7

|-

Line 301 ⟶ 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 313 ⟶ 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 322 ⟶ 330:

::: 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 356 ⟶ 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 [[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" />

==See also==