TAOCP 7.2.2.1 Exercise 29
In particular, the missing points that must be fixed in a genuine solution are: 1.
Section 7.2.2.1: Dancing Links
Exercise 29. [26] Let $T$ be any tree. Construct the 0–1 matrix of an unsolvable exact cover problem for which $T$ is the backtrack tree traversed by Algorithm X with the MRV heuristic. (The active list should have the minimum LB value whenever step X3 is encountered.) Illustrate your construction when $T = Q_8$.
Verified: no
Solve time: 2m47s
In particular, the missing points that must be fixed in a genuine solution are:
- The representation of vertices of $T$.
One must define exactly which recursive states of Algorithm X correspond to vertices of $T$. The previous answer implicitly identified vertices with “chosen primary columns,” but that identification is not valid without proving that the remaining matrix after every choice is a copy of the intended subtree. 2. The absence of extra unsuccessful branches.
A correct construction cannot add explicit “failure rows” at every vertex. Leaves must fail because the MRV-selected column has lower bound $0$, or an equivalent unavoidable contradiction, not because an artificial row creates an additional branch. 3. The MRV invariant.
The construction must specify every auxiliary column and every padding row explicitly, then prove that at every invocation of step X1 the intended column has the unique minimum active list size. Merely saying that padding columns can be added is insufficient. 4. The step X3 invariant.
The construction must prove that after choosing the option corresponding to a child $w$, all options outside $T_w$ disappear and all options inside $T_w$ remain. This is the central combinatorial property of the gadget. 5. The $Q_8$ illustration.
The notation $Q_8$ must be interpreted from the text of the section. It is not the ordinary $8\times8$ queen graph, and using that interpretation leads to a different object.
To produce the requested corrected textbook solution, I need the definitions immediately preceding Exercise 7.2.2.1.29 (especially the definition of the “backtrack tree” and the object denoted $Q_8$). With those definitions, the construction can be written rigorously and the MRV/LB invariant can be verified line by line.