# How many ways are there to tile a chessboard with 32 knights?

The maximal amount of knights which can be places on a regular $8 \times 8$ chessboard so that no two take each other is $32$ (To see this just notice that a knight on a black square only attacks knights placed on white squares).

I was wondering how many ways there are to tile a regular chessboard with these $32$ knights so that no two take each other.

A generalisation of this question has already been posed here: In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?. However, the answers given include a polynomial approach which cannot be used in the case of an $8 \times 8$ chessboard, because, as an answer states, a computer struggles to compute such a polynomial.

Even if it were quite easy for a computer to compute such a polynomial, in an Olympiad no such computational power is allowed. Hence, I was wondering if there was a pure combinatorics approach for this particular case.

An example of such a tiling is to place all the knights on all the black cells.

• You can put the knights on the black squares or on the white squares. This makes two ways. Or am I missing something? – ajotatxe Jul 20 '17 at 11:58
• @ajotatxe Are there no other possibilities? Can you prove this? – Plato Jul 20 '17 at 11:59
• Consider a knight's tour of the chessboard. Obviously, if $32$ of the $64$ squares are occupied by non-attacking knights, then the tour must alternate between occupied and unoccupied squares. This means that there are (at most) two ways to place the $32$ knights. But of course there are two ways, use all the black squares or all the white squares. – bof Jul 20 '17 at 12:11
• In graph-theoretic terms: A cycle graph $C_{2n}$ has exactly two independent sets of size $n.$ Therefore, a Hamiltonian graph of order $2n$ has at most two independent sets of size $n.$ The knight's graph on the $8\times8$ chessboard is a Hamiltonian graph of order $64.$ – bof Jul 20 '17 at 12:20
• The existence of a knight's tour seems crucial here. Actually, in a $2\times 2$ board there is no knight's tour, and there are $6$ ways to put two non-attacking horses on it. – ajotatxe Jul 20 '17 at 12:26

Consider a knight's tour of the chessboard. Obviously, if $32$ of the $64$ squares are occupied by non-attacking knights, then the tour must alternate between occupied and unoccupied squares, since a horse can only attack a square if the opposite colour. This means that there are (at most) two ways to place the $32$ knights. We can offer examples of these two ways: use all the black squares or all the white squares.
Another way to look at the problem is to consider graph theory. A cycle graph $C_{2n}$ has exactly two independent sets of size $n$. Therefore, a Hamiltonian graph of order $2n$ has at most two independent sets of size $n$. The knight's graph on the $8 \times 8$ chessboard is a Hamiltonian graph of order 64. From here we can conclude in the same manner as in the first solution.