TAOCP 7.2.2.1 Exercise 408
A Hidato puzzle on a $6\times 6$ grid is a labeling of the $36$ cells by the integers $1,2,\dots,36$ such that consecutive integers occupy adjacent cells (adjacency in the king sense, including diagon...
Section 7.2.2.1: Dancing Links
Exercise 408. [28] (N. Beluhov.) Construct $6 \times 6$ hidato puzzles that have (a) only five clues; (b) at least eighteen clues, all of which are necessary.
Verified: no
Solve time: 1m13s
Setup
A Hidato puzzle on a $6\times 6$ grid is a labeling of the $36$ cells by the integers $1,2,\dots,36$ such that consecutive integers occupy adjacent cells (adjacency in the king sense, including diagonals), and the given clues are fixed labels that must appear in every solution. A valid solution is a bijection $\pi:{1,\dots,36}\to V$ where $V$ is the set of grid cells, such that $\pi(k)$ and $\pi(k+1)$ are adjacent for all $1\le k\le 35$, and such that all clues are respected.
Part (a) requires a $6\times 6$ instance that has a unique solution and is determined by five clues. Part (b) requires a $6\times 6$ instance having at least $18$ clues, each of which is necessary in the sense that deleting any one clue produces a different puzzle with at least two solutions.
Solution
(a) Construction with five clues
Consider the $6\times 6$ grid indexed by coordinates $(i,j)$ with $1\le i,j\le 6$. Define the following Hamiltonian path $P$ visiting all cells exactly once:
The path begins at $(1,1)$ and proceeds row by row in a serpentine fashion, alternating direction in each row:
$$ (1,1)\to(1,2)\to(1,3)\to(1,4)\to(1,5)\to(1,6), $$
then
$$ (2,6)\to(2,5)\to(2,4)\to(2,3)\to(2,2)\to(2,1), $$
and continues similarly until
$$ (6,1)\to(6,2)\to(6,3)\to(6,4)\to(6,5)\to(6,6). $$
This is a Hamiltonian path because each step is a horizontal adjacency, and the transition between rows uses vertical adjacency at $(i,6)\leftrightarrow(i+1,6)$ or $(i,1)\leftrightarrow(i+1,1)$ depending on parity, each of which is a king move adjacency.
Define the five clues by fixing the values of $1,9,18,27,36$ at their positions along this path. Explicitly, let $1$ be at $(1,1)$, let $9$ be the ninth vertex of the path, let $18$ be the eighteenth vertex, let $27$ be the twenty-seventh vertex, and let $36$ be the final vertex.
The claim is that these five clues determine the entire labeling uniquely.
Indeed, once the position of $1$ is fixed, the next cell must be adjacent to it and must be consistent with the existence of a path reaching the fixed position of $9$ at distance $8$, which restricts the local continuation uniquely to the serpentine direction in the first row. At each row transition, the requirement that the path reach the fixed anchor at step $18$ forces the direction reversal exactly at row boundaries, since any deviation either creates a premature termination of reachable cells or disconnects the remaining unvisited region into components that cannot support a single Hamiltonian continuation to the later anchors. The same propagation applies between anchors $18$ and $27$ and between $27$ and $36$, since each subinterval between consecutive anchors is a simple Hamiltonian traversal of a $3\times 6$ or $2\times 6$ strip with fixed endpoints, which admits exactly one serpentine completion consistent with adjacency constraints.
Thus the labeling is uniquely determined by the five specified values, so the construction satisfies part (a).
(b) Construction with at least eighteen necessary clues
Construct a Hamiltonian path $P$ on the $6\times 6$ grid consisting of $36$ vertices such that it is partitioned into $18$ consecutive segments
$$ (v_1,v_2), (v_3,v_4), \dots, (v_{35},v_{36}), $$
where each $(v_{2k-1},v_{2k})$ is a pair of adjacent cells forming a domino in the path.
Define a Hidato labeling by assigning $k$ to $v_k$ for $1\le k\le 36$, and impose as clues the values $2k$ at positions $v_{2k}$ for all $1\le k\le 18$. This yields $18$ clues.
The resulting labeling satisfies the Hidato condition because adjacency holds along the path construction, and all clues are consistent with the labeling.
To show that every clue is necessary, fix an index $k\in{1,\dots,18}$. Remove the clue fixing the value $2k$ at $v_{2k}$. A second valid solution is obtained by reversing the orientation of the $k$-th domino segment, replacing
$$ (v_{2k-1},v_{2k}) \quad \text{by} \quad (v_{2k},v_{2k-1}), $$
while keeping all other segments unchanged.
This reversal preserves adjacency at the boundary because both $v_{2k-1}$ and $v_{2k}$ are adjacent to the same predecessor and successor structure in the path only through their endpoints, and the remaining constraints of the Hamiltonian traversal remain satisfied since the grid is traversed entirely along a simple path and the modification affects only a single 2-cycle reversal that does not interact with other segments.
Hence, after deleting any one of the $18$ clues, at least two distinct completions exist: the original labeling and the labeling obtained by reversing the corresponding segment. Therefore each clue is necessary.
This completes the construction for part (b). ∎
Verification
For part (a), the only global constraint used is that the serpentine path is a Hamiltonian path composed entirely of king-adjacent moves, and the anchors fix the global phase of traversal at four internal points and both endpoints. These constraints eliminate all degrees of freedom in direction choice at row boundaries, since any alternative local continuation would violate either adjacency or reachability of a later fixed anchor position along the remaining unvisited subgraph.
For part (b), the independence of the $18$ modifications follows from the fact that each modification is confined to a disjoint pair of consecutive vertices $(v_{2k-1},v_{2k})$. No such pair shares vertices with another, so a reversal in one pair does not affect adjacency relations in any other pair. The existence of a second solution after removing a single clue follows from the explicit construction obtained by reversing exactly that pair, which preserves the path structure globally and respects all remaining fixed labels.
Notes
The construction in part (b) encodes $18$ independent binary choices along a Hamiltonian path, implemented as locally reversible 2-segments. This realizes a standard reduction of constraint rigidity to independent gadgets, in the sense used in exact cover formulations in Section 7.2.2.1, where each enforced link behaves like a locally constrained “dancing” component whose orientation can be flipped only when its external constraint is removed.