Advertisement

A Mathematician Has Solved a 150-Year-Old Chess Problem About Queens

How many queens can fit on a board without attacking one another?

Get your chessboard out, prepare to look at it for a long time, and let us present you with a 150-year-old challenge: Could you arrange eight queens on a chessboard in such a way that none of them are attacking each other? Let's say this is conceivable, how many ways are there to do it?

This is the first form of a mathematics problem known as the n-queens problem. In 1848, a German chess magazine published the first 8-by-8 chessboard problem, and by 1869, the n-queens dilemma has emerged. Since then, mathematicians have produced many results on n-queens, and now, Michael Simkin, a postdoctoral fellow at Harvard University's Center of Mathematical Sciences and Applications, has all but solved this problem, proving for the first time a result that had previously been only guessed at using computer simulations, according to Quanta Magazine

Instead of asking how many ways there are to position eight queens on a conventional 8-by-8 chessboard (where there are 92 potential working configurations), the problem asks how many ways there are to place n queens on an n-by-n board. This might be 50 queens on a 50-by-50 board, for example.

Simkin proved that there are roughly (0.143n)n configurations for big chessboards with a large number of queens. This means that, on a million-by-million board, there are approximately 1 million ways to arrange 1 million non-threatening queens, followed by around 5 million zeros!

But how did he manage to find that? By keeping track of the number of spaces that were not under attack after the position of each additional new queen's position was revealed, Simkin was able to calculate a maximum number of configurations. Therefore, he concluded that he had nearly discovered the exact number of n-queens configurations because this maximum figure matched his minimum one almost completely, his proof providing the 150-year-old challenge a long-awaited clarity.

Advertisement

While this is not to say that mathematicians will stop toying with this problem in an attempt to learn more about it, Simkin's conclusion has most definitely removed most of the dust and mystery that clouded numerous people's minds.

Follow Us on

Stay on top of the latest engineering news

Just enter your email and we’ll take care of the rest:

By subscribing, you agree to our Terms of Use and Privacy Policy. You may unsubscribe at any time.