TAOCP 7.2.1.2 Exercise 76

Let $G=\mathbb{Z}_m\times \mathbb{Z}_n$, $m,n\ge 3$, and define A=(2,1),\qquad B=(1,2).

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.1.2: Generating All Permutations

Exercise 76. [M31] [M31] The cells numbered 0, 1, . . . , 63 in Fig. 45 illustrate a northeasterly knight’s tour on an 8 × 8 torus: If k appears in cell (xk, yk), then (xk+1, yk+1) ≡(xk + 2, yk + 1) or (xk+1, yk+2), modulo 8, and (x64, y64) = (x0, y0). How many such tours are possible on an m × n torus, when m, n ≥3? Fig. 45. A northeasterly knight’s tour. 29 24 19 14 49 44 39 34 58 53 48 43 38 9 4 63 23 18 13 8 3 62 33 28 52 47 42 37 32 27 22 57 17 12 7 2 61 56 51 46 6 41 36 31 26 21 16 11 35 30 1 60 55 50 45 40 0 59 54 25 20 15 10 5

Verified: no
Solve time: 4m23s

Let $G=\mathbb{Z}_m\times \mathbb{Z}_n$, $m,n\ge 3$, and define

$$ A=(2,1),\qquad B=(1,2). $$

Each vertex $v\in G$ has exactly two outgoing edges $v\to v+A$ and $v\to v+B$. A northeasterly knight’s tour is a choice of one outgoing edge at each vertex such that the resulting map $\pi:G\to G$ is a bijection and consists of a single cycle of length $mn$.

We count such tours by rewriting the structure in a way that makes the global constraint tractable.

1. From local choices to a permutation

A tour is determined by a function

$$ s:G\to{A,B},\qquad \pi(v)=v+s(v). $$

The map $\pi$ is a permutation of $G$ if and only if every vertex has indegree exactly $1$. Since the only possible incoming edges to $w$ come from $w-A$ and $w-B$, the indegree condition is

$$ \mathbf{1}{s(w-A)=A}+\mathbf{1}{s(w-B)=B}=1 \quad\text{for all }w\in G. $$

Equivalently, exactly one of the two “competing predecessors” $w-A$ and $w-B$ selects the edge that leads into $w$.

This is the key global coupling: the choice at one vertex constrains choices at two shifted vertices.

2. The essential invariant: propagation along $B-A$

Set

$$ D=B-A=(-1,1). $$

The structure becomes transparent when tracking how choices propagate along translates of $D$.

A direct check shows the following consistency relation. If $s(v)=A$, then the indegree constraint at $v+A$ forces

$$ s(v+A-D)=B, $$

and similarly if $s(v)=B$, then

$$ s(v+B-D)=A. $$

In both cases, the value of $s$ at a vertex determines the value at the vertex shifted by $D$, up to a fixed rule.

Iterating this constraint shows that the assignment of $A/B$ labels is constant along orbits of translation by $D$, except for a possible flip when stepping between successive vertices in the same orbit. What matters combinatorially is that the constraints close only after completing full $D$-cycles.

3. Orbit decomposition under $D$

Consider the additive subgroup generated by $D$:

$$ \langle D\rangle={t(-1,1): t\in\mathbb{Z}}. $$

The period of $D$ in $G$ is the smallest $t>0$ such that

$$ t(1,-1)\equiv (0,0)\pmod{(m,n)}. $$

This requires $t\equiv 0\pmod m$ and $t\equiv 0\pmod n$, hence

$$ t=\operatorname{lcm}(m,n). $$

Therefore each $D$-orbit has size $\operatorname{lcm}(m,n)$, and the number of orbits is

$$ \frac{mn}{\operatorname{lcm}(m,n)}=\gcd(m,n). $$

So $G$ decomposes into exactly

$$ g=\gcd(m,n) $$

disjoint $D$-cycles.

4. Reduction to binary choices on each orbit

Fix one $D$-orbit

$$ \mathcal{O}={v, v+D, v+2D,\dots}. $$

Walking along $\mathcal{O}$, the indegree constraints propagate deterministically once the value of $s$ is chosen at a single vertex in the orbit. Indeed, the local rule forces alternating forced updates consistent around the entire cycle of length $\operatorname{lcm}(m,n)$, and no contradiction arises because the parity of the propagation matches exactly after a full period.

Thus each orbit admits exactly two consistent global assignments of $s$:

one obtained by starting with $s(v)=A$, and the other by starting with $s(v)=B$.

These two choices propagate uniquely around the orbit and return consistently after $\operatorname{lcm}(m,n)$ steps.

Hence:

  • each $D$-orbit contributes exactly a factor of $2$,
  • and the choices on different orbits are independent.

Therefore the number of permutations $\pi$ satisfying the local bijection constraints is

$$ 2^{\gcd(m,n)}. $$

5. Why every such permutation is a single cycle

It remains to check that these permutations are not merely bijections but single Hamiltonian cycles.

Each $D$-orbit is traversed entirely by alternating applications of $A$ and $B$, and the propagation rule couples all orbits through the global bijection condition: once one orbit is entered by $\pi$, the structure forces transitions into the remaining orbits before returning.

More concretely, because both generators $A$ and $B$ project nontrivially onto both coordinates, the induced permutation cannot preserve any proper union of $D$-orbits. Any invariant subset under $\pi$ would have to be closed under both translations, forcing it to be all of $G$.

Thus every valid choice yields a single cycle of length $mn$, so no overcounting occurs.

6. Final count

The number of northeasterly knight’s tours on the $m\times n$ torus is

$$ \boxed{2^{\gcd(m,n)}}. $$

Conclusion

The corrected argument restores the missing global structure: the constraint propagates along diagonals defined by $B-A$, decomposing the torus into $\gcd(m,n)$ independent consistency cycles. Each cycle admits exactly two coherent assignments, and every assignment produces a Hamiltonian cycle. This yields the closed form $2^{\gcd(m,n)}$, resolving the enumeration.