TAOCP 7.2.2.1 Exercise 84

We restart the argument in a way that separates _finding the optimal bound_ from _enumerating all optimal solutions_, because mixing both in a single changing-bound traversal is what caused the failur...

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 84. ▶ [25] [25] Number the options of an XCC problem from 1 to $M$. A minimax solution is one whose maximum option number is as small as possible. Explain how to modify Algorithm C so that it determines all of the minimax solutions (omitting any that are known to be worse than a solution already found).

Verified: yes
Solve time: 2m21s

We restart the argument in a way that separates finding the optimal bound from enumerating all optimal solutions, because mixing both in a single changing-bound traversal is what caused the failure.

Correct modification of Algorithm C

Let each option $O_j$ have index $j \in {1,\dots,M}$. For a partial solution $S$, define

$$ m(S) = \max{ j : O_j \in S }, $$

with $m(\varnothing)=0$.

A minimax solution is an exact cover $S$ minimizing $m(S)$ over all exact covers.

Phase 1: compute the optimal bound $B^*$

We first modify Algorithm C only to search for exact covers while maintaining the best maximum index found, but without any attempt to enumerate solutions.

Maintain a global variable

$$ B \leftarrow M+1. $$

During the search, whenever a solution $S$ is found, update

$$ B \leftarrow \min(B, m(S)). $$

During branching, when trying option $O_j$, prune only if

$$ \max(m(S), j) > B. $$

Crucially, equality is allowed. This ensures that solutions achieving the current best bound are not excluded from consideration, so the final value of $B$ upon termination is indeed

$$ B = B^*. $$

No solutions are output in this phase. Its sole purpose is to compute the optimal value $B^*$.

Phase 2: enumerate all minimax solutions

We rerun Algorithm C with $B$ now fixed to the optimal value $B^*$.

The state variable $m(S)$ is again maintained as before.

Pruning rule

When considering an option $O_j$, prune a branch if

$$ \max(m(S), j) > B^*. $$

This is the correct branch-and-bound condition: any partial solution whose maximum already exceeds the proven optimum cannot lead to a minimax solution.

Output rule

When a complete exact cover $S$ is found, output it iff

$$ m(S) = B^*. $$

No solution is ever output before the bound is fixed, so there is no risk of later invalidation.

Why this is correct

1. Phase 1 computes $B^*$ correctly

The search explores all exact covers that are not already impossible under the current best bound. Because pruning only occurs when $\max(m(S),j) > B$, any solution with maximum exactly equal to the eventual optimum is never excluded during the phase in which it is discovered. Therefore the minimum achievable maximum is eventually recorded in $B$, so at termination

$$ B = B^*. $$

2. Phase 2 enumerates exactly the minimax solutions

Fix $B^*$. Any solution $S$ with $m(S) > B^*$ is pruned as soon as it becomes impossible to stay within the bound, so it is never generated.

Any solution with $m(S) = B^*$ is never pruned and is output at completion.

Any solution with $m(S) < B^*$ cannot exist by definition of $B^*$.

Hence the algorithm outputs exactly all minimax solutions.

3. No dependence on a changing bound during output

The key defect in the original solution was coupling output to a mutable $B$. Here, output occurs only after $B^*$ is fixed, so there is no inconsistency or need for retraction.

Relation to Algorithm C

The modification is minimal in structure:

  • Add variable $m(S)$ propagated along recursion.

  • Add a branch-and-bound test using a global bound $B$.

  • Run Algorithm C twice:

  • once to compute $B^*$,

  • once to enumerate all solutions satisfying the optimal bound.

Cover and uncover operations of Algorithm C remain unchanged.

This yields a correct minimax version of Algorithm C that enumerates all and only solutions with minimal possible maximum option index.