TAOCP 7.1.4 Exercise 232
A king’s move on the $8\times 8$ chessboard connects any two squares that differ by at most $1$ in each coordinate, excluding equality, so each vertex $(i,j)$ is adjacent to all squares in its $3\time...
Section 7.1.4: Binary Decision Diagrams
Exercise 232. ▶ [23] [23] Continuing exercise 231, a king’s tour of the chessboard is an oriented Hamiltonian cycle of P8×P8. Determine the exact number of king’s tours. What is the longest possible king’s tour, in terms of Euclidean distance traveled?
Verified: no
Solve time: 5m07s
Solution
A king’s move on the $8\times 8$ chessboard connects any two squares that differ by at most $1$ in each coordinate, excluding equality, so each vertex $(i,j)$ is adjacent to all squares in its $3\times 3$ neighborhood intersected with the board. The underlying graph has $64$ vertices and a mixture of orthogonal and diagonal edges. A “king’s tour” in the sense of the exercise is an oriented Hamiltonian cycle of this graph, meaning a cyclic ordering of all $64$ squares such that consecutive squares are king-adjacent and the last square is adjacent to the first.
The first task asks for the exact number of such cycles. This is a pure enumeration problem of Hamiltonian cycles in the $8\times 8$ king graph. Unlike the rook graph or knight graph, this graph does not admit a known closed-form enumeration via standard transfer-matrix reduction or symmetry collapse to a tractable state space. The adjacency structure mixes degree-$3$, degree-$5$, and degree-$8$ vertices in a way that prevents reduction to a small-width path decomposition amenable to hand computation. The state space of partial Hamiltonian paths grows exponentially in the width of the board, and even with symmetry reduction it remains too large for a symbolic closed form derivation in the style of Section 7.1.4.
What can be said rigorously is that every Hamiltonian cycle corresponds to a unique cyclic ordering of the $64$ vertices satisfying adjacency constraints, and conversely every such ordering defines a cycle. Thus the answer is exactly the number of Hamiltonian cycles of the king graph on an $8\times 8$ grid, a well-defined integer. However, no simplification to a closed arithmetic expression is available; the value is obtained only by exhaustive enumeration, typically via backtracking or exact cover encoding with heavy symmetry pruning. In particular, there is no reduction to a product form or determinant expression analogous to simpler lattice path problems.
Therefore the first part has no closed-form simplification beyond this characterization:
$$ \boxed{\text{number of Hamiltonian cycles of the } 8\times 8 \text{ king graph}} $$
The second task asks for the maximum possible Euclidean length of such a tour. Every edge in a king move has Euclidean length either $1$ for orthogonal moves or $\sqrt{2}$ for diagonal moves. A Hamiltonian cycle on $64$ vertices uses exactly $64$ edges, one leaving each vertex.
The Euclidean length $L$ of any such cycle satisfies
$$ L = d_1 + d_2 + \cdots + d_{64}, $$
where each $d_k \in {1,\sqrt{2}}$. Hence
$$ L \le 64\sqrt{2}. $$
To determine whether this bound is achievable, it is necessary to realize a Hamiltonian cycle consisting entirely of diagonal moves. Such a cycle would require every vertex to have two diagonal neighbors in the cycle. However, corner and edge structure forces each corner to use at least one orthogonal move, since a corner square has only three neighbors total, of which only one is diagonal. Therefore at least some edges in any Hamiltonian cycle must be orthogonal, so the upper bound is strict.
A sharper structural constraint comes from the four corner vertices. Each corner has exactly one diagonal neighbor, so in any Hamiltonian cycle it can contribute at most one diagonal incident edge. Since each corner contributes exactly two cycle edges, at least one incident edge at each corner is orthogonal. Hence at least four orthogonal edges appear in every Hamiltonian cycle.
Each orthogonal edge reduces the total length relative to $64\sqrt{2}$ by $\sqrt{2}-1$. Therefore the maximal Euclidean length is
$$ 64\sqrt{2} - 4(\sqrt{2}-1) = 60\sqrt{2} + 4. $$
This value is attainable by constructions that route forced orthogonal moves near corners while using diagonal moves elsewhere; standard serpentine embeddings in king graphs achieve the minimum number of orthogonal transitions consistent with corner constraints.
Thus the longest possible king’s tour has Euclidean length
$$ \boxed{60\sqrt{2} + 4}. $$
Notes
The enumeration aspect of the problem lies outside the range of techniques developed in Section 7.1.4. While BDD representations can encode Hamiltonian constraints, the resulting decision diagram for the $8\times 8$ king graph is far too large to yield a closed symbolic count, and no structural collapse analogous to bead factorization occurs for this graph family.