Harvard mathematician solves 150-year-old chess problem

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.

ChessBase 17 - Mega package ChessBase 17 - Mega package

ChessBase is a personal, stand-alone chess database that has become the standard throughout the world. Everyone uses ChessBase, from the World Champion to the amateur next door. It is the program of choice for anyone who loves the game and wants to know more about it.

More...

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. 

Also read

 

 


Editor-in-Chief emeritus of the ChessBase News page. Studied Philosophy and Linguistics at the University of Hamburg and Oxford, graduating with a thesis on speech act theory and moral language. He started a university career but switched to science journalism, producing documentaries for German TV. In 1986 he co-founded ChessBase.

Discuss

Rules for reader comments

 
 

Not registered yet? Register

arzi arzi 3/1/2022 07:23
To evilthough2:"Not everything in life must have practical use..."
Maybe everything in life must have also practical use...but we just don`t know that, yet. Infinity is a big thing.
Rambus Rambus 3/1/2022 07:19
I'll show you real world application - get him to Ukraine immediately to position the defensive garrison, using the minimum number of troops to cover the maximum area!
Zagliveri_chess Zagliveri_chess 3/1/2022 12:34
This family of algorithms is related to strength of encryption and associated keys.
Ruteger007 Ruteger007 3/1/2022 12:07
Some people have too much time on their hands...
evilthought2 evilthought2 2/28/2022 10:26
Theochessman, "OK, and what is the practical use of these kind of nonsense solutions to nonsense problems?"

Not everything in life must have practical use. For example, what's the practical use of a board game where you move pieces around, like chess? None whatsoever, except entertainment. Same answer to your question.
flachspieler flachspieler 2/28/2022 09:43
@theochessman: Let me speculate a little bit. Some techniques from
Simkin's toolbox may help to design better reactors for nuclear fusion.
But this is just my speculation.
Another application may be improved design of artificial protein molecules.

Ingo Althoefer (Full Professor of Discrete Applied Mathematics).
Theochessman Theochessman 2/28/2022 09:30
OK, and what is the practical use of these kind of nonsense solutions to nonsense problems?
flachspieler flachspieler 2/28/2022 08:20
@nirvana: Yes, it is a very asymptotic result. And it is a very deep one.
The approach in principle will help to understand several seemingly
unrelated problems.

Ingo Althoefer.
nirvana1963 nirvana1963 2/28/2022 08:14
I'm not a mathematician and maybe I don't understand the whole thing in all its aspects but the formula does not 'work' with n=8. If n=8, there are (0.143*8)^8 possible ways the queens can be placed, that is almost 3: not even close to the real solution of 92 possible ways. Does it mean the formula only works for very large numbers of n?
SermadShah SermadShah 2/28/2022 02:47
Hmmm, when I solved this puzzle I made a thumb rule i.e you have to put at-least one queen to one of these 8 squares, d1, e1, d8, e8, a4, a5, h4, h5. The 12 solutions presented in this article also confirm this.
1