11
$\begingroup$

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

Improve this question
$\endgroup$
11
  • $\begingroup$ 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)? $\endgroup$
    – Julian Rosen
    Commented Nov 30, 2014 at 16:29
  • $\begingroup$ @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. $\endgroup$
    – Rand al'Thor
    Commented Nov 30, 2014 at 16:31
  • $\begingroup$ At the very least we would require $\operatorname{gcd}\left( m, n\right) = 1$ and $m,n < 7$. $\endgroup$
    – COTO
    Commented Nov 30, 2014 at 16:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – Rand al'Thor
    Commented Nov 30, 2014 at 16:45
  • 1
    $\begingroup$ @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 :-( $\endgroup$
    – Rand al'Thor
    Commented Nov 30, 2014 at 17:11

1 Answer 1

Reset to default
15
$\begingroup$

This question is answered in a paper by Donald Knuth [1].

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.

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Except an (m,n) leaper, which is what they talk about is the equivalent of a (m+1 x n+1) General $\endgroup$
    – blademan9999
    Commented Jan 9, 2023 at 16:31
  • $\begingroup$ 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. $\endgroup$
    – Ben Reiniger
    Commented May 23, 2023 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.