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

-
Welcome to math.SE. We love to answer questions here, especially intriguing ones (which this is, in my opinion). But it really helps your own odds and this site's impression of you as a new poster if you add a paragraph (or even just a sentence) detailing what you have tried yourself and where you're stuck. – Arthur Dec 20 '13 at 16:30
Not a complete answer, but it might help: divide the board into 9 $2\times 2$ tiles. Each such tile can contain at most one king, so this gives an easy (but very loose) upper bound of $5^9$. Moreover, this approach reduces the problem to a 2D analogue of combinatorics on words: counting grids which avoid forbidden subgrids. – Peter Taylor Dec 20 '13 at 21:06
@Serkan, I'm not sure what you're counting there. The more obvious criticism is that the last sentence of my comment talks about "reducing" to a problem class which already contains the original problem. – Peter Taylor Dec 22 '13 at 7:11
@Serkan, we've both been trying to bound the wrong problem. You were trying to bound it for 3 kings and I for 0 to 9 kings, but I see now that the question asks about 6 kings, so the division into $2\times 2$ tiles gives a bound of $\binom{9}{6}4^6$. – Peter Taylor Dec 22 '13 at 23:28
@PeterTaylor Oh ok, you're right :) – user33321 Dec 23 '13 at 0:48

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.

-

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$

-
You might also be interested in A061995,...,A061998 in OEIS. – benh Dec 22 '13 at 3:09
A more relevant OEIS sequence is A018807. – Peter Taylor Dec 22 '13 at 7:51
Oh. I've been trying to solve the wrong problem. – Peter Taylor Dec 22 '13 at 23:19

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.

-
When you consider center right and center bottom, there should be only 12 possibilities, not 15. There are 4 choices for each king, but if one is in row 4 and the other in row 5 they are next to each other. – Ross Millikan Dec 22 '13 at 3:14
@Ross, only if they're at (4,5) and (5,4). – Peter Taylor Dec 22 '13 at 7:18
Sorry, misimagined it. I was thinking center right and bottom right. – Ross Millikan Dec 22 '13 at 16:25

There are lot of information collected in "Non-attacking chess pieces" (sixth edition) book by Vaclav Kotesovec, http://web.iol.cz/vaclav.kotesovec/ published online at http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf or at http://members.chello.cz/photos2/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.

-