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) = N² and B(2,N) = N²/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)?

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) ≥ K²/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.

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

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

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

Joseph DeVincentis noticed that by placing the knights all on the black squares of the checkerboard, we have K(2,N) ≥ N² /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)² and K(4,2n+1) ≥ n+(n–1)². He notes these are not sharp for 5×5 or 6×6 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.

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.