TAOCP 7.2.2.1 Exercise 84

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: no
Solve time: 1m25s

Solution

Algorithm C can be modified by adding a bound on the largest option number that is permitted in a partial solution. Let $B$ denote the smallest maximum option number among complete solutions found so far. Initially set $B \leftarrow M+1$, because no solution has yet been found.

Whenever Algorithm C chooses an option numbered $r$, the current partial solution can be extended only to solutions whose maximum option number is at least $r$. Hence a branch containing such an option cannot produce a minimax solution if $r>B$. Such a branch is omitted immediately.

The recursive search is changed as follows. Before the recursive call that follows the choice of an option $O$, let $r$ be the number of $O$. If $r>B$, do not make the recursive call. Otherwise perform the usual covering operations of Algorithm C and continue the search. When the search reaches a successful termination, let $r$ be the largest option number occurring in the current solution. If $r<B$, erase all previously recorded solutions, set $B\leftarrow r$, and record the current solution. If $r=B$, record the current solution together with the previously recorded ones. If $r>B$, discard the current solution.

The modification can be incorporated into Algorithm C by keeping one additional variable $B$ and one list of solutions. The variable $B$ is updated only at successful leaves of the search tree, and the test $r>B$ is made before descending from a node of the tree.

To prove correctness, first consider any solution returned by the modified algorithm. A returned solution is recorded only when its maximum option number is equal to the current value of $B$. Suppose that a later solution with a smaller maximum option number existed. When the branch leading to that solution was reached, every option in the partial solution would have number at most that smaller maximum. The search test would not have removed that branch, because its option numbers would all have been less than the then current value of $B$. The branch would eventually reach a successful leaf and replace $B$ by the smaller value. Thus the earlier returned solution could not remain in the final output. Therefore every final returned solution has minimum possible maximum option number.

Conversely, let $S$ be a minimax solution, and let its maximum option number be $b$. Every option selected while constructing $S$ has number at most $b$. During the search, a branch leading to $S$ can be discarded only after selecting an option numbered greater than the current value of $B$. Before the first solution with maximum option number at most $b$ is found, $B$ is greater than $b$, so no option in $S$ can cause the branch to be discarded. The branch corresponding to $S$ is therefore reached. When it reaches a successful leaf, its maximum option number is $b$, so it is recorded unless a solution with a smaller maximum has already been found. If such a smaller solution had already been found, the existence of a smaller maximum would contradict the assumption that $S$ is minimax. Hence $S$ is recorded in the final output.

The pruning condition is also sufficient to omit all known worse solutions. If a partial solution already contains an option numbered $r>B$, every completion has maximum option number at least $r$, which is larger than a previously found complete solution's maximum. Such a completion cannot be minimax and may be omitted.

This modification preserves the behavior of Algorithm C on every branch that can still contain a minimax solution, while eliminating every branch whose maximum option number is already known to be too large. Therefore it determines all minimax solutions and omits every solution known to be worse than one already found.

This completes the proof. ∎