Mathematician cracks 150-year-old chess problem

A standard 64 square chess board.

(Image credit: Tomasz Bobrzynski via Getty Images.)

A chess problem that has stumped mathematicians for more than 150 years has finally been cracked.

The n-queens problem began as a much simpler puzzle, and was first posed in an 1848 issue of the German chess newspaper Schachzeitung by the chess composer Max Bezzel. It asked how many ways eight rival queens — which are the most powerful pieces on the chessboard and capable of moving any number of squares horizontally, vertically and diagonally — could be positioned on a standard 64-square board without any queen attacking another.

The answer, revealed just two years later, was that there were 92 configurations that kept the eight queens from each other's throats, with all but 12 of the solutions being simple rotations and reflections of each other. But in 1869, an even more perplexing iteration of the problem was asked by the mathematician Franz Nauck: Instead of configuring eight queens on a standard 8-by-8 board, what about 1,000 queens on a 1,000-by-1,000 board? What about a million, or even a billion?

Simkin took nearly five years to find this close approximation of an equation. Mathematicians usually solve problems by finding ways to break them into more manageable chunks. But because queens placed closer to the center of a board can attack many more squares than queens at the edges can, the n-queens problem is highly asymmetrical — and, therefore, stubbornly resistant to simplification.

Collaborating with Zur Luria, a mathematician at the Swiss Federal Institute of Technology in Zurich, Simkin initially simplified the task by considering a more symmetrical "toroidal" version of the problem, in which the edge squares wrap around the board to form a donut-shape. This arrangement enables queens to disappear at the top left and reappear at the bottom right, for instance. It also means that no matter where they are placed, each queen can attack the same number of squares as its counterparts.

By using the toroidal board as a first approximation, the two mathematicians next applied a strategy called a "random greedy algorithm" to the problem. They placed a queen at random, blocking off all the squares it attacked; then the next queen would be selected to sit on the remaining spots, with its attacking squares blocked off in turn. The pair continued doing this over multiple configurations until they found a rough lower bound — or lowest possible number — on the number of configurations of n queens on a toroidal board.

But their estimate was far from perfect. The wraparound nature of the board prevented them from finding the last few queen positions in some configurations. After dropping the problem for a few years, the duo returned to it with the idea of adapting their algorithm to a regular board, which provided more hiding spots for the final queens than the toroidal board. By adapting the random greedy algorithm to a standard, non-toroidal board, the pair somewhat improved the accuracy of this lower-bound estimate.

To solve this problem, Simkin realized he would need to adapt the algorithm. Because most of the viable configurations on a standard board had more queens at the board's edges — where they attacked fewer squares — than at its center, Simkin refined the random greedy algorithm by weighting the squares. Instead of his algorithm assigning queens randomly, it preferentially placed queens in spots that would branch out to the highest number of possible configurations. This allowed Simkin to focus on how many queens would occupy each board section and find a formula for a valid number of configurations, thus improving the accuracy of the lower-bound guess even further.

But finding the lower bound of a number still leaves an infinite set of numbers bigger than that. To really get to the solution, Simkin needed to find an upper bound. To solve this second half of the problem, he turned to a strategy called the "entropy method", which involved keeping note of the number of squares not under attack after a new queen was placed on the board. Using this method, he produced a maximum bound formula that spat out a number that almost perfectly matched the number for his lower bound; Simkin concluded that he'd actually struck the formula close to dead-on.

Ben Turner is a U.K. based writer and editor at Live Science. He covers physics and astronomy, tech and climate change. He graduated from University College London with a degree in particle physics before training as a journalist. When he's not writing, Ben enjoys reading literature, playing the guitar and embarrassing himself with chess.