![\"\"](\"https:\/\/lh6.googleusercontent.com\/laXz0DGTb0B2TH7VYg65GqHuWjDU4MdHciJWNTdcK25Fgm3g3MKKMlOgL5ru9oiVDhOLjU3PAccu-8Fd7s9g6o8AAKKyvQxNl5XdzgGRdbKK2CFG4jlYh1I5lc4oD9fFoj3DsPTJ=s0\")
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:<\/p>\n\n\n\n
![\"\"](\"https:\/\/lh6.googleusercontent.com\/9j8kbaBXi03EGA1YZmwEaWu7601miNssmVAFoCLuP6v9uS7KnzOMgxdE8wVXIFpMKp0ZCpei8hzjTCOq5-lyqjgw9GdPHEMH7LVOkP-b8jGFORMrGms1v3KjzQv8PXtcfKGfUZQm=s0\")
Also, a queen can capture any piece that\u2019s 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?<\/p>\n\n\n\n
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<\/em> 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\u2014or n <\/em>queens\u2014on an n\u00d7n chessboard.<\/p>\n\n\n\n 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\u2019s Center of Mathematical Sciences and Applications, has this problem figured out; their solution can be found in preprint over on arXiv.<\/p>\n\n\n\n In his study of the n-queens problem, Simkin proved that there are approximately (0.143n)n<\/sup> configurations for some n number of queens on an n\u00d7n chessboard. In the case of a hundred non-attacking queens on a 100\u00d7100 chessboard, there would be around 3.42\u00d710115<\/sup> different configurations. For a million queens on a chessboard a million rows wide and a million columns tall, there would be around 1.09\u00d7105155336<\/sup> configurations\u2014that\u2019s a one followed by at least five million zeros.<\/p>\n\n\n\n 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 \u201csimplifying\u201d the situation. Thing is, the n-queens problem didn\u2019t seem to have a pattern to its solution, meaning Simkin struggled to search for answers to his problem.<\/p>\n\n\n\n Even after collaborations with fellow mathematicians, like Swiss Federal Institute of Technology Zurich mathematician Zur Luria, they could only figure out the \u201clower bound<\/em>\u201d of the solution, which was also put out on preprint on arXiv earlier this year<\/a>. In that case, they had to start with a \u201ctoroidal<\/em>\u201d chessboard that wraps around itself, so a piece that moves to the extreme right just goes around to the left instead.<\/p>\n\n\n\n Simkin eventually landed on a realization after pondering on the fact that queens on an n\u00d7n chessboard are more likely to occupy some squares more than others, given the clause that queens should not be able to attack each other.\\<\/p>\n\n\n\n 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<\/em> to narrow down the maximum number of configurations. It was there where he discovered that the two values almost perfectly matched\u2014meaning he actually managed to compute a nearly exact expression for the number of n-queens configurations. And thus, the (0.143n)n<\/sup> solution was born.<\/p>\n\n\n\n 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 \u201calmost perfectly\u201d matching, other mathematicians will most likely attempt the problem as well, if only to further close the gap between the maximum and minimum values.<\/p>\n\n\n\n In the words of Simkin: \u201cThe interesting things are the methods. […] We\u2019re constantly looking to make our tools stronger. I hope that I\u2019ve succeeded in doing that here.\u201d<\/p>\n\n\n\n Finally, if you\u2019re still curious, there are 92 different configurations for eight queens in a normal chessboard where no queens can attack another.<\/p>\n\n\n\nReferences<\/h2>\n\n\n\n
![\"\"](\"https:\/\/lh5.googleusercontent.com\/a_Q1cfgFsO_v9DLsknOs1ZzYVXoJCx-91qhvofXQ4JnbGlXzGLww3t5izMEt_aiVmECTVJnOwKjT5xGTM0XoicjjABGAw_HxkaFBdPlnpWYtIKcm47cJZS7uwpeSIqu_8yyU7USm=s0\")