by Frederic Friedel
2/28/2022 – You know the problem: can you place eight queens on a chessboard so that now two queens threaten each other. There are 92 distinct ways of doing this. But how about on larger chessboards? For 27×27 board people have worked out that there are exactly 234,907,967,154,122,528 ways. Now a Harward mathematician Michael Simkin has come up with an almost-definitive answer for any number queens on a corresponding chessboard. Warning: his result can lead to dizziness and fainting spells.
It is known as the eight queens puzzle and was first brought up in a German chess magazine in 1848 – by one Max Friedrich William Bezzel. The problem entails placing eight queens on a chessboard so that no two queens threaten each other. The problem is fairly easy to solve – even a rank beginner should be able to construct a position that fulfils the requirement.
But how many solutions are there to the problem? Below are twelve fundamentally distinct solutions (source: Wiki). Most of the positions have eight variants which you can get by rotating them 90, 180, or 270° and reflecting each them. However, one of the fundamental solutions, the last one shown 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 soon conclusively established. But then the question arose: in how many different ways could queens be placed on larger boards? How many ways are there to place n queens on an n x n board so that no queen attacks another queen?
It turns out that there is no known formula to work this out. For a 9x9 board there are 352 distinctive ways, on a 10 x 10 board it 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 way to place the 27 queens so none attacks any other. Working it out was a very laborous task.
How about larger numbers, e.g. 1000 queens on a 1000 x 1000 board? Or a million queens on a million square board? 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 has worked on the problem for almost five years, applying breakthroughs from the field of combinatorics, which focuses on counting and problems of selection and arrangements. He calculated that there are about (0.143n)n ways the queens can be placed on giant n-by-n chessboards. This final equation doesn’t provide the exact number, but it is as close to the actual result as anyone can get right now. You can read about it in greater detail in this Harward Gazette story. There we learn what the formula implies:
On the extremely large chessboard with one million queens, for example, 0.143 would be multiplied by one million, coming out to about 143,000. That figure would then be raised to the power of one million, meaning it’s multiplied by itself one million times. The final answer is a figure with five million digits.
A bit of advice to our readers: do not try to list all these positions. It would take too long.
Many more articles
Simkin's paper on the solution is available on the preprint server arXiv.
or if you are really interested: listen to this one-hour discussion at the Copenhagen-Jerusalem Combinatorics Seminar:
No comments:
Post a Comment