I was thinking on some variations of the n-Queen problem until I reached the following problem I couldn't solve:
How many ways are there to put $n$ kings (as in a chess game) on a $n\times n$ chessboard such that no two kings threaten each other?
I'm not so optimistic that it would be solved in "non purely computational" methods. I've tried recursions, bijection and almost anything in my own knowledge yet I have achieved nothing.
Any help would be appreciated!
N-“Kings” Problem
chessboardcombinatorics
Related Solutions
If the number of rows and columns are multiples of $3$, you can break the board into $3 \times 3$ squares, put eight kings around the edge of each square and leave the central square empty. This gets $\frac 89$ filling fraction. This is the best you can do because each empty cell can receive at most eight kings. I am pretty sure that just cutting off rows is as good as you can do for the cases where one or both dimensions are $2 \bmod 3$. You can't for $1 \bmod 3$ because you lose some of the central squares. Here are my best shots for $12 \times 9$ and $10 \times 7$. Kings are in the red cells.
I do not think there is any formula to count the number of matrices. You can use dynamic programming to count the number of matrices for $n\le 10$, but the time required is $O(n^32^{2n})$, so this quickly becomes infeasible. Here is the data I found (not in OEIS):
| $n$ | $4$ | $6$ | $8$ | $10$ |
|---|---|---|---|---|
| # matrices | $246$ | $8784000$ | $111869178489670$ | $384868991272320758246400$ |
Here is a sketch of how the program works. Let $N(n,m,k,v)$ be the number of $m\times n$ matrices with elements in $\mathbb Z/2\Bbb Z$ which have exactly $k$ ones, where every row has an even number of ones, and for which the sum of the row vectors is $v$. By considering all possible choices for the last row of the matrix, we have $$ N(n,m,k,v)= \begin{cases} \sum_r N(n,m-1,k-|r|,v\oplus r) & m \ge 1 \\ 1 & m=0, k=0,v=\vec 0 \\ 0 & \text{otherwise} \end{cases} $$ where the sum ranges over all vectors $r\in (\Bbb Z/2\Bbb Z)^n$ with an even number of ones, $|r|$ is the number of ones in $r$, and $\oplus$ is the usual vector addition in $(\mathbb Z/2\mathbb Z)^n$. Your problem calls for $N(n,n,n^2/2, \vec 0)$.
Best Answer
Based on the section 2.1.2 book "Non-attacking chess pieces" by "Václav Kotěšovec", the general answer does exist and is equal to the following : $$ \frac{n^{2n}}{n!}\left(1-\frac{9(n-1)n}{2n^2}+\frac{(n-1)n(243n^2-439n-142)}{24n^4}-\ldots\right) $$