The n-queens problem is about finding how many different ways queens can be placed on a chessboard so that none attack each other. A mathematician has now all but solved it.
Samuel Velasco/Quanta Magazine
Leila Sloman
Contributing Writer
September 21, 2021
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.
The symmetry of the toroidal board gave Simkin and Luria a foothold on the problem. But the toroidal version trades freedom for symmetry, ultimately tripping them up. On the classic board, most queens attack fewer than 27 spaces, which leaves more flexibility for building a configuration.
“The nooks and crannies of a real chessboard turn out to really help,” said Eberhard.
Simkin and Luria’s progress on the toroidal problem eventually stalled when they couldn’t find room for the last few queens in a given configuration. Having hit a wall, they moved on to other projects. But eventually, Simkin recognized that the approach that had failed for the toroidal problem was actually well suited to the normal chessboard.
“Two, three years after we had given up on it, I realized that for the classical problem, actually this is much easier,” said Simkin.
So Simkin and Luria tried to finish up their configuration on a normal chessboard (of any dimension). They found they could usually succeed by adjusting some of the pieces they’d already placed.
“You can just move a couple of queens around, stick two new queens in and take one old queen out,” explained Nick Wormald of Monash University.
But the lack of symmetry in the classic problem did come back to bite the researchers. The random greedy algorithm treats every space on the board equally and is best suited for highly symmetric problems where every square is the same. When queens are placed at random on a standard board, the algorithm doesn’t distinguish between the center square and a side square.
Due to this limitation, Simkin and Luria only ended up improving the known lower bound for the problem. They posted their results last May.
But Simkin kept thinking about the question, even after he moved from Israel to Boston last fall after completing his doctorate at the Hebrew University of Jerusalem. Eventually it dawned on him that he could adapt the random greedy algorithm to the asymmetric environment of the standard n-by-n chessboard. His key realization was that queens in an n-queens configuration were far more likely to occupy certain squares than others — so that it didn’t make sense to use the strategy he and Luria had used in which they chose every space with equal likelihood.
The nooks and crannies of a real chessboard turn out to really help.
Sean Eberhard, the University of Cambridge.
“I realized you can actually use these asymmetries to your advantage,” he said.
Because queens in the middle of the board attack the most spaces, most configurations feature more queens on the side of the board than near the center. Once a board has even 100 or so spaces along each side, Simkin found that these effects started to overwhelm other possibilities. Almost all the configurations have their queens distributed in a particular way, with fewer queens near the middle of the board and more along the sides. Simkin just needed to figure out the exact weights to assign each square when assigning queens at random.
“Let’s say you take all the queen arrays and you put them one on top of the other. Then you ask: How often is this particular position occupied?” said Nati Linial, a professor at the Hebrew University and Simkin’s doctoral adviser.
To understand roughly how the queens would be arranged, Simkin broke the n-by-n chessboard into sections, each made up of thousands of squares. Then, instead of specifying exactly which spaces on the chessboard had queens, he looked at the bigger picture: How many queens are in each section?
Once he figured out how to allocate queens by section, he returned to the techniques he and Luria had used. Only this time he could wield them more precisely: Rather than putting queens down completely randomly, he chose spaces where there were more queens more often. This allowed him to determine a formula for the minimum number of valid configurations.
Finally, Simkin proved that this formula was more than just a minimum — that it was nearly an exact description — by using a strategy known as the entropy method.
Imagine that you have a valid n-queens configuration, and you want to share it with someone. If the other person knows roughly what a configuration looks like, how much more information do you need to share before they can reconstruct it precisely?
Simkin was able to calculate a maximum number of configurations by tracking the number of spaces not under attack after the position of each additional new queen was revealed. This maximum value matched his minimum one almost perfectly, allowing Simkin to conclude that he’d just about pinpointed the actual number of n-queens configurations. His proof brought long-sought clarity to the classic problem.
Mathematicians will probably continue playing with this problem — trying to squeeze these bounds even closer together, though Simkin’s result has now taken most of the mystery out of the problem.
It’s “just about as realistic as you could hope for,” said Eberhard.
But the techniques in Simkin’s paper could prove useful for studying other questions as well. In fact, last week Candida Bowtell and Peter Keevash of the University of Oxford used similar ideas to find an analogous solution for the toroidal n-queens problem. The paper is so new it has not been fully vetted yet. And there are many other open problems in combinatorics that could benefit from the ideas Simkin used.
“The interesting things are the methods,” said Simkin. “We’re constantly looking to make our tools stronger. I hope that I’ve succeeded in doing that here.”
No comments:
Post a Comment