10

The 8 queen's puzzle is a well-known puzzle involving placing 8 queens on a chessboard so that no queen attacks another queen. It is more or less obvious that 8 is the maximum number of queens that can populate a chessboard so that no queens are attacking each other.

But what if we use knights instead? How many knights can we maximally place on a chessboard while still satisfying the stipulation of no piece attacking another piece? So far the maximum I've achieved is 24, attained by placing a cluster of 4 knights in the center, and on every square on the edge of the board except for c1, a3, a6, c8, f8, h6, h3, and f1. I cannot see how this number is improved, although I haven't proven that 24 is the theoretical maximum yet.

Additionally, what happens if we use bishops? The maximum I've achieved is 14 at the moment, placing as many as possible along the edges. But this one I haven't really tried to optimize very much.

7
  • 2
    I would recommend you to move the bishops part to a new question, in order not to mix them.
    – Ángel
    Sep 4, 2020 at 0:59
  • 1
    @bof Could you post an answer, please? You've written a lot of detailed things in comments, but comments aren't designed to hold permanent information (e.g. they're not searchable, and are one-click deletable).
    – wizzwizz4
    Sep 4, 2020 at 13:15
  • 1
    Small correction to @bof's argument for a maximum of 14 bishops: there are 8 parallel diagonals for each color, but two of those diagonals consist of a single square each, and those squares attack each other along the perpendicular diagonal, so only one of those two diagonals can be occupied. Sep 4, 2020 at 16:55
  • 1
    @bof - My apologies - should have checked both directions. Sep 4, 2020 at 23:40
  • 2
    @reirab In these sorts of problems it's customary to say the pieces don't "attack" each other, though it would make more sense to say they don't protect each other since they are all the same color.
    – bof
    Sep 5, 2020 at 1:52

2 Answers 2

20

14 non-attacking bishops

We may consider the white-square bishops and the black-square bishops separately.

At most 7 bishops can be placed on white squares, namely, at most one bishop on each of the 7 white diagonals parallel to the h1-a8 diagonal. In fact, we can put bishops on the 7 white squares b1, d1, f1, h1, c8, e8, g8.

The solution for black-square bishops is just the mirror image of the solution for white-square bishops. At most one bishop can be placed on each of the 7 black diagonals parallel to the a1-h8 diagonal, and this can be achieved with bishops on a1, c1, e1, g1, b8, d8, f8.


32 non-attacking knights

We can put 32 knights on the board by putting knights on all the white squares or on all the black squares.

One way to see the we can't have more than 32 knights is to consider a knight's tour. If we number the squares from 1 to 64 in the order they are visited by the touring knight, then it's clear that our non-attacking knights can occupy at most one of the two squares 1 & 2, at most one of squares 3 & 4, at most one of squares 5 & 6, and so on.

But a knight's tour is somewhat difficult, and not really needed for this problem. All we really need is to divide the 64 squares of the chessboard into 32 pairs, each pair being separated by a knight's move. Since the 8 x 8 board can be cut up inti eight 2 x 4 boards, it will be enough to observe that the 2 x 4 board admits such a pairing (and therefore can hold at most 4 non-attacking knights), namely a1 & c2, a2 & c1, b1 & d2, b2 & d1.


Non-attacking knights on variant chessboards

It can be shown that, provided m,n > 2, the maximum possible number of knights on an m x n chessboard is ceiling(mn/2), that is, it's mn/2 if mn is even, (mn+1)/2 if mn is odd. This number can obviously be attained by putting all the knights on squares of one color. Proving that it's optimal is more work.

Let's say that an m x n chessboard has a "good pairing" if the set of squares can be partitioned into pairs (with one square left over if mn is odd), each pair being connected by a knight move. The existence of a good pairing follows from the existence of a knight's tour, but good pairings are easier to find than knight's tours. It will suffice to show that a good pairing exists whenever m,n > 2. In fact, it will suffice to show that a good pairing exists for 2 x 4, 3 x 3, 3 x 4, 3 x 5, 3 x 6, 5 x 5, and 5 x 6 chessboards, since every m x n chessboard with min(m,n) > 2 can be partitioned into rectangular pieces of those seven sizes, without using more than one piece with an odd number of squares. Constructing good pairings for those seven small boards is left to the reader. (The 3 x 4, 5 x 5, and 5 x 6 boards allow knight's tours.)

0
14

For knights, the maximum is 32. Since knights can only attack the color opposite of the square they’re on, placing one on 32 squares of the same color is therefore optimal.

[FEN "N1N1N1N1/1N1N1N1N/N1N1N1N1/1N1N1N1N/N1N1N1N1/1N1N1N1N/N1N1N1N1/1N1N1N1N w - - 0 1"]

As for bishops, 14 is the highest possible.

[FEN "B7/B6B/B6B/B6B/B6B/B6B/B6B/B7 w - - 0 1"]
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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