The peaceable queens problem is to determine the maximum number m such that one can place m queens of each colour on an n by n chessboard without any queens of opposite colours attacking each other. On an 11 by 11 chessboard, it is possible to do this with 17 queens of each colour, as shown above. Furthermore, 17 is the largest possible number that works on an 11 by 11 board.
It is possible to place 9 peaceable queens of each colour on an ordinary 8 by 8 chessboard. One such solution is shown above, and we can find others using the dihedral symmetry of the problem. What this means is that rotating the solution (by a multiple of 90°) also gives a solution to the problem, as does reflecting the solution in a mirror. Another way to find additional solutions is to change the colour of each of the pieces. Even taking into account all these symmetries, there are still 71 essentially different ways to place 9 peaceable queens of each colour on an 8 by 8 board.
If we take the configuration of 17+17 queens on the 11 by 11 board and place it on a larger board, it will still be the case that no two queens attack each other. This shows that if we increase n, the largest possible value of m will be the same or greater. This leads to the question of what happens asymptotically, meaning when n gets very large.
This problem was discussed by Stephen Ainley in his 1977 book Mathematical Puzzles. Using elementary geometry, it is easily checked that in the diagram above, 7/48 of the total grid area is shaded blue, and 7/48 of it is shaded red. By placing queens of one colour roughly in the blue area, and queens of the other colour roughly in the red area, Ainley showed that it is possible to find a value of m that is around 7n2/48 (about 0.1458n2) or maybe larger. For example, if n=20, then 7n2/48 is around 58.3, and it is indeed possible to place 58 queens of each colour on a 20 by 20 board without any two attacking each other, as shown below.
Many other people have worked on this problem, but even after nearly 50 years, nobody has made more than incremental improvements to Ainley’s original lower bound on m in terms of n. However, there have been generalizations in other directions, such as in the recent paper Constructions, bounds, and algorithms for peaceable queens by Katie Clinch, Matthew Drescher, Tony Huynh, and Abdallah Saffidine. The authors make significant progress on what happens in the peaceable queens problem with a toroidal board; in other words, a board in which the top edge wraps around to the bottom edge, and the left edge wraps around to the right edge, like in the classic video game Asteroids.
The picture above shows a lower bound construction (i.e., the analogue of the Ainley construction) for a 32 by 32 toroidal board. The solution for toroidal boards of odd size turns out to behave rather differently, and the picture below shows the corresponding lower bound construction for a 31 by 31 toroidal board. Both solutions somewhat resemble woven fabrics, in contrast to the large blobs of pieces appearing in Ainley’s construction. The authors prove that, for a toroidal board, m lies between 0.1339n2 and 0.1402n2 if n is large and even, and between 0.0833n2 and 0.125n2 if n is large and odd.
The authors do not improve on Ainley’s lower bound for the original (non-toroidal) problem, but they find a new upper bound showing that m is at most 0.1641n2, which is a significant improvement on the previously known bound of 0.25n2. The authors also provide algorithms to find good solutions to the problem. Their algorithms find Ainley’s solutions very easily, which provides further evidence that Ainley’s constructions are optimal.
Picture credits and relevant links
The right half of the top diagram comes from the 2004 paper Models and symmetry breaking for “Peaceable armies of queens” by Barbara M. Smith, Karen E. Petrie, and Ian P. Gent.
The two three-dimensional chess diagrams are by Michael De Vlieger. These appear in entry A250000 of the On-Line Encyclopedia of Integer Sequences, which gives the optimal bounds for the peaceable queens problem on an ordinary n by n board, for each value of n.
Entry A260680 of the OEIS gives the number of essentially different solutions for the maximum possible number of peaceable queens on an n by n board (which is where the number 71 came from).
The two monochrome grid diagrams come from the paper by Katie Clinch, Matthew Drescher, Tony Huynh, and Abdallah Saffidine.
I created the 8 by 8 chessboard using the tools at lichess.org. The graphic of the grid with the shaded blue and red areas is my own work.
Wikipedia has a page about the video game Asteroids.
Substack management by Buzz & Hum.
Interesting! I'm very familiar with the Eight Queens problem, but this is the first I've heard of gaggles of peaceable queens. I like the toroidal patterns. I'm somehow a bit surprised the solution doesn't come in integer form when it seems like an integer problem -- N rows and columns, N possible positions. But I'm a math tyro with little math intuition to call my own.
Chess is an ideal framing to explore mathematical analyses. Thank you for the post!