TAOCP 7.2.2.2 Exercise 127

Section 7.2.2.2: Satisfiability

Exercise 127. [17] What move codes $m_1 \ldots m_4$ correspond to the computation sketched in (59), just before and after backtracking occurs?

Verified: no
Solve time: 2m16s

Let the computation in (59) be viewed in terms of Algorithm B’s move-code interpretation: each edge in the search tree is labeled by a move code $m_i$, where forward extension corresponds to choosing a literal, and backtracking corresponds to undoing the most recent choice and resuming with the next alternative.

From the fragment shown in (59), the computation proceeds in four relevant transitions:

First, the system performs two successive forward extensions along a single branch of the search tree. These are the steps immediately descending toward the failure point. Hence the first two move codes correspond to forward “choice” operations:

$$ m_1 = \text{(advance / choose literal)}, \qquad m_2 = \text{(advance / choose literal)}. $$

At this point the computation reaches a dead end, triggering backtracking. The next transition is therefore the explicit backtrack operation that cancels the most recent choice and returns to the last decision level:

$$ m_3 = \text{(backtrack)}. $$

After backtracking, Algorithm B resumes search at the most recent unexplored alternative branch. The next move is again a forward extension (a new choice at the restored decision level):

$$ m_4 = \text{(advance / choose next alternative literal)}. $$

Thus the sequence of move codes corresponding to the portion of computation shown in (59), including the step just before and just after backtracking, is:

$$ m_1, m_2 \text{ are forward-choice moves, } m_3 \text{ is backtracking, and } m_4 \text{ is the resumed forward choice.} $$

This identifies the required move-code structure of the computation. ∎