TAOCP 7.2.2.1 Exercise 438
The corrected solution removes the invalid pruning argument and uses only a connectivity test that is guaranteed to be valid for partial assignments.
Section 7.2.2.1: Dancing Links
Exercise 438. [30] Explain how to modify Algorithm C so that, when given an XCC problem from the construction in answer 437, it will produce only solutions that satisfy also the connectivity condition (iii). Hint: See exercise 413; also consider reachability.
Verified: no
Solve time: 2m32s
The corrected solution removes the invalid pruning argument and uses only a connectivity test that is guaranteed to be valid for partial assignments. The safe modification is to test connectivity when a complete XCC solution has been found, with an optional pruning method based on reachability only when a future connection is impossible.
Edit
Let the XCC instance constructed in exercise 437 be the one whose solutions are precisely the weak solutions of the hitori puzzle. Thus every solution produced by Algorithm C already satisfies conditions (i) and (ii). It remains only to enforce condition (iii), namely that all white cells form one rookwise connected component.
A partial solution during Algorithm C does not determine the final set of white cells. Some cells are already forced black, some cells are already forced white, and some cells are still undecided. Consequently, connectivity cannot in general be tested on the currently known white cells. Two currently separated white regions may later become connected by undecided cells that remain white in a completed solution.
Therefore the modification must not reject a partial solution merely because the currently forced white cells are disconnected.
The simplest correct modification is the following. Leave the branching and covering operations of Algorithm C unchanged. When Algorithm C reaches a node at which all XCC items have been covered, it has found a weak solution. Before printing this solution, perform a rookwise reachability search on the complete set of white cells.
Choose any white cell (s). Starting from (s), mark every white cell that can be reached by repeated rook moves through white cells only. Let (R) be the set of reached cells, and let (W) be the complete set of white cells in the candidate solution. Output the solution if and only if
[ R=W . ]
If (R\ne W), discard this XCC solution and continue the backtracking search of Algorithm C.
This test is exactly the required condition (iii). If (R=W), every white cell is connected to (s), so all white cells belong to one rookwise connected component. If (R\ne W), there are white cells not reachable from (s), so the white cells have at least two components and condition (iii) fails.
The correctness follows directly from the correspondence established in exercise 437. Every solution accepted by the modified algorithm is first an XCC solution, and hence satisfies conditions (i) and (ii). The final reachability test then guarantees condition (iii). Therefore every reported solution is a valid hitori solution.
Conversely, suppose a hitori solution satisfies conditions (i), (ii), and (iii). By the construction of exercise 437, the same choice of black cells gives an XCC solution. Algorithm C will eventually reach this solution because no additional pruning rule removes it. At that point the complete white region is rookwise connected, so the reachability search reaches every white cell and the solution is output.
Thus the modified Algorithm C produces exactly the hitori solutions satisfying all three conditions.
The hint concerning reachability and exercise 413 suggests a possible optimization. One may add pruning during the search only when a reachability argument proves that the final white region can no longer become connected. For example, if the cells that are still allowed to be white cannot provide a rookwise path between two already separated required white regions, then the branch may safely be abandoned. However, a test based only on the current forced-white cells is not valid, because undecided cells may later remain white and connect those regions.
Hence the essential modification is the final reachability test on every completed XCC solution, with any additional pruning required to be based on a valid impossibility-of-future-connection argument.