The problem of n rival queens was first raised in 1869. The game consists of placing them on a board without attacking each other.
First thing: how can there be an unsolved chess problem since 1869? The n rival queens problem went unanswered for 150 years.
Its origins, with eight queens on the board
The n-queens problem started out as a much simpler puzzle and was first stated in an 1848 edition of the German chess journal Schachzeitung by chess expert Max Bezzel. In your column, I ask: In how many ways can eight rival queens be placed on a standard 64-square board without one queen attacking another?
Remember that the queen in chess is the most versatile piece and therefore the most powerful. It can move in any direction, as many spaces as the player wants, horizontally, vertically and diagonally. So putting eight rival queens on a board, without any of them attacking another, is complex enough.
Two years to get an answer
The answer, revealed just two years later, was that there were 92 configurations that kept the eight queens away from each other. All solutions except 12 are simple rotations and changes between parts.
But in 1869, mathematician Franz Nauck came up with an even more intriguing iteration of the problem: Instead of putting eight queens on a standard 8-by-8 board, how about 1,000 queens on a 1,000-by-1,000 board? How about a million, or even a billion?
What was a relatively simple puzzle became a much deeper mathematical problem, requiring the discovery of a general rule for the number of ways to place any number (represented as “n”) of queens on an n-by board. .
The problem had been unsolved for 150 years.
On a million-per-million board
Michael Simkin, a mathematician at the Center for Mathematical Sciences and Applications at Harvard University, presented a almost definitive answer.
On a huge n by n board, there are approximately (0.143n)^n ways to place n queens so that none can attack each other. This means that on a million-per-million board, the number of non-threatening configurations that 1 million queens can be arranged into is about 1 followed by 5 million zeros.
It took almost five years for Simkin to find that approximation. The mathematician explains the process to find the solution in a launch .
It may interest you:
In how many ways can a game of chess be played?
No human can beat AlphaZero