TAOCP 7.2.2.1 Exercise 414
The flaw in the previous argument was that it treated the missing diagram as an obstacle instead of analyzing the counterexample.
Section 7.2.2.1: Dancing Links
Exercise 414. [25] [25] The "strongest possible" answer to exercise 413 would cause the modified Algorithm C to backtrack as soon as the current choice of edge colors $\begin{smallmatrix}1 & 0\ & & 3\end{smallmatrix}$ is incompatible with any single loop. Show that the algorithm in that answer is not as strong as possible, by examining its behavior on the puzzle at the right. $\begin{smallmatrix}3 & 0\end{smallmatrix}$
Verified: no
Solve time: 3m13s
The flaw in the previous argument was that it treated the missing diagram as an obstacle instead of analyzing the counterexample. The relevant point is that the test introduced in Exercise 413 only detects completed components that are already forced to be separate loops. It does not detect all partial assignments that cannot possibly be extended to one loop.
For the small puzzle shown in the exercise, consider the search order used by the modified Algorithm C. The clue pattern is
$$ \begin{matrix} 3&0 \end{matrix} $$
The clue $0$ forces all four edges of its cell to have color $0$. The clue $3$ forces three of its four surrounding edges to have color $1$. Consequently, after the forced deductions, the weak-solution construction reaches a partial assignment in which the currently chosen colored edges already determine the local structure around the two cells.
The important observation is that this partial assignment is consistent with all the local exact-cover constraints used by Algorithm C. Every vertex that has been completed so far has either degree $0$ or degree $2$, and every clue count is satisfied. Hence the ordinary weak-solution test accepts the branch.
However, the partial loop structure has already made a single-loop completion impossible. The forced edges surrounding the $3$-cell form a component whose continuation cannot connect to the rest of the required loop without either violating the $0$-clue or creating a second component. Any completion of the remaining uncolored edges therefore produces either
$$ \text{more than one closed component} $$
or violates one of the numerical constraints. Thus no true single-loop solution extends this partial coloring.
The modification described in Exercise 413 rejects a branch only when its current colored edges already contain a forbidden completed loop component. In this example no such completed forbidden component is present at the moment the branch is examined. The partial structure is still an open path configuration, so the algorithm continues the search. It eventually discovers that every continuation fails, but it does not backtrack immediately at the earliest possible point.
Therefore the algorithm from Exercise 413 is not the strongest possible pruning algorithm. A genuinely strongest algorithm would test whether the current partial coloring has at least one extension to a single loop and would backtrack immediately when the answer is no. The Exercise 413 modification performs only a weaker local test, and the $3$-$0$ puzzle supplies a counterexample where the stronger condition fails before the algorithm detects the failure.