What is the minimum number of chess pieces of a given type needed to attack every vacant square of the board? The answer turns out to be 9 for kings, 5 for queens, 8 for bishops or rooks, and 12 for knights. The picture above shows some minimal solutions to the problem for kings, queens, bishops, and knights, and the placement shown for the bishops also works for rooks. Problems of this sort are called domination problems.
In the case of queens, it turns out that it is possible to solve the domination problem by placing the five queens on the long diagonal of the board. If we choose coordinates so that the bottom left square is (1, 1) and the top right square is (8, 8), then the three vacant diagonal squares in the picture have coordinates (1, 1), (3, 3), and (7, 7). The set of vacant positions, {1, 3, 7}, may appear somewhat random, but E.J. Cockayne and S.T. Hedetniemi proved in 1984 that the set of vacant positions in this problem always has the structure of a Salem–Spencer set consisting of all-odd or all-even numbers.
A Salem–Spencer set is a set of numbers with the property that the average of any two of the numbers is not in the set. (To put it another way, no three of the numbers form an arithmetic progression.) The set {1, 3, 7} is a Salem–Spencer set: the average of 3 and 7 is 5, which is not in the set; the same is true for the average of 1 and 3, and the average of 1 and 7. It is not obvious what this has to do with the chess problem, but the picture below may help explain.
The problem requires that the vacant square (3, 7), highlighted in magenta, must be attacked by one of the queens. However the squares (3, 3) and (7, 7) (highlighted in red and blue respectively) are both vacant, so the square (3, 7) cannot be attacked along a row or down a column. It follows that one of the queens must attack the square (3, 7) diagonally, namely the one at position (5, 5) highlighted in green; note that the squares (3, 7) and (5, 5) lie on a diagonal because 3+7=5+5. This explains why the average of 3 and 7 (i.e., 5) cannot lie in the set {1, 3, 7}, and therefore why the set {1, 3, 7} is a Salem–Spencer set. Notice also that the squares on the main diagonal are all dark squares, and any other square, like (3, 7), that can be diagonally attacked from a dark square must itself be a dark square. A point (x , y) is a dark square if and only if x and y are both even, or both odd.
It turns out that Salem–Spencer sets have practical applications in theoretical computer science, including in fast algorithms for matrix multiplication and the construction of zero-knowledge proofs. It is surprisingly easy to construct infinite Salem–Spencer sets, such as the one above, which starts 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31. This looks like a somewhat random sequence of numbers, but they make a lot more sense written in base 3, as shown below.
This is the sequence of numbers whose base 3 representations contain no occurrences of “2”. To prove that this is a Salem–Spencer set, we need to show that the sequence does not contain three different numbers a, b, and c with the property that a+c=2b. The base 3 representation of the number 2b would only contain 0s and 2s, because the base 3 representation of b contains only 0s and 1s. In order for the base 3 representation of a+c to contain only 0s and 2s, the 1s in the numbers a and c would have to occur in the same positions. This would mean that a=c, which is not the case.
Another type of chess problem along the same lines is the independence problem. Here, the goal is to place as many pieces as possible of the same type in such a way that they do not attack each other. (According to the rules of chess, two pieces of the same colour cannot actually “attack” each other, but this is how mathematicians talk.) It turns out, as illustrated above, that it is possible to place as many as 16 kings, or 8 queens, or 8 rooks, or 14 bishops, or 32 knights on the board.
In 1918, George Pólya proved that it is possible to place n queens on an n by n board without any two conflicting (i.e., “attacking each other”), provided that n is at least 4. He also considered what would happen if we identified the top and bottom edges of the board, and the left and right edges of the board, so that a queen could move off one side of the board and come back on the opposite side, like in a video game. (This is equivalent to playing chess on a torus.) In this case, it is still possible to place n queens on the board, so long as n is not a multiple of 2 or 3.
I found out about this problem from the recent paper Torus Queen Independence by Kada Williams. The paper proves many results about how many queens can be placed on a torus without conflict, and even considers what would happen in higher dimensions. One of the main results is that if n leaves a remainder of 2 or 10 when divided by 12, then it is possible to place n–1 queens on an n by n torus (i.e., a wraparound board) without conflict. The picture above shows the example of 9 queens placed on a 10 by 10 torus. The author also conjectures that, provided n is at least 3, it should always be possible to place n–2 queens on an n by n torus without conflict.
Picture credits and relevant links
The diagram of the queens on the 10 by 10 torus is from the paper by Kada Williams.
The diagrams of the domination and independence problems come from Wikipedia’s page on mathematical chess problems.
The meme image is folklore, and the other graphics are my own work.
The infinite Salem–Spencer set mentioned is sequence A005836 in the On-Line Encyclopedia of Integer Sequences
Salem–Spencer sets are named after Raphaёl Salem and Donald C. Spencer, who studied them in 1942.
Wikipedia has an article on George Pólya (1887–1985).
Substack management by Buzz & Hum.
Do the Salem–Spencer sets have any application or relation to Van der Waerden's theorem and Szemeredi's theorem?
I really enjoyed the connection with chess! Thank you for another post to learn from 👍👍😄