Kings Problem

$\begin{figure}\begin{center}\BoxedEPSF{KingsMax.epsf}\end{center}\end{figure}$

The problem of determining how many nonattacking kings can be placed on an $n\times n$ Chessboard. For , the solution is 16, as illustrated above (Madachy 1979). In general, the solutions are

$\begin{displaymath} K(n)=\cases{ {\textstyle{1\over 4}}n^2 & $n$\ even\cr {\textstyle{1\over 4}}(n+1)^2 & $n$\ odd\cr} \end{displaymath}$

(1)

(Madachy 1979), giving the sequence of doubled squares 1, 1, 4, 4, 9, 9, 16, 16, ... (Sloane's A008794). This sequence has Generating Function

$\begin{displaymath} {1+x^2\over(1-x^2)^2(1-x)}=1+x+4x^2+4x^3+9x^4+9x^5+\ldots. \end{displaymath}$

(2)

$\begin{figure}\begin{center}\BoxedEPSF{KingsMin.epsf}\end{center}\end{figure}$

The minimum number of kings needed to attack or occupy all squares on an $8\times 8$ Chessboard is nine, illustrated above (Madachy 1979).

References

Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, p. 39, 1979.