In chess, the queen is arguably one of the most powerful pieces on the board. Unlike any other piece, the queen can move in the horizontal, straight, or oblique directions at will, and the number of tiles is unlimited.
The queen in chess has a very flexible move. | Image credit: Alma Cebrian via Wiki under CC BY-SA
Now you can think about the question: If you put 8 queens on a standard chessboard of 8 × 8 squares, how many arrangements would there be that would prevent them from attacking each other in one move?
This is also often referred to as the classic Eight Queens problem. It first appeared in a German chess magazine in 1848. After a few years, people found the answer to it, it was 92 kinds.
A solution to the Eight Queens problem. | Image design: MJJ
In 1869, a broader version of the Eight Queens problem emerged. People began to think about what if there were more queens on a larger board, for example, to put 1,000 queens on a 1,000×1,000-square-meter chessboard, or even 1 million queens on a 1 million-× 1 million-square-meter oversized board.
The expanded n queen problem can be summarized as, if you want to put n queens on an n× n grid chessboard, how many arrangements can make them unable to attack each other in one move?
Until the end of last year, a mathematician provided an almost certain answer. Michael Simkin, a mathematician at Harvard University, calculated that there are about (0.143n) ways to place queens so that they cannot attack each other on a board of n×n grids.
nThe "problem" of the Queen's question
In previous attempts to solve the n queen problem, many have used computer simulations to "guess" the answer. And Simkin wants to go back to mathematics to prove it.
One of the big obstacles to solving the n queen problem is that there is no obvious way to simplify it. Even in the case of a relatively limited board with a small number of pieces (i.e., n smaller), the number of potential arrangements for queens is large, not to mention a huge chessboard.
In this case, mathematicians often want to find some potential pattern or structure to break down the computation into smaller pieces that are easier to handle.
But for the n queen problem, there doesn't seem to be any structure. This is because not all spaces on the board are equal.
To understand this intuitively, we can look back at the Eight Queens problem. If you place the first queen near the center, it can attack the space of the row, column, or two long diagonal lines, that is, your next queen has a 27-block space exclusion zone.
Placing the first queen (red in the picture) near the middle of the checkerboard will give the next queen 27 positions of forbidden zones (green in the picture). | Image design: MJJ
But if you put your first queen on the edge of the chessboard, it will only threaten the 21-block space.
When the first queen (red in the picture) is placed next to the board, the next queen has only 21 blocks of forbidden area (green in the picture). | Image design: MJJ
In other words, the positions of the middle and edges are not equal, so the checkerboard lacks a symmetrical structure that makes the problem simple.
A few years ago, Simkin visited Zur Luria, a mathematician at ETH Zurich and a chess prodigy. They decided to start by working on a simpler symmetrical super-torus n queen problem, in which the checkerboard "rolls up" at the edges like a torus. It's understandable that if you fall out of the board from the right side, you're actually falling to the left.
The two collaborated and developed new technologies, and although no definitive answers were ultimately obtained, Simkin gained some accumulation from them.
Subsequently, he went on to return to the classic version of the problem. His final equation doesn't provide an accurate answer, but simply puts it, and this number is the closest you can get to the actual number at the moment. 0.143 represents the average level of uncertainty for the possible outcome of the variable, which is multiplied by n and then raised to the power of n to get the answer. This calculation is actually very amazing, you can simply try it, if n is 1 million, the resulting number will contain 5 million bits.
He was able to obtain this solution by understanding the basic patterns of how a large number of queens are distributed on these huge chessboards, such as whether they are concentrated in the middle or at the edges, and then applying well-known mathematical techniques and algorithms. Formally, he simplifies the problem to an optimization problem.
By focusing on those positions that were more likely to be occupied, Simkin figured out how many queens would be in each section of the board and came up with a formula to get an effective number of configurations. The result of the calculation is the so-called nether, i.e. the minimum number of possible configurations. With this number, he used a strategy known as the entropy method to look for the upper bound, the maximum number that could be configured.
In the end, it was found that the answer to the lower bounds almost exactly coincided with the answer to the upper boundary. Simply put, it suggests that the exact answer should be sandwiched between two boundaries in a relatively small mathematical space, which is about (0.143n) the method.
A test of patience and perseverance
Simkin, who has been working on the n queen's problem for almost 5 years, says it's a test of patience and perseverance.
But he was so interested in the problem because it could be applied in a field of mathematics known as combinatorics, which focuses on counting and selection and permutation problems.
Simkin has said that he himself is a very bad chess player. "I still really enjoy the challenge of playing chess, but I guess math seems more 'tolerant'," he says. ”
#创作团队:
Written by: Takeko
Typography: Wenwen
#参考来源:
https://news.harvard.edu/gazette/story/2022/01/harvard-mathematician-answers-150-year-old-chess-problem/
https://www.quantamagazine.org/mathematician-answers-chess-problem-about-attacking-queens-20210921/
http://www.math.utah.edu/~alfeld/queens/queens.html
#图片来源:
Cover image: Pixabay
First image: Pixabay