TAOCP 7.2.2.1 Exercise 407

Section 7.2.2.1: Dancing Links

Exercise 407. ▶ [20] Here's a curious $4 \times 8$ array that is consistent with 52 hidato solutions:

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline & 22 & & & & & & 12 \ \hline & & 29 & 26 & 16 & 8 & 3 & \ \hline \end{array}$$

Change it to a valid hidato puzzle, by adding one more clue.

Verified: no
Solve time: 3m33s

---

The reviewer’s diagnosis is correct: the previous “solution” never engaged with the actual constraint graph of the full $4\times 8$ Hidato instance. The argument is not repairable locally, because the missing information is not a minor technicality but the defining structure of the puzzle.

1. Critical error: missing problem data

A Hidato instance is completely determined by:

• the full $4\times 8$ adjacency graph (king moves on all 32 cells),
• all pre-filled labels,
• and the set of allowed numbers $1,\dots,32$.

In the statement provided here, only two partial rows are visible:

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline & 22 & & & & & & 12 \ \hline & & 29 & 26 & 16 & 8 & 3 & \ \hline \end{array} $$

but the remaining two rows of the $4\times 8$ grid are completely absent.

Without those 16 cells, the king-adjacency graph is undefined, so:

• forced-move analysis is undefined,
• Hamiltonian path constraints are incomplete,
• and “uniqueness after adding a clue” is not a well-posed predicate.

Any proposed completion or uniqueness proof is therefore not mathematically grounded.

2. Consequence: no valid uniqueness argument can be constructed

The previous solution attempted to argue:

• propagation from a chosen starting cell,
• forced continuation along a “corridor”,
• global connectivity obstructions.

Each of these steps depends on knowing the full adjacency structure of all 32 vertices. Since half the vertices are not specified, none of the following can be determined:

• degrees of vertices in the king graph,
• bottlenecks or forced corridors,
• reachability of the fixed digits $22, 29, 26, 16, 8, 3, 12$,
• existence of alternative Hamiltonian extensions.

Thus the claimed “deterministic propagation” is not merely unproven; it is not even defined.

3. Critical error: no verification of existence or uniqueness

Even if one guessed a missing clue such as $(1,1)=1$, a correct solution would still require:

1. Existence: at least one full Hamiltonian labeling consistent with all clues.
2. Uniqueness: all other completions ruled out by structural argument or exhaustive constraint propagation.

Neither can be carried out without the missing two rows, because both depend on how paths enter and exit those unknown cells.

4. Fabricated structural claims

The earlier references to a “rigid corridor” formed by

$$ 29 \to 26 \to 16 \to 8 \to 3 $$

are unsupported. In a Hidato grid, such a sequence is not inherently rigid unless:

• the intermediate adjacency constraints force linearity, and
• alternative branches are eliminated by boundary structure.

Both require full knowledge of surrounding cells, which is absent.

5. Correct conclusion

Since the full $4\times 8$ grid is not provided, the exercise as stated here is incomplete. In particular:

• The set of admissible puzzles obtained by adding a single clue cannot be evaluated.
• No candidate clue can be verified for uniqueness.
• No Hamiltonian-path reasoning can be completed.

Final answer

The problem cannot be solved from the given information. The corrected resolution is that the instance is underspecified:

$$ \boxed{\text{The full } 4\times 8 \text{ grid is required to determine a valid additional clue.}} $$

Any claimed solution, including $(1,1)=1$, is unverified without the missing two rows of the puzzle definition.