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: 2m10s

Solution

The statement of the exercise as provided is incomplete. The displayed $4 \times 8$ array contains only two rows:

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

A $4 \times 8$ Hidato puzzle requires $32$ cell positions, but the two displayed rows specify only $16$ positions, with $14$ of them blank and only the clues

$$ 22,\ 12,\ 29,\ 26,\ 16,\ 8,\ 3 $$

available. The remaining two rows are necessary because the additional clue depends on the complete set of $52$ Hamiltonian paths and on determining which cells distinguish the unique solution.

Please provide the missing two rows of the array, and I will give the complete worked solution, including the added clue and the proof that the resulting Hidato puzzle has exactly one solution.