Kings on a chessboard

Question

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.

Answer 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.

Answer 2

I would love to see a generating function approach, but while we're waiting for someone to find it here's a sketch of how we can exploit the small size of this problem to enumerate by hand.

We're going to use the property that no $2\times 2$ square can contain more than one king. So we divide the $6\times 6$ grid into a $3\times 3$ grid of $2 \times 2$ squares. Assume for the time being that we're packing a maximal 9 kings onto the board: therefore each of these squares contains one king.

The board has rotational symmetry, so wlog the king on the centre $2 \times 2$ square is in the top left, and we multiply all board counts by $4$:

4x
??????    Key:
?---??      K  King
?-K-??      -  No king
?---??      ?  Uncertain
??????
??????

Now consider the centre-right and the centre-bottom squares, which are unconstrained by our first king and have considerable knock-on effects on the adjacent three squares. There are 15 possible placements of kings in these two squares (the 16th is ruled out because they're diagonally adjacent), but taking into account the symmetry along the leading diagonal we have 9 distinct cases:

4x        8x        8x        8x        8x        4x        8x        8x        4x
??????    ??????    ??????    ??????    ??????    ??????    ??????    ??????    ??????
?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?---??    ?---??
?-K-K-    ?-K-K-    ?-K-K-    ?-K--K    ?-K--K    ?-K--K    ?-K--K    ?-K---    ?-K---
?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?---K-    ?----K
?-K-??    ??-K-?    ?---??    ?-K-??    ??-K-?    ?---??    ??---?    ?-----    ??----
?---??    ??---?    ?-K-??    ?---??    ??---?    ?-K-??    ??-K-?    ?-K-??    ??-K-?

Observe that in each case the bottom-right square is now a choice independent of the remaining unplaced kings, and the spaces available for the remaining unplaced kings fit a mere 3 patterns:

96x       64x       4x
??????    ??????    ??????
?         ?         ?   ??
?         ?         ?     
?         ?         ?     
?         ??        ??    
?         ??        ??    

Calculate the number of placements for each of these patterns (which is a straight combinatorics-on-words problem) and you just need to apply the appropriate multiplicities.

You still need to calculate the number of patterns which have fewer than 9 kings, but since the constraints on placement are the same each of them is going to be one or more of these patterns with some kings removed. I haven't worked through the details, but I would hope that standard techniques would serve.

Answer 3

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$

Answer 4

There are lot of information collected in "Non-attacking chess pieces" (sixth edition) book by Vaclav Kotesovec, http://www.kotesovec.cz/ published online at http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf (written in Czech language)

Kings positions are discussed in section 2 of the work:

2.1   k Kings on an n x n chessboard 
2.1.1   k Kings on a 1 x n and 2 x n chessboard 
2.1.2   n Kings on an n x n chessboard
2.2   k Kings on an k x n chessboard 
2.3   m x n Kings on a 2m x 2n chessboard
2.3.1   n Kings on a 2 x 2n chessboard 
2.3.2   2n Kings on a 4 x 2n chessboard 
2.3.3   3n Kings on a 6 x 2n chessboard 
2.3.4   4n Kings on a 8 x 2n chessboard 
2.3.5   5n Kings on a 10 x 2n chessboard 
2.3.6   6n Kings on a 12 x 2n chessboard
2.3.7   7n Kings on a 14 x 2n chessboard 
2.3.8   8n Kings on a 16 x 2n chessboard 
2.3.9   more kings on a 2m x 2n chessboard 
2.3.10   Largest and smallest root 
2.4   n^2  Kings on a 2n x 2n chessboard

2.5-2.9 are about chessboards with one of dimension connected into cylinder or with both dimensions connected (toroidal chessboard)

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

Your task is "2.1.2 n Kings on an n x n chessboard" and there is link to OIES "n kings n x n, A201513" - http://oeis.org/A201513

Here is the copy of A201513 as of February 2014:

LINKS: Andrew Woods, Table of n, a(n) for n = 1..20

V. Kotesovec, Non-attacking chess pieces

FORMULA: Asymptotics (Vaclav Kotesovec, Nov 29 2011): n^(2n)/n!*e^(-9/2).

AUTHOR: Vaclav Kotesovec, Dec 02 2011

And table for all n:

1 1
2 0
3 8
4 79
5 1974
6 62266
7 2484382
8 119138166
9 6655170642
10 423677826986
11 30242576462856
12 2390359529372724
13 207127434998494421
14 19516867860507198208
15 1986288643031862123264
16 217094567491104327256049
17 25357029929230564723578520
18 3151672341378566296926684684
19 415294220890662636616927907958
20 57824201125787566041674560880632

If you want numbers for bigger n, just ask, I will try to compute them. I already computed some biggest variants of king placing tasks for Kotesovec.