info prev up next book cdrom email home

Bishops Problem

\begin{figure}\begin{center}\BoxedEPSF{BishopsMax.epsf}\end{center}\end{figure}

Find the maximum number of bishops $B(n)$ which can be placed on an $n\times n$ Chessboard such that no two attack each other. The answer is $2n-2$ (Dudeney 1970, Madachy 1979), giving the sequence 2, 4, 6, 8, ... (the Even Numbers) for $n=2$, 3, .... One maximal solution for $n=8$ is illustrated above. The number of distinct maximal arrangements of bishops for $n=1$, 2, ... are 1, 4, 26, 260, 3368, ... (Sloane's A002465). The number of rotationally and reflectively distinct solutions on an $n\times n$ board for $n\geq 2$ is

\begin{displaymath}
B(n)=\cases{
2^{(n-4)/2} [2^{(n-2)/2}+1] & for $n$\ even\cr
2^{(n-3)/2} [2^{(n-3)/2}+1] & for $n$\ odd\cr}
\end{displaymath}

(Dudeney 1970, p. 96; Madachy 1979, p. 45; Pickover 1995). An equivalent formula is

\begin{displaymath}
B(n)=2^{n-3}+2^{\left\lfloor{(n-1)/2}\right\rfloor -1},
\end{displaymath}

where $\left\lfloor{n}\right\rfloor $ is the Floor Function, giving the sequence for $n=1$, 2, ... as 1, 1, 2, 3, 6, 10, 20, 36, ... (Sloane's A005418).


\begin{figure}\begin{center}\BoxedEPSF{BishopsMin.epsf}\end{center}\end{figure}

The minimum number of bishops needed to occupy or attack all squares on an $n\times n$ Chessboard is $n$, arranged as illustrated above.

See also Chess, Kings Problem, Knights Problem, Queens Problem, Rooks Problem


References

Ahrens, W. Mathematische Unterhaltungen und Spiele, Vol. 1, 3rd ed. Leipzig, Germany: Teubner, p. 271, 1921.

Dudeney, H. E. ``Bishops--Unguarded'' and ``Bishops--Guarded.'' §297 and 298 in Amusements in Mathematics. New York: Dover, pp. 88-89, 1970.

Guy, R. K. ``The $n$ Queens Problem.'' §C18 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 133-135, 1994.

Madachy, J. Madachy's Mathematical Recreations. New York: Dover, pp. 36-46, 1979.

Pickover, C. A. Keys to Infinity. New York: Wiley, pp. 74-75, 1995.

Sloane, N. J. A. Sequences A002465/M3616 and A005418/M0771 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26