# Generalisation of tours on chessboards

It's well-known that a knight placed on one square of a chessboard can get to any other square, but a bishop can only reach half the squares from a fixed starting point. Another question on this site dealt with a new type of chess piece with a different way of moving. I'm trying to generalise all of these ideas.

A knight's move takes you between opposite corners of a $2\times3$ rectangle of squares. A bishop's move takes you between opposite corners of a $2\times2$ rectangle. So let's define a General (a new, generalised breed of chess piece) to be a piece that can move from its current position to the opposite corner of an $m\times n$ rectangle. For what values of $m$ and $n$ is it possible for a General to start from one square and reach every other square on the chessboard?

(Possible further generalisations include changing the chessboard to $M\times N$ rather than $8\times8$; looking for a 'General's tour', the General visiting each square exactly once; or looking for a 'General's tour' with the General visiting each square exactly once and ending on the same square it began on.)

• To clarify: do you want the General to visit each square once and only once? Also, do you want the tour to be closed (meaning the General ends at the same square it started)? Nov 30, 2014 at 16:29
• @JulianRosen - Either of these restrictions would also make for interesting questions, but I was just thinking of all squares being reachable from any one. I'll edit the question. Nov 30, 2014 at 16:31
• At the very least we would require $\operatorname{gcd}\left( m, n\right) = 1$ and $m,n < 7$.
– COTO
Nov 30, 2014 at 16:33
• @Gilles - What's wrong with the two tags you removed? They say a lot more about what the question's really about than 'chess' does. Nov 30, 2014 at 16:45
• @JulianRosen - Yes, it cuts both ways. But from what I've seen on meta and on some of my more mathematical questions, maths on this site tends to scare away more people than it attracts :-( Nov 30, 2014 at 17:11

This question is answered in a paper by Donald Knuth .

Theorem: An $$(m\times n)$$-Leaper, with $$1\leq m\leq n$$, can reach every square on an $$M\times N$$ board, with $$2\leq M\leq N$$, if and only if the following three conditions hold:

• $$m+n$$ is relatively prime to $$m-n$$
• $$N\geq 2n$$
• $$M\geq m+n$$

The proof is a couple of pages. Maybe it's possible to give a quicker argument for $$8\times 8$$ boards.

 Knuth, Donald. Leaper Graphs. The Mathematical Gazette, Vol. 78, No. 483 (Nov., 1994), pp. 274-297

• Except an (m,n) leaper, which is what they talk about is the equivalent of a (m+1 x n+1) General Jan 9 at 16:31
• On 8x8 (indeed any square board), the third condition is redundant to the second, which reduces at least that largest chunk of the necessity proof. But of course the sufficiency is the hard and long argument. May 23 at 14:08