Constructions, bounds, and algorithms for peaceable queens

The peaceable queens problem asks to determine the maximum number a (n) such that there is a placement of a (n) white queens and a (n) black queens on an n n chessboard so that no queen can capture any queen of the opposite color. In this paper, we consider the peaceable queens problem and its variant on the toroidal board. For the toroidal board, we provide new upper and lower bounds. Somewhat surprisingly, our bounds show that there is a sharp contrast in behaviour between the odd torus and the even torus. Our lower bounds are given by explicit constructions. For the upper bounds, we formulate the problem as a quadratic optimization problem with at most 70 variables, regardless of the size of the board. We solve our quadratic program exactly using modern optimization software. Our method is quite robust. For example, with very minor changes, it also provides upper bounds for the regular board. In particular, we show that a (n) 0. 1641n², for all n. This improves on the bound a (n) 0. 25n² of van Bommel and MacEachern. We also provide a local search algorithm and a software implementation which converges very rapidly to solutions which appear optimal. Our algorithm is sufficiently robust that it works on both the classical and toroidal boards. For example, for the classical board, the algorithm quickly finds the so-called Ainley construction. Thus, our work provides some further evidence that the Ainley construction is indeed optimal.