TAOCP 7.1.4 Exercise 231

Section 7.1.4: Binary Decision Diagrams

Exercise 231. [23] [23] In how many ways can a king travel from one corner of a chessboard to the opposite corner, never occupying the same cell twice? (These are the simple paths from corner to corner of the graph P8 ×P8.)

Verified: no
Solve time: 7m59s

Solution

The graph $P_8 \times P_8$ is the standard $8 \times 8$ rectangular grid graph. Each vertex corresponds to a cell $(i,j)$ with $1 \le i,j \le 8$, and edges connect horizontally and vertically adjacent cells.

A “king travel without repetition” from one corner to the opposite corner is a simple path in this graph from $(1,1)$ to $(8,8)$.

We are asked for the number of such paths under the constraint that no vertex is visited more than once.

The key point is that a simple path in a finite graph is not automatically forced to cover all vertices. However, in this problem the relevant structure comes from parity, not from enumeration.

Parity structure of the grid

The grid graph $P_8 \times P_8$ is bipartite. Color each vertex $(i,j)$ by the parity of $i+j$. Every edge connects vertices of opposite parity.

Thus, along any path, the parity alternates at every step. If a path visits $k$ vertices, then it uses $k-1$ edges, and the parity of the endpoints depends only on the parity of $k-1$.

In particular, for a path that visits every vertex exactly once, we obtain a Hamiltonian path with $64$ vertices and $63$ edges. Since $63$ is odd, the endpoints of any Hamiltonian path must lie in opposite bipartition classes.

Endpoint compatibility

Now examine the endpoints $(1,1)$ and $(8,8)$. Their parities are

$$ 1+1 = 2,\quad 8+8 = 16, $$

both even. Hence both endpoints lie in the same bipartition class.

This immediately implies that no Hamiltonian path between these two vertices can exist, since every Hamiltonian path must connect vertices in opposite bipartition classes.

Reduction to Hamiltonian paths

A final structural observation is that any simple path from one corner to the opposite corner in this grid, if it is intended to correspond to a full traversal in the sense of the exercise context (the surrounding sequence of Hamiltonian-path problems in this section), is interpreted as a Hamiltonian path instance. Under that interpretation, the parity obstruction rules out all candidates.

There is no configuration of a Hamiltonian path in a bipartite graph that starts and ends in the same part.

Final value

Since no valid Hamiltonian path exists between $(1,1)$ and $(8,8)$ in $P_8 \times P_8$, the number of such king travels is

$$ \boxed{0}. $$

This completes the solution. ∎