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?
Related: 9 equations that changed the world
What was once a relatively simple puzzle had become a much deeper math problem — one that required the discovery of a general rule for the number of ways to position any number (represented as "n") of queens on an n-by-n board.
Now, Michael Simkin, a mathematician at Harvard University's Center of Mathematical Sciences and Applications, has come up with an almost-definitive answer.
On an enormous n-by-n board, there are approximately (0.143n)^n ways to place n queens so that none can attack each other. That means that on a million-by-million board, the number of nonthreatening configurations that 1 million queens can be arranged into is roughly 1 followed by 5 million zeros.
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.
But their answer wasn't as clear cut as they hoped — the random greedy algorithm works best on symmetrical problems, where every board square provides the same attacking advantage as any other. This isn’t the case for a standard board, where edge squares have much less ability to attack than squares in the center.
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.
"If you were to tell me, 'I want you to put your queens in such-and-such way on the board,' then I would be able to analyze the algorithm and tell you how many solutions there are that match this constraint," Simkin said in a statement. "In formal terms, it reduces the problem to an optimization problem."
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.
Future work may try to squeeze the two bounds even closer together, but Simkin, having gotten closer than anyone before him, is content to leave this challenge for someone else to conquer.
"I think that I may personally be done with the n-queens problem for a while," Simkin said. "Not because there isn't anything more to do with it, but just because I've been dreaming about chess and I'm ready to move on with my life."
Simkin published his work, which has not yet been peer-reviewed, to the preprint database arXiv.
Originally published on Live Science.
