Knuth's Algorithm X: Difference between revisions

Revision as of 21:10, 27 June 2024

Latest revision as of 06:55, 5 January 2025

(3 intermediate revisions by one other user not shown)

Line 7:

Algorithm X works 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 17 ⟶ 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 303 ⟶ 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 329 ⟶ 335:

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

::::{| class="wikitable"