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

$\endgroup$
  • $\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 Nov 30 '14 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 Nov 30 '14 at 16:31
  • $\begingroup$ At the very least we would require $\operatorname{gcd}\left( m, n\right) = 1$ and $m,n < 7$. $\endgroup$ – COTO Nov 30 '14 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 Nov 30 '14 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 Nov 30 '14 at 17:11
10
$\begingroup$

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

Theorem: An $(m\times n)$-General, 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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