Proofs of Existence and Optimality · Constructive Proofs of Existence
Lesson 11
Nikolai Chukhin · Alexander S. Kulikov
Eight queens and thirty-two knights can be placed. To verify this, just look at the diagram below. It is easy to see directly that the queens do not attack each other. To verify that no two knights attack each other, note that, on the one hand, they all stand on squares of the same color, and on the other hand, a knight only attacks squares of the opposite color. However, fifteen bishops cannot be placed on the board; we will soon prove this rigorously. But fourteen bishops can be placed, as shown in the diagram.
For the curious 🤓
The diagram above is a rigorous mathematical proof that the required number of pieces can be placed. However, the question remains: how to find these configurations? For example, finding a configuration of queens is not that simple. Especially if you need to place, for example, \(20\) queens on a \(20 \times 20\) board. It is not easy to do this manually (try it!), nor is it easy to write a program for this task. At the same time, explicit configurations of \(n\) queens on an \(n \times n\) board are known for all \(n \ge 4\). For example, if \(n\) is an even number that does not leave a remainder of \(2\) when divided by \(6\), then the following configuration will work: for all \(1 \le i \le n/2\), place queens in the cells \((i, 2i)\) and \((n/2+i,2i-1)\).