1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can put the knights on the black squares or on the white squares. This makes two ways. Or am I missing something? $\endgroup$ – ajotatxe Jul 20 '17 at 11:58
  • $\begingroup$ @ajotatxe Are there no other possibilities? Can you prove this? $\endgroup$ – Plato Jul 20 '17 at 11:59
  • 4
    $\begingroup$ 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. $\endgroup$ – bof Jul 20 '17 at 12:11
  • 1
    $\begingroup$ 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.$ $\endgroup$ – bof Jul 20 '17 at 12:20
  • 1
    $\begingroup$ 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. $\endgroup$ – ajotatxe Jul 20 '17 at 12:26
2
$\begingroup$

This is bof's solution to the problem.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.