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\).