Problem of the Month (March 2005)

The problem of placing 8 non-attacking queens on an 8×8 chessboard is well known. Less known is the problem of placing different colored queens on a chessboard so that no queen attacks one of a different color. Mario Velucchi found many interesting results on this problem years ago. For example, here are 2 sets of 7 non-attacking queens on a 7×7 chessboard and 4 sets of 3 non-attacking queens on an 8×8 chessboard:

Unfortunately, the problem of placing different colored rooks on a chessboard is not as interesting. It is not hard to show that the maximum number of rooks of C different colors on an N×N chessboard so that none attacks a rook of a different color is 2N/C /2 × 2N/C /2 . For example, here are 3 sets of 6 non-attacking rooks on an 8×8 chessboard:

This month we consider the problem of placing the maximum number of bishops or knights of C different colors each on an N×N chessboard so that no bishop or knight attacks one of a different color. Let B(C,N) be the maximum number of bishops, and K(C,N) be the maximum number of knights.

Clearly B(1,N) = K(1,N) = N2 and B(2,N) = N2/2 . Can you show B(3,5)=5? or B(3,6)=8? Can you find a formula or bounds for B(3,N)? How about B(C,N)? Can you show K(3,4)=4? or K(5,5)=3? Can you find a formula for K(2,N)? What are the other values of K(C,N)?


ANSWERS

Joseph DeVincentis and Emilio Schiavi proved that B(C,N)=0 for C > 2N-2.

Joseph DeVincentis proved and B(N-1,N)=4.

Emilio Schiavi proved that B(2N-2,N)=1 and B(N,N)=2. He also proved the following. Let C be even and let K = 2N/C . Then if C divides 2N, then B(C,N) ≥ K2/2 , and if not, then B(C,N) ≥ K(K+1)/2 .

Philippe Fondanaiche conjectured that B(3,N)=2N-4 if N is even and B(3,N)=2N-5 if N is odd, and B(4,N)=2N-6, but these fail for large N.

Corey Plover noticed that B(C,N) ≥ a B(aC,N), and conjectured that B(4,2N) = (N+1)2/2 - 2.

Sasha Ravsky showed that B(C,N) ≤ ((2N-1)/C)2.

Joseph DeVincentis, Philippe Fondanaiche, Corey Plover, and Claudio Baiocchi found many of the small configurations below.

Best-Known Lower Bounds for B(C,N)
N \ C123456789
11
242
39421
41684211
52512542111
636188642111
7492410844211
86432141064421
98140171386442


Joseph DeVincentis and Corey Plover proved that K(3,4)=4.

Philippe Fondanaiche and Claudio Baiocchi showed that K(2,2n) ≥ 2n(n-1) for n > 2 and K(2,2n+1) ≥ 2n2 for n ≥ 2.

Joseph DeVincentis noticed that by placing the knights all on the black squares of the checkerboard, we have K(2,N) ≥ N2 /2 /C . Claudio Baiocchi noted that often some knights can be placed on white squares to improve this bound.

Corey Plover noticed that K(C,N) ≥ a K(aC,N).

Claudio Baiocchi showed that K(4,2n) ≥ 1+(n-1)2 and K(4,2n+1) ≥ n+(n-1)2. He notes these are not sharp for 5x5 or 6x6 boards, but expects they are for larger n.

Sasha Ravsky showed that K(C,N) ≥ N ((N+2)/C - 2) by placing knights of different colors in different rows separated by 2 blank rows.

Joseph DeVincentis, Philippe Fondanaiche, and Claudio Baiocchi found many of the small configurations below.

Best-Known Lower Bounds for K(C,N)
N \ C123456789
11
24211
393211
4166421111
525105432211
636148643332
7491811754433
86424131076543
Joe DeVincentis
Philippe Fondanaiche
Claudio Baiocchi


If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 4/26/05.