TAOCP 7.2.2.1 Exercise 404
A hidato solution is a Hamiltonian path of king moves on the $m \times n$ board.
Section 7.2.2.1: Dancing Links
Exercise 404. ▶ [25] [25] (Hidato®.) A "hidato solution" is an $m \times n$ matrix whose entries are a permutation of ${1, 2, \ldots, mn}$ for which the cells containing $k$ and $k + 1$ are next to each other, either horizontally, vertically, or diagonally, for $1 \le k < mn$. (In other words, it specifies a Hamiltonian path of king moves on an $m \times n$ board.) A "hidato puzzle" is a subset of those numbers, which uniquely determines the others; the solver is expected to reconstruct the entire path from the given clues.
| 3 | 14 | 1 |
|---|---|---|
| 5 | 9 | |
| 8 |
(i)
| 3 | 14 | 1 |
|---|---|---|
| 4 | ||
| 5 | 9 | |
| 8 |
(ii)
| 3 | 14 | 1 |
|---|---|---|
| 4 | ||
| 6 | 8 |
(iii)
| 16 | 3 | 14 | 1 |
|---|---|---|---|
| 4 | |||
| 5 | 9 | 10 | 12 |
| 6 | 7 | 8 |
(iv)
For example, consider the $4 \times 4$ puzzle (i). There's only one place to put '2'. Then there are two choices for '4'; but one of them blocks the upper left corner (see (ii)), so we must choose the other. Similarly, '6' must not block any corner. Therefore (iii) is forced; and it's easy to fill in all of the remaining blanks, thereby obtaining solution (iv).
Explain how to encode such puzzles for solution by Algorithm C.
Verified: no
Solve time: 1m51s
Solution
A hidato solution is a Hamiltonian path of king moves on the $m \times n$ board. The exact cover formulation must choose, for every number $k$, exactly one location, and it must also choose compatible consecutive locations for every pair $(k,k+1)$.
Let the cells of the board be denoted by $s$, with $1 \le s \le mn$. Let $K(s)$ denote the set of cells that are king-adjacent to $s$. A possible placement of the number $k$ in cell $s$ is represented by the option
$$ (k,s). $$
The first class of items is the position requirement. For every $k$ with $1 \le k \le mn$, introduce an item
$$ P_k, $$
meaning that the number $k$ has been placed exactly once. The option $(k,s)$ contains the item $P_k$.
The clues are handled by restricting the available options. If the clue says that number $k$ occurs in cell $s$, all options $(k,t)$ with $t\ne s$ are omitted. Thus every exact cover solution automatically respects the given clues.
The adjacency requirement is encoded by introducing transition items. For every $k$ with
$$ 1\le k < mn $$
and every ordered pair of king-adjacent cells $(s,t)$, introduce an item
$$ T_{k,s,t}. $$
The intended meaning is that $k$ is in $s$ and $k+1$ is in $t$.
The option corresponding to placing $k$ in $s$ must now specify how the path leaves and enters that cell. For $1<k<mn$, an option is therefore indexed by a triple
$$ (s,t,u), $$
where
$$ t\in K(s),\qquad u\in K(s), $$
with the interpretation that $k$ is placed in $s$, $k-1$ is placed in $t$, and $k+1$ is placed in $u$. The corresponding exact cover option contains
$$ P_k,\quad T_{k-1,t,s},\quad T_{k,s,u}. $$
For the endpoint numbers, the definition is modified. For $k=1$, an option is indexed by an adjacent cell $u\in K(s)$ and contains
$$ P_1,\quad T_{1,s,u}. $$
For $k=mn$, an option is indexed by an adjacent cell $t\in K(s)$ and contains
$$ P_{mn},\quad T_{mn-1,t,s}. $$
The transition items force compatibility. If an option chooses $k$ at $s$ and $k+1$ at $t$, then the item $T_{k,s,t}$ is covered. Since every item must be covered exactly once, no second option may choose a different successor or predecessor for the same transition. Hence the selected options define a single sequence
$$ s_1,s_2,\ldots,s_{mn} $$
satisfying
$$ s_{k+1}\in K(s_k) $$
for every
$$ 1\le k<mn. $$
The position items $P_k$ force every number to occur exactly once, so the sequence contains all $mn$ cells. Therefore the selected options form a Hamiltonian path of king moves.
Conversely, suppose a hidato solution is given. Let $s_k$ be the cell containing $k$. For each $k$, choose the option determined by the cells $s_{k-1}$, $s_k$, and $s_{k+1}$, using the endpoint versions when $k=1$ or $k=mn$. The position item $P_k$ is covered once because each number appears once. The transition item $T_{k,s_k,s_{k+1}}$ is covered once because the path has exactly one successor relation between $k$ and $k+1$. No other transition item is selected. Thus the selected options form an exact cover.
Therefore the hidato puzzles and the exact covers constructed above are in one-to-one correspondence. Algorithm C can solve the puzzle by applying its exact cover search to this collection of options and items. The dancing-links representation from Section 7.2.2.1 may then be used directly, with each $1$ in the incidence matrix represented by a node in the sparse option-item structure.
This completes the encoding required for Algorithm C. ∎