Queens are vicious in chess, as they are on RuPaul’s Drag Race. They march up and down the board, taking out whichever enemy piece poses a threat in whichever direction they damn well please – while pawns can only move forward one step at a time, bishops can move diagonally, and knights can do that weird one-step-this-way-two-steps-that-way thing, the queen can move in any direction as far as she wants. In fact, the only piece that can match a queen’s strength is… another queen. So, given an eight-by-eight chessboard, is it possible to place eight queens in such a way that any other queen can attack none of them?
The eight-queen conundrum was initially published in a German chess magazine in 1848, and the exact solution was discovered just a few years later. Not only is the challenge entirely feasible, but it also turns out that there are 92 possible solutions. However, chess players appear to be agents of disorder, and an updated version of the problem arose in 1869: given a large chessboard (1,000 × 1,000 squares or more), how many ways can 1,000 queens be arranged without putting any in jeopardy?
After more than 150 years, a solution has been discovered. “If you told me I wanted you to put your queens on the board in this way,” Michael Simkin, a postdoctoral fellow at Harvard University’s Center for Mathematical Sciences and Applications, explained, “I’d be able to analyze the algorithm and tell you how many solutions there are that match this constraint.” “It reduces the problem to an optimization problem in formal terms.”
Simkin determined that for n queens on an n-by-n board, there are roughly (0.143n) n configurations of queens – an object Simkin names “queenons” in the study – that satisfy the conditions in a newspaper, which is accessible as a preprint on the arXiv. For example, on a 1,000 by 1,000 square chessboard, there are roughly (0.143 1000)1,000 = 1431,000 possible ways to place 1,000 queens that meet the bill – a number with over 2000 digits.
Simkin’s result is not a perfect answer to the problem, but it is the best we have right now. There is a reason the n-queens issue has remained unresolved for so long: despite the invention of combinatorial tools like random greedy algorithms and the Rödl nibble (both actual things, not jokes), none of them are powerful enough to solve n-queens on their own. The n-queens problem has remained difficult for two reasons, according to Simkin’s article.
“The first is that the limitations are asymmetric: Some board positions are more ‘threatening’ than others because the diagonals vary in length from 1 to n. This makes analyzing nibble-style arguments challenging. Furthermore, the limitations are irregular: Some diagonals in a complete layout contain a queen, whereas others do not. This makes the entropy method difficult to use.”
Simkin used a hybrid approach to determine the upper bound: he built a randomized technique to get a lower bound on the number of arrangements, and then coupled it with another common method to get the upper bound. He discovered that those two calculations yielded very similar answers, resulting in a relatively narrow region of the number line where the real answer could be determined. “There are two parts to the [lower bound] algorithm: a random phase in which the majority of the queens are placed on the board, and a rectification phase in which a limited number of alterations are performed to produce a complete configuration,” Simkin stated. “The entropy method is the fundamental tool for proving the upper bound […].”
The answer to the n-queens problem has long sought by chess lovers and Simkin himself, who has been working on it for nearly five years, according to him. He believes he has finished with the puzzle for now, though he “wonders[s] whether comparable methods might succeed in obtaining more accurate estimations.” “I suppose I’m done with the n-queens problem for the time being,” he added, “not because there’s nothing else to do with it, but because I’ve been dreaming about chess and I’m ready to go on with my life.” He continued, “I still appreciate the challenge of playing.” “But math, I suppose, is more forgiving.”
