Problem of the Month (July 2007)

The problem of finding closed knight tours of rectangular chessboards is well-known. An m×n chessboard has a closed knight tour for m≤n when mn is even except when m=1, 2, or 4, or when m=3 and n<10. Now consider a whole army of knights located on every light square in such a tour, and give the tour some orientation. No knight attacks any other, and this remains true as every knight moves simultaneously around the tour one move at a time.

We generalize this by looking for closed tours of rectangular chessboards by Kings, Rooks, or Queens so that each piece moves only one square at a time, and no piece attacks any other as they move around the tour. For a given rectangle, what is the largest number of Rooks that can be in a closed non-threatening tour? What are the corresponding answers for Kings and Queens?

ANSWERS

Let R(m,n), K(m,n), and Q(m,n) be the maximum number of the corresponding chess pieces that can be part of a closed non-threatening tour. It is clear that R(m,n) ≤ min{m,n} and Q(m,n) ≤ min{m,n}, since no more than one piece can be in any row at any given time. It is less obvious that K(m,n) ≤

m/2

n/2

, because this is the maximum number of non-attacking Kings that will fit on such a chessboard. This can be reduced by 1 when m or n is odd, and reduced by 2 when both are odd, but surely there is a better upper bound? Corey Plover and Claudio Baiocchi noticed that K(m,n) ≥ Q(m,n), since the pieces have the same moves and the Queens are more restricted.

You can click on some of the tours below for an animation of the tour.

I proved that R(3,4n+2)=3 and R(3,2n)≥2 by generalizing these tours:

(animation)
(animation)

David Bush proved that R(2n,2m)=2min{m,n} by considering zig-zag tours like this:

David Bevan gave some great results for K(n,m), verifying many results by computer.

He showed these optimal values for K(3,n):

He showed these other lower bounds for K(3,n):

And he showed K(3,2n)≥n by generalizing the tour:

He showed K(4,n)≥n-1 (and that K(4,n)=n-1 for 3≤n≤8) with a series of tours:

He showed K(4,rs)≥2s for r≥3 by generalizing the tour:

He showed K(4,rs)≥4s for r≥5 odd by generalizing the tour:

He showed K(4,rs)≥8s for r≥13 odd by generalizing the tour:

He showed K(5,n)≥n for r≥3 by generalizing these tours:

He showed these lower bounds for larger rectangles:

Finally, he gave a very general tour that shows K(3n,4m)≥2mn:

Claudio Baiocchi sent me an applet to animate most of these tours.

Here are the best known bounds on K(n,m):

Bounds for K(n,m)

n \ m	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
3	1	2	3	3	2	4	3	5	5	6	4	7	[5,14]	[8,15]	[7,16]
4		3	4	5	6	7	[8,9]	[9,10]	[10,11]	[11,12]	[12,13]	[13,14]
5			[5,7]	[6,8]	[7,10]	[8,11]	[9,13]	[10,14]	[11,16]	[12,17]	[13,19]	[14,20]
6				[6,9]	[7,11]	[8,12]	[9,14]	[12,15]
7					[7,14]	[8,15]
8						[8,16]