TOPICS
Search

Kings Problem


KingsMax

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

 K(n)={1/4n^2   n even; 1/4(n+1)^2   n odd
(1)

(Madachy 1979), giving the sequence of doubled squares 1, 1, 4, 4, 9, 9, 16, 16, ... (OEIS A008794). This sequence has generating function

 (1+x^2)/((1-x^2)^2(1-x))=1+x+4x^2+4x^3+9x^4+9x^5+....
(2)
KingsMin

The minimal number of kings needed to occupy or attack every square on an n×n chessboard (i.e., domination numbers for the n×n king graphs) are given for n=1, 2, ... by 1, 1, 1, 4, 4, 4, 9, 9, 9, 16, ... (OEIS A075561), with the gamma(K_(8,8))=9 case illustrated above and noted by (Madachy 1979, p. 39). In general, for an m×n chessboard,

 gamma(K_(m,n))=|_(m+2)/3_||_(n+2)/3_|.
(3)

See also

Bishops Problem, Chess, Hard Hexagon Entropy Constant, Knights Problem, Queens Problem, Rooks Problem

Explore with Wolfram|Alpha

References

Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, p. 39, 1979.Sloane, N. J. A. Sequences A008794 and A075561 in "The On-Line Encyclopedia of Integer Sequences."Watkins, J. Across the Board: The Mathematics of Chessboard Problems. Princeton, NJ: Princeton University Press, 2004.

Referenced on Wolfram|Alpha

Kings Problem

Cite this as:

Weisstein, Eric W. "Kings Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KingsProblem.html

Subject classifications