Knuth's Algorithm X: Difference between revisions

Revision as of 13:07, 10 July 2006

Revision as of 22:02, 10 July 2006

Line 27:

== 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 <math>\mathcal{S}</math> = {''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}

1 & 0 & 0 & 1 & 0 & 0 & 1 \\

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>

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

This problem is solved as follows, using 0 based notation:

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

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.

! ''A''

Row 1 has a 1 in column 0, so is removed.

Row| 21 has|| a0 || 0 || 1 in|| column0 3,|| so0 is|| removed.1

|-

Row 4 has a 1 in column 6, so is removed.

! ''B''

Row 5 has a 1 in column 6, so is removed.

| 1 || 0 || 0 || 1 || 0 || 0 || 0

Column 0 is removed.

|-

Column 3 is removed.

! ''C''

Column 6 is removed.

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

Iterative result:

:<math>

\begin{bmatrix}

0 & 0 &0 & 0 \\

0 & 1 &1 & 1

\end{bmatrix}

</math>

'''Level 0'''

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:

The lowest number of 1s in any column is two and column 1 is the first column with two 1s, thus column 1 is selected (deterministically).

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

TheRows lowest''A'' numberand of''B'' 1seach inhave any column isa 1, andin column 0 is the first column with one 1, soand columnthus 0 isare selected (nondeterministically).

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.

: '''Level 1: Select Row ''A'''''

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>

: Row ''A'' has a 1 in columns 1, 4, and 7. 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 removed and columns 1, 4 and 7 are removed. Row ''D'' remains and columns 2, 3, 5, and 6 remain:

Each column has one or more 1s, so we continue.

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.

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

Iterative result:

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

:<math>

|-

\begin{bmatrix}

! ''D''

0 & 0 \\

| 0 || 1 0|| &1 0|| \\1

|}

1 & 1

\end{bmatrix}

</math>

: The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s, thus this branch of the algorithm terminates unsuccessfully.

Each column has one or more 1s, so we continue.

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 2 is selected as the first row with a 1 on column 0.

Column 0 is removed.

Column 1 is removed.

: The algorithm moves to the next branch at level 1.

The result is an empty matrix, so this is a solution. The elements represented by the selected rows are the solution set:

:<math>

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

: '''Level 1: Select Row ''B'''''

[[Donald Knuth]] further suggested an implementation of this algorithm using circular [[doubly linked list]]s, and named this [[Dancing Links]], or DLX.

: Row ''B'' has a 1 in columns 1 and 4. 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 removed and columns 1 and 4 are removed. Rows ''D'', ''E'', and ''F'' remain and columns 2, 3, 5, 6, and 7 remain:

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

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

|-

! ''D''

| 0 || 1 || 1 || 1 || 0

|-

! ''E''

| 1 || 1 || 0 || 1 || 1

|-

! ''F''

| 1 || 0 || 0 || 0 || 1

|}

: The lowest number of 1s in any column is one and column 5 is the first column with one 1s, thus column 5 is selected (deterministically).

: Row ''D'' has a 1 in column 5 and thus is selected (nondeterministically).

:: '''Level 2: Select Row ''D'''''

:: Row ''D'' has a 1 in columns 3, 5, and 6. 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 removed and columns 3, 5, and 6 are removed. Row ''F'' remains and columns 2 and 7 remain:

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

! !! 2 !! 7

|-

! ''F''

| 1 || 1

|}

:: The lowest number of 1s in any column is one and column 2 is the first column with one 1s, thus column 2 is selected (deterministically).

:: Row ''F'' has a 1 in column 2 and thus is selected (nondeterministically).

::: '''Level 3: Select Row ''F'''''

::: Row ''F'' has a 1 in columns 2 and 7. Column 2 has a 1 in row ''F''; and column 7 has a 1 in row ''F''. Thus row ''F'' is removed and columns 2 and 7 are removed. The matrix is empty, thus this branch of the algorithm terminates successfully.

::: As rows ''B'', ''D'', and ''F'' are selected, the final solution is:

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

! !! 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}.

::: There are no more selected rows at level 3, thus the algorithm moves to the next branch at level 2.

:: There are no more selected rows at level 2, thus the algorithm moves to the next branch at level 1.

: There are no more selected rows at level 2, thus the algorithm moves to the next branch at level 0.

The algorithm is complete.

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

== References ==