if you have For a few games of chess at home, try the following exercises: Arrange 8 queens on the board so that they do not attack each other. If you succeed once, can you find a second arrangement? one third? How many are there?
This challenge has a history of more than 150 years.This is the earliest version of a mathematical problem called n-The solution to the queen problem Michael Simkin, A postdoctoral researcher at Harvard University’s Center for Mathematical Sciences and Applications, Zero In a paper published in July.The question is not to place 8 queens on a standard 8×8 chessboard (there are 92 different configurations), but how many ways to place them n Queen n-go through-n board. This could be 23 queens on a 23 × 23 board-or 1,000 on a 1,000 × 1,000 board, or any number of queens on a board of the corresponding size.
“It’s easy to explain to anyone,” said Erica Roldan, Researcher Marie Skłodowska-Curie at the Technical University of Munich and the Swiss Federal Institute of Technology Lausanne.
Simkin proved that for a huge chessboard with a large number of queens, there are approximately (0.143n)n Configuration. Therefore, on a one-millionth chessboard, the number of ways to arrange 1 million non-threatening queens is approximately 1, and then approximately 5 million zeros.
The original question on the 8×8 chessboard first appeared in the German chess magazine in 1848. By 1869, n-The queen question follows.Since then, mathematicians have produced a large number of results n-Queen. Although previous researchers used computer simulations to guess what Simkin found, he was the first to actually prove it.
“He is basically sharper than anyone before,” said Sean Eberhard, Postdoctoral fellow at Cambridge University.
An obstacle to solving the problem nThe problem with -queens is that there is no obvious way to simplify it. Even on a relatively small board, the potential number of queens can be huge. On a larger board, the amount of calculation involved is staggering. In this case, mathematicians usually want to find some potential patterns or structures that enable them to break the calculations into smaller pieces that are easier to handle.But the n-The queen problem does not seem to be any problem.
“One thing worth noting about this issue is that, at least without careful consideration of it, there doesn’t seem to be any structure,” Eberhard said.
This is because not all spaces on the board are equal.
To understand why, again imagine building your own configuration of eight queens. If you place the first queen close to the center, it will be able to attack any space on its row, column, or two longest diagonals on the chessboard. This leaves 27 restricted areas for your next queen. But if you put your first queen on the side of the board, it will only threaten 21 spaces, because the related diagonal is shorter. In other words, the center square and the side squares are different-therefore, the chessboard lacks a symmetrical structure that might make the problem easier.
The reason for this lack of structure is that when Simkin visited Zur Luria, a mathematician at the Swiss Federal Institute of Technology in Zurich four years ago, to collaborate on this problem, they initially solved the more symmetrical “ring” problem. n-Queen question. In this modified version, the chessboard “wraps” itself on the edge like a ring: if you fall to the right, you will reappear on the left.
Due to its symmetry, the ring problem seems simpler. Unlike the classic chessboard, all diagonals have the same length, and each queen can attack the same number of spaces: 27.
Simkin and Luria tried to build a configuration on a ring board using a two-part recipe. At each step, they randomly place a queen and choose any space with equal possibilities as long as it is available. Then they sealed off all the spaces it could attack. By tracking how many options they have at each step, they hope to calculate a lower limit-the absolute minimum of the number of configurations.Their strategy is called Random Greedy Algorithm, and it has been used to solve many other problems in the following areas Combinatorics.