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. 
 A: 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.
A: 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$
A: 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.
