TAOCP 7.2.2.2 Exercise 124

Section 7.2.2.2: Satisfiability

Exercise 124. ▶ [21] Spell out the low-level link field operations that are sketched in step B3.

Verified: no
Solve time: 3m22s

---

Let the structure be Knuth’s orthogonal doubly linked representation used for exact cover: each node $x$ has four link fields

$$ L[x],\ R[x],\ U[x],\ D[x], $$

and each row and column is a circular list with a distinguished header node. Let $C$ denote the header of the clause (row) to be deleted.

Step B3 removes every node in row $C$ from all column lists and from its own row, and finally unlinks the row header $C$.

Low-level specification of Step B3

We begin at the row header $C$. The key point is that traversal must not be destroyed by pointer updates, so the successor of each node is saved before any unlinking is performed.

Set

$$ x \leftarrow R[C]. $$

We iterate over all non-header nodes in the row until we return to $C$.

Loop invariant and traversal discipline

At every iteration, $x$ is a node in row $C$, with $x \neq C$. Before modifying any pointers of $x$, we store its horizontal successor:

$$ \text{next} \leftarrow R[x]. $$

This guarantees that the remaining portion of the row remains reachable after $x$ is excised.

Removal of a node $x$

For each node $x$ in the row (excluding the header), perform the following low-level pointer updates.

1. Unlink $x$ from its column (vertical removal)

Let $U[x]$ and $D[x]$ be the adjacent nodes in its column list. Execute:

$$ D[U[x]] \leftarrow D[x], \qquad U[D[x]] \leftarrow U[x]. $$

This removes $x$ from its column while preserving the vertical circular list.

2. Unlink $x$ from its row (horizontal removal)

Let $L[x]$ and $R[x]$ be its neighbors in row $C$. Execute:

$$ R[L[x]] \leftarrow R[x], \qquad L[R[x]] \leftarrow L[x]. $$

This removes $x$ from the row list.

Advancement of traversal

After unlinking $x$ in both directions, advance to the stored successor:

$$ x \leftarrow \text{next}. $$

This step is essential because $R[x]$ is no longer reliable after the horizontal deletion has modified the row structure.

Termination of the loop

The process continues until

$$ x = C, $$

meaning we have returned to the row header after traversing the entire original row cycle.

Final removal of the row header

After all non-header nodes have been deleted from their column lists and excised from the row, the row header $C$ is removed from the master list of active rows:

$$ R[L[C]] \leftarrow R[C], \qquad L[R[C]] \leftarrow L[C]. $$

Correctness and structural preservation

1. The stored variable $\text{next}$ ensures that row traversal remains well-defined despite destructive updates.
2. Every node $x \in C$, $x \neq C$, is removed from both its column and row exactly once.
3. The header $C$ is not touched until all incident nodes have been removed, ensuring safe access to the row structure throughout.
4. All remaining row and column lists preserve circular doubly linked consistency because every deletion uses symmetric pointer bypass operations.

Thus Step B3 is fully specified at the level of individual link-field assignments in a manner consistent with TAOCP’s pointer-machine conventions. ∎