Harvard mathematician solves 150-year-old chess problem


It is known as the Eight Queens Puzzle and was first mentioned in a German chess magazine in 1848 – by a certain Max Friedrich William Bezzel. The problem is to place eight queens on a board so that no queen threatens each other. The problem is quite easy to solve – even a rank newbie should be able to build a position that meets the requirement.

But how many solutions are there to the problem? Here are twelve fundamentally distinct solutions (source: wiki). Most positions have eight variations that you can achieve by rotating them 90, 180, or 270° and mirroring each one. However, one of the fundamental solutions, the last presented below, is identical to its own 180° rotation, and has only four variants.

So it turns out that the total number of distinct solutions is 92, as was quickly conclusively established. But then the question arose: how many different ways could queens be placed on larger boards? How many ways are there to place n queens on an nxn board so that no queen attacks another queen?

It turns out that there is no known formula for solving this problem. For a 9×9 array there are 352 distinct lanes, on a 10 x 10 board is 724. The largest board for which an exact solution has been worked out is the 27×27 board. There are exactly 234,907,967,154,122,528 different ways to place the 27 queens so that none attack the others. Developing it was a very laborious task.

How about bigger numbers, for example 1000 queens on a 1000 x 1000 board? Or a million queens on a board of a million squares? It was a problem that fascinated mathematicians. In 2021, Michael Simkin found a way to calculate the result for very large numbers of n. He worked on the problem for nearly five years, applying breakthroughs from the field of combinatorics, which focuses on counting and selection and arrangement problems. He calculated that there are approximately (0.143not)not ways queens can be placed on giant n-by-n chessboards. This final equation doesn’t provide the exact number, but it’s as close to the actual result as anyone can get right now. You can read about this in more detail in this story from the Harvard Gazette. There we learn what the formula entails:

On the extremely large chessboard with a million queens, for example, 0.143 would be multiplied by a million, which would be approximately 143,000. This figure would then be raised to the power of a million, which means it is multiplied by itself a million times. The final answer is a five million digit number.

A little advice to our readers: do not try to list all of these positions. It would take too long.

Read also


Comments are closed.