The game of chess has been around for at least 1,500 years, and has morphed in our current understanding from a war simulation to seemingly becoming a mathematics and logic puzzle to academics today.
With that context in mind, let’s take a step back from formal chess rules, and imagine a normal chessboard. For a refresher, the queen is the most powerful chess piece, and is capable of moving in a straight or diagonal line all the way across the board, like so:
Also, a queen can capture any piece that’s unfortunate enough to sit along its possible paths of movement. Now, with those in mind, imagine a scenario where you have eight (8) individual queens on a normal chessboard. How would you place them in such a way that no queens attack another? And how many arrangements of eight queens could you make out that allows this stalemate?
As it turns out, this very problem is pretty old, as it stretches back some 150 years. The thought experiment above is the simplest version of a conundrum known as the n-queens problem. There, instead of just eight queens sitting on a normal chessboard with eight rows and eight columns, the problem imagines some arbitrary number of queens—or n queens—on an n×n chessboard.
The original eight-queens problem was first devised in a German magazine back in 1848, followed by the introduction of the formal n-queens problem some 21 years later. Now, a mathematician by the name of Michael Simkin, a postdoctoral fellow from Harvard University’s Center of Mathematical Sciences and Applications, has this problem figured out; their solution can be found in preprint over on arXiv.
In his study of the n-queens problem, Simkin proved that there are approximately (0.143n)n configurations for some n number of queens on an n×n chessboard. In the case of a hundred non-attacking queens on a 100×100 chessboard, there would be around 3.42×10115 different configurations. For a million queens on a chessboard a million rows wide and a million columns tall, there would be around 1.09×105155336 configurations—that’s a one followed by at least five million zeros.
Figuring out the solution necessitated several hours of painstaking calculations, as the calculations needed to compute for the number of possible arrangements were staggering in amount. In cases like these, mathematicians often seek out patterns instead of raw numbers, as a way of “simplifying” the situation. Thing is, the n-queens problem didn’t seem to have a pattern to its solution, meaning Simkin struggled to search for answers to his problem.
Even after collaborations with fellow mathematicians, like Swiss Federal Institute of Technology Zurich mathematician Zur Luria, they could only figure out the “lower bound” of the solution, which was also put out on preprint on arXiv earlier this year. In that case, they had to start with a “toroidal” chessboard that wraps around itself, so a piece that moves to the extreme right just goes around to the left instead.
Simkin eventually landed on a realization after pondering on the fact that queens on an n×n chessboard are more likely to occupy some squares more than others, given the clause that queens should not be able to attack each other.\
Eventually, he ended up with a formula which he thought gave the minimum number of configurations; he then used what mathematicians call the entropy method to narrow down the maximum number of configurations. It was there where he discovered that the two values almost perfectly matched—meaning he actually managed to compute a nearly exact expression for the number of n-queens configurations. And thus, the (0.143n)n solution was born.
Simkin hopes that the methods he devised to figure out the n-queens solution may help illuminate the path for other mathematicians working on problems with a similar structure. Of course, as the solution Simkin found was only “almost perfectly” matching, other mathematicians will most likely attempt the problem as well, if only to further close the gap between the maximum and minimum values.
In the words of Simkin: “The interesting things are the methods. […] We’re constantly looking to make our tools stronger. I hope that I’ve succeeded in doing that here.”
Finally, if you’re still curious, there are 92 different configurations for eight queens in a normal chessboard where no queens can attack another.
References
- Luria, Z., & Simkin, M. (2021). A lower bound for the $n$-queens problem. ArXiv:2105.11431 [Math]. http://arxiv.org/abs/2105.11431
- Simkin, M. (2021). The number of $n$-queens configurations. ArXiv:2107.13460 [Math]. http://arxiv.org/abs/2107.13460
- Sloman, L. (2021, September 21). Mathematician answers chess problem about attacking queens. Quanta Magazine. https://www.quantamagazine.org/mathematician-answers-chess-problem-about-attacking-queens-20210921/
- Sloman, L. (2021b, October 3). A mathematician answers a 150-year-old chess problem. Wired. https://www.quantamagazine.org/mathematician-answers-chess-problem-about-attacking-queens-20210921/
