If you have a few chess sets at home, try the following exercise: Arrange eight queens on a board so that none of them are attacking each other. If you succeed once, can you find a second arrangement? A third? How many are there?
This challenge is over 150 years old. It is the earliest version of a mathematical question called the n-queens problem whose solution Michael Simkin, a postdoctoral fellow at Harvard University’s Center of Mathematical Sciences and Applications, zeroed in on in a paper posted in July. Instead of placing eight queens on a standard 8-by-8 chessboard (where there are 92 different configurations that work), the problem asks how many ways there are to place n queens on an n-by-n board. This could be 23 queens on a 23-by-23 board—or 1,000 on a 1,000-by-1,000 board, or any number of queens on a board of the corresponding size.
“It is very easy to explain to anyone,” said Érika Roldán, a Marie Skłodowska-Curie fellow at the Technical University of Munich and the Swiss Federal Institute of Technology Lausanne.
Simkin proved that for huge chessboards with a large number of queens, there are approximately (0.143n)n configurations. So, on a million-by-million board, the number of ways to arrange 1 million non-threatening queens is around 1 followed by about 5 million zeros.
The original problem on the 8-by-8 chessboard first appeared in a German chess magazine in 1848. By 1869, the n-queens problem had followed. Since then, mathematicians have produced a trickle of results on n-queens. Though previous researchers have used computer simulations to guess at the result Simkin found, he is the first to actually prove it.
“He basically did this much more sharply than anyone has previously done it,” said Sean Eberhard, a postdoctoral fellow at the University of Cambridge.
One barrier to solving the n-queens problem is that there are no obvious ways to simplify it. Even on a relatively small board, the number of potential arrangements of queens can be huge. On a larger board, the amount of computation involved is staggering. In this situation, mathematicians often hope to find some underlying pattern, or structure, that lets them break up the calculations into smaller pieces that are easier to handle. But the n-queens problem didn’t seem to have any.
“One of the things that is notable about the problem is that, at least without thinking very hard about it, there doesn’t seem to be any structure,” said Eberhard.
This stems from the fact that not all spaces on the board are created equal.
To see why, again imagine constructing your own eight-queens configuration. If you put your first queen near the center, it will be able to attack any space in its row, in its column, or along two of the board’s longest diagonals. That leaves 27 spaces off-limits for your next queen. But if you place your first queen along the side of the board instead, it threatens only 21 spaces, since the relevant diagonals are shorter. In other words, the center and side squares are distinct—and as a result, the board lacks a symmetric structure that might make the problem simpler.
This lack of structure is why, when Simkin visited the mathematician Zur Luria at the Swiss Federal Institute of Technology Zurich to collaborate on the problem four years ago, they initially tackled the more symmetric “toroidal” n-queens problem. In this modified version, the chess board “wraps” around itself at the edges like a torus: If you fall off to the right, you reappear on the left.
The toroidal problem seems simpler because of its symmetry. Unlike on the classic board, all the diagonals are the same length, and every queen can attack the same number of spaces: 27.
Simkin and Luria attempted to build configurations on the toroidal board using a two-part recipe. At each step, they placed a queen at random, choosing any space with equal likelihood as long as it was available. They then blocked off all the spaces that it could attack. By keeping track of how many options they had at each step, they hoped to calculate a lower bound—an absolute minimum for the number of configurations. Their strategy is called a random greedy algorithm, and it’s been used to solve many other problems in the area of combinatorics.
