The Problem of the Kings

Abstract

On a $2m\times 2n$ chessboard, the maximum number of nonattacking kings that can be placed is $mn$, since each $2\times 2$ cell can have at most one king. Let $f_m(n)$ denote the number of ways that $mn$ nonattacking kings can be placed on a $2m\times 2n$ chessboard. The purpose of this paper is to prove the following result.

Theorem. For each $m=1,2,3,\ldots $ there are constants $c_m>0$, $d_m$, and $0\le \theta_m < m+1$ such that $$f_m(n)= (c_mn+d_m)(m+1)^n+O(\theta_m^n)\qquad (n\to\infty).$$