First appearing in 1869, the “n-queens problem” has puzzled scientists for over 150 years.
Chess is an ancient game that originated in India and Persia, making its way to Southern Europe in the latter half of the 15th century. Despite its long history, chess still holds many mysteries, the most famous of which is the n-queens problem, which stems from a puzzle.
Chess is an ancient game that originated in India and Persia.
The puzzle is as follows: How many ways can 8 queens – the most powerful pieces on the board, capable of moving any number of squares horizontally, vertically, and diagonally – be placed on a standard 64-square chessboard without any queens being in each other’s way?
This puzzle first appeared in 1848, posed by master Max Bezzel in the chess magazine Schachzeitung in Germany. From the moment it was mentioned, the puzzle posed challenges not only to chess enthusiasts but also to mathematicians.
The answer was revealed two years later, stating there are 92 ways to arrange 8 queens on the chessboard, but in summary, there are only about 12 basic arrangements, as most of the remaining solutions are symmetrical to one another.
However, in 1869, a variant of the original puzzle was proposed by mathematician Franz Nauck, which was even more complex. The question posed: Instead of arranging 8 queens on a standard 8 x 8 board, what if there were 1,000 queens on a 1,000 x 1,000 board? Then 1 million, 1 billion…
What was once a relatively simple puzzle became a much deeper challenge, requiring the exploration of a general rule for the number of arrangements of any number (represented as “n”) of queens on an n x n grid.
The problem involves arranging queens on a chessboard such that piece A does not lie in the attacking path of piece B.
Only now, after more than 150 years, Michael Simkin, a mathematician at the Mathematical and Applied Sciences Center at Harvard University, has provided what is considered to be a near-exact answer to the problem.
Specifically, according to Simkin, on a gigantic n x n chessboard, there are approximately (0.143n) ^ n ways to arrange n queens so that no queen can attack another. This means that on a million x million board, the arrangements for 1 million queens can amount to a number with 5 million zeros.
It is known that Simkin spent nearly 5 years developing this approximate equation. His approach involved placing a queen randomly on the board and then blocking all squares that it could reach (including those vertically, horizontally, and diagonally). He then continued using an algorithm to position the remaining queens in a similar manner.
However, this algorithm is not perfect, as it works best on symmetrical problems where every square provides the same attacking advantage to the queens as any other square. This is not the case on a standard chessboard, where queens placed on squares near the edge have much less attacking capability than those in the center.
To address this issue, Simkin realized he would need to make further adjustments to the algorithm, but he is getting closer to conquering this challenge.
“I personally think I might solve the n-queens problem in some time,” Simkin stated. “Not because there is nothing left to do, but because I have always dreamed about variations of chess, and I am ready to continue pursuing my passion.”
