Leaper Tours

The knight is a chess piece that moves one step in one direction (North, South, East, or West) and two steps in an orthogonal direction. The first tours of the knight on the traditional $8 \times 8$ chessboard, visiting each square exactly once and going back to the starting square, seem to have been constructed as early as the 9th century.

Consider a “generalized knight”, or “leaper”, that moves $p$ steps in one direction and $q$ steps in an orthogonal direction. What natural obstructions forbid a tour on an $m \times n$ board? From the graph-theoretic point of view, we consider the graph obtained from the $m \times n$ rectangular grid by adding edges between all points $(x, y)$ and $(x \pm p, y \pm q)$, as well as between $(x, y)$ and $(x \pm q, y \pm p)$, and the goal is to understand when this graph is Hamiltonian.

There are several natural necessary conditions for the existence of a tour. First, $p + q$ should be odd, since otherwise the generalized knight would only stay on squares of coordinates $(x, y)$ where $x + y$ has some fixed parity. Second, $p$ and $q$ should be relatively prime, since otherwise the generalized knight would always stay on squares of coordinates $(x, y)$ where $x$ and $y$ have some fixed remainders modulo $d$, for some $d \ge 2$. Generalized knights which satisfy both of these conditions are known as free.

Note that, when $p + q$ is odd, the generalized knight alternates between white squares and black squares in the traditional chessboard coloring, so the total number of squares has to be even if a tour exists. Finally, we need to assume in addition that $m$ and $n$ are sufficiently large compared to $p$ and $q$. For example, the generalized knight cannot make any moves at all on a board where one side is at most $\min(p, q)$.

If all of these conditions are satisfied, is it true that the generalized knight can tour the board?

In the present paper, the author proves that for free generalized knights, a tour always exists on boards where both of $m$ and $n$ are even and sufficiently large compared to $p$ and $q$. There are two main ingredients to the proof. One is an earlier result of the author, confirming a conjecture of Willcocks, which states that a free generalized knight always tours the board of size $2(p + q) \times 2(p + q)$. The other, original to the present paper, is the proof that a free generalized knight tours all boards of size $4pq \times n$ where $n$ is sufficiently large compared to $p$ and $q$.