In chess, as in RuPaul’s Drag Race, queens are fierce. They march up and down the board taking out whichever enemy piece poses a threat, doing so whichever way they damn well please – while pawns are doomed to only move forward one step at a time, bishops move diagonally, and knights have that weird one-step-this-way-two-steps-that-way thing they do, the queen can move in any direction as far as she likes.
In fact, the only piece as powerful as a queen is… another queen. So here’s a question: given a standard eight-by-eight chessboard, is it possible to arrange eight queens in a way that means none can be attacked by any other?
This problem, known as the eight-queens puzzle, was first posed in a German chess magazine in 1848, and the correct answer was discovered just a couple of years later. Not only is the challenge totally possible, but it also turns out there are 92 different ways to solve it.
However, chess players are agents of chaos, it seems, and in 1869 an updated version of the problem surfaced: say you have a huge chessboard, 1,000 by 1,000 squares or more – how many ways are there to arrange 1,000 queens without putting any in jeopardy?
Over 150 years later, an answer has finally been found.
“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,” said Michael Simkin, a postdoctoral fellow at the Center of Mathematical Sciences and Applications in Harvard University. “In formal terms, it reduces the problem to an optimization problem.”
In a new paper, available as a preprint on the arXiv, Simkin calculated that for n queens on an n by n board, there are approximately (0.143n)n arrangements of queens – an object Simkin labels “queenons” in the paper – that fulfill the requirements.
That means, for instance, that 1,000 by 1,000 square chessboard has approximately (0.143 × 1000)1,000 = 1431,000 different ways available to arrange 1,000 queens that fit the bill – that’s a number more than 2000 digits long.
Simkin’s result is not an exact solution to the problem, but it’s as close as we can get right now. There’s a reason the n-queens problem has stayed unsolved for so long: despite the development of combinatorial tools like random greedy algorithms or the Rödl nibble (both real things, not jokes), none are powerful enough to tackle n-queens alone.
“The n-queens problem has remained challenging for two reasons,” Simkin’s paper explains. “The first is the asymmetry of the constraints: Since the diagonals vary in lengths from 1 to n, some board positions are more 'threatened' than others. This makes the analysis of nibble-style arguments difficult. Additionally, the constraints are not regular: In a complete configuration, some diagonals contain a queen and some do not. This creates difficulties for the entropy method.”
So, Simkin adopted a hybrid method: he constructed a randomized algorithm to obtain a lower bound on the number of arrangements, and then combined it with another standard method to find the upper bound. Those two calculations, he found, gave remarkably close results – making the section of the number line where the true answer could be found very small indeed.
“The [lower bound] algorithm has two phases: a random phase, in which most of the queens are placed on the board, and a correction phase, in which a small number of modifications are made to obtain a complete configuration,” Simkin wrote. “[To] prove the upper bound […] the main tool is the entropy method.”
The solution to the n-queens problem is long-awaited both for chess fans and Simkin personally – he’s been working on it for nearly five years, he said. And while he “wonder[s] whether similar methods might succeed in obtaining more accurate estimates,” he says he’s done with the puzzle for now.
“I think that I may personally be done with the n-queens problem for a while,” he 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.”
“I still enjoy the challenge of playing,” he added. “But, I guess, math is more forgiving.”