TAOCP 7.2.2.1 Exercise 404

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: 3m30s