The kings problem asks for the maximum number 
of nonattacking kings that can be placed on an 
chessboard, where 
is a positive
integer. For 
, the solution is 16, as illustrated
above (Madachy 1979). In general, the solutions are
 |
(1)
|
(Madachy 1979), giving the sequence of doubled squares 1, 1, 4, 4, 9, 9, 16, 16, ... (OEIS A008794). This sequence has generating function
 |
(2)
|
The minimum numbers of kings needed to occupy or attack every square on an 
chessboard (i.e., domination numbers for the 
king graphs) are given
for 
, 2, ... by 1, 1, 1, 4, 4, 4, 9, 9, 9, 16, ... (OEIS
A075561), with the ![gamma(P_8□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]P_8)=9](/images/equations/KingsProblem/Inline8.svg)
case illustrated above (Madachy 1979, p. 39). In general, for positive
integers 
and 
, the king graph is the
graph strong product ![P_m□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]P_n](/images/equations/KingsProblem/Inline11.svg)
of two path graphs, with
![gamma(P_m□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]P_n)=|_(m+2)/3_||_(n+2)/3_|,](/images/equations/KingsProblem/NumberedEquation3.svg) |
(3)
|
where 
is the floor function.
