Kings on a chessboard

In how many different ways can six kings be placed on a $6\times 6$ chessboard so that no one attacks the others?

If the problem was asked for a $3 \times 3$ board and $3$ kings, then the answer would be 8.

I tried to find all the combinations at least two kings are attacking each other. Placed two kings adjacent vertically, horizontally, diagonally and counted the number of possibilities for the remaining $4$ kings. But there seems to be too many overlaps, meaning I counted the same situation more than once. And I couldn't figure out a way to subtract all the situations happening more than once.

Solution 1:

If haven't done the calculations, but can tell you how they can be done for the general problem of placing $k$ kings on a $p\times q$ board.

Let $I=\{1,\ldots,p\}$ represent a column of the board. For simplicity, assume that $p\le q$. Let $\cal{C}$ be the set of subsets of $I$ so that no pair $x,x+1\in C$ for any $C\in\cal{C}$: these sets represent permitted placements of kings in a column.

Now we define a matrix $A$ with elements $A_{ij}$ for $i,j\in\cal{C}$: you may enumerate the sets in $\cal{C}$ any way you like. We define the elements $$ A_{ij}=\left\{\begin{array}{l l} 0&\text{if there are $x\in i$, $y\in j$ with $|x-y|\le1$}\\ x^{|j|}&\text{otherwise, where $|j|$ is the number of elements in $j$} \end{array}\right. $$ so $A_{ij}$ represents the addition of a column with kings in the $j$ positions after having had a column with kings in the $i$ positions.

If we let $e=\{\}\in\cal{C}$ represent the initial state, i.e. no kings to the left of the board, and successively add $q$ columns, we get $$ e\cdot A^q\cdot 1=\sum_{k} a_kx^k $$ where the $1$ represents the vector $(1,\ldots,1)$ and $a_k$ is the number of ways to place $k$ kings on the $p\times q$ board.

This is fairly ok to compute for arbitrary $k$ and $q$, but quickly gets tough is $p$ increases. That's why selecting $p\le q$ is an advantage if the board is rectangular but not square.

Solution 2:

Let $K(n,k)$ be the number of ways to place $k$ kings on a $n \times n$ chess board.

I want to suggest a graph theoretic point of view on the problem: You are investigating the number of independent k-sets of a grid graph where diagonal elements are adjacent. Equivalently, this is the number of k-cliques in the complementary graph. There are general algorithms to compute those numbers, but also asymptotic results and algorithms to determine the maximum number of $k$ for which $K(n,k)\neq 0$.

However, for just calculating some values for $K$, I think an approach like the one Einar Rødland suggested is more efficient.

I implemented a similar one and got the following values for $K(n,k)$ where rows are $n$ from 2 to 6

1 King     2 Kings     3 Kings    4 Kings     5 Kings     6 Kings   
4         
9          16          8         
16         78          140        79         
25         228         964        1987        1974       
36         520         3920       16834       42368       62266     

and here is the OEIS-sequence you are looking for:

http://oeis.org/search?q=8%2C79%2C1974%2C62266&sort=&language=german&go=Suche

EDIT: the maximum $k$ for which $K(n,k)\neq 0$ is $\lceil \frac{n}{2} \rceil^2$