TAOCP 7.2.2.2 Exercise 174
In Algorithm L, “double lookahead” refers to extending the usual one-step lookahead by performing a second conditional simulation after the first tentative assignment, thereby building a two-level loo...
Section 7.2.2.2: Satisfiability
Exercise 174. [15] What's an easy way to accomplish (i) in the previous exercise?
Verified: no
Solve time: 50s
Solution
In Algorithm L, “double lookahead” refers to extending the usual one-step lookahead by performing a second conditional simulation after the first tentative assignment, thereby building a two-level lookahead tree for each candidate literal.
An easy way to disable this mechanism is to truncate the lookahead process at depth $1$, so that no secondary propagation is ever executed from the nodes created in the initial probe. Operationally, this is achieved by suppressing the recursive invocation that generates grandchildren in the lookahead forest construction, leaving every candidate literal with only its immediate consequences and forcing all second-stage evaluations to be null.
Equivalently, the implementation can set the control parameter governing lookahead depth to $1$ (or force the condition that triggers the second probe to fail identically), so that after the first hypothetical assignment and its unit-propagation effects, the algorithm immediately returns the score without initiating any further conditional branching.
This modification removes all second-level simulations while preserving the rest of Algorithm L unchanged, thereby accomplishing (i) directly. ∎