The mathematical problem of the chess queens that a Harvard scientist solved after 150 years without a solution

It is very likely that when the German chess player Max Bezzel conceived the problem of the eight queens in 1848, he did not imagine the turns that his approach would take.

Over time, it gave way to queens problemwhich has had many mathematicians (and computers) racking their brains for a solution.

“Bezzel actually would have liked to study mathematics, but his friends advised him against it, ‘because the prospects for a mathematician in Bavaria were dire at the time,’” Hans Siegfried wrote in a short biography.

He became a lawyer, but he did not abandon his passion for chess and mathematics and that is how the famous problem involving the most powerful piece on the board arose.

A new chapter on the n queens problem was written by someone who confesses to not being very good at chess.

On January 21, The Harvard Gazettethe official press organ of Harvard University, reported that one of its mathematicians, Michael Simkin, had solved “to a large degree a 150-year-old chess problem.

And it is not certain when the problem of n-queens was raised for the first time, although everything indicates that it was before 1869.

At BBC Mundo we delve into this fascinating problem, its history and the solution that the scientist reached after five years turning it around.

What is the problem about?

Bezzel “could be considered one of the world’s first chess masters,” wrote Max Lange, another German chess great, in an 1860 book.

But beyond his prowess in that game, Bezzel distinguished himself by posing ingenious and complex problems.

“It was the mathematical side of chess that fascinated him,” Siegfried wrote on the website. Ansbach Chess Club.

This is how he proposed, in a publication on chess, the problem of How many ways can eight queens be placed on an 8 x 8 board? squares without meeting each other.

The queen can move as many squares as she wants in a linear way, either horizontally, vertically or diagonally.

They say that the problem became so popular that even the extraordinary mathematician Carl Friedrich Gauss tried to solve it.

But it was Franz Nauck, in 1850, who enunciated the solution: the eight queens can be placed in 92 ways.

That is the first version of the problem that was generalized as the problem of the n queens and that Simkin explains to BBC Mundo like this:

“Suppose n is a natural number, like 1,2,8,100 or a million. Now imagine a chessboard with n rows and n columns.

In how many ways are there to place n queens on the board so that there are not two that threaten each other each?

In other words, how many ways are there to place n queens on the board so that there is one queen in each row, one queen in each column, and no more than one queen on each diagonal?

The challenge captivated him.

The time had come for the queens

For Simkin, the approach has “nice features”, it can be quickly explained to almost anyone, “even non-mathematicians”, and that is something “unusual” when dealing with problems of this type.

He emphasizes that it is an example of “combinatorial design theory” and given the advances in probabilistic combinatorics, it seemed to him that “it was the right time to attack the problem of the queens”.

He says that he never decided to focus on the problem until he knew he had solved it.

At that time, he rushed to write it and the result was published in July 2021, in the academic article The number of n-queens configurations (“The number of configurations of n queens”).

“The problem had been going around in my head for about five yearsbut I had not progressed much and had concentrated on other projects”.

After completing his Ph.D. in 2020, he moved with his family from Israel to Boston to take up a postdoctoral position at Harvard.

In the midst of a pandemic, without much opportunity to socialize, the n queens gave him a new wink.

“Most of the work was just learning the newest techniques in probabilistic combinatorics,” not really realizing that learning them would actually solve the problem. “That came later.”

In addition to realizing that it was feasible to “attack the problem,” he had to “struggle to get a great deal of technical detail right” to enable him to write and publish “the proof.”

the eureka moment

The mathematician says that the “eureka” moment came when he realized “the need to understand where the queens ‘live’ on the board” and it happened when he was going down Wachusett Mountain, in Massachusetts.

He had gone up with his wife and daughter, but when it was time to go down, the girl was very tired and Simkin left for the car.

“As I walked alone and reflected, I realized that the main obstacle in previous attempts it was to assume that the queens were evenly distributed on the board”.

“And actually, they’re not.”

He “finally” understood that the key to counting the number of n-queens setups is to first understand what they “look like”.

“Are the queens generally evenly distributed on the board? Are they grouped in the middle? In the corners? To the sides?”

“For every possible pattern of how the queens might be placed on the board, I calculated the number of configurations in which the queens fit that pattern. Thus, the problem becomes: What is the pattern that allows the largest number of positions?

“This is what computer scientists call a convex optimization problem. In particular, you can use a computer to solve it.”

The solution

Simkin calculated that for huge chessboards (n by n squares) and with many queens, there are about (0.143n)^n ways to place the queens without any being threatened.

“Suppose we want to know how many configurations there are for 1,000,000 queens”, indicates the researcher.

That is, we want to determine the number of ways 1,000,000 queens can be placed on a 1,000,000 x 1,000,000 (square) board without attacking each other.

To calculate that number, which is an approximation, we must multiply 1,000,000 by 0.143 and the result, 143,000, we raise it to the power of 1,000,000.

“In other words, multiply 143,000 by itself a million times. The result is a very large number, with approximately five million digits”.

That would be roughly the number of configurations.

Do you want to see it with a smaller number? Let’s take the 1,000.

In an interview with BBC Mundo, Jesús Fernando Barbero, a mathematician and scientific researcher at the Spanish Higher Council for Scientific Research, made the calculation using the Simkin equation.

If we want to know approximately how many configurations there are for 1,000 queens, where is the n we put 1,000:

0.143 x 1000= 143 and we raise it to 1,000.

The teacher used his computer and this is the result he got:

“It gives me a huge number, more than 2,000 digits, but very close to the real value of the number of configurations there are for a board of size 1000×1000″.

“A step”

With the final Simkin equation an approximate result is reached, it is not the exact number of configurations, but it is the closest figure to the real number that can be obtained so far.

He himself indicates: “for problems of this type it is unusual to have an exact solution”.

For Barbero, “it is a huge advance” in what refers to the approach of the n-queens.

“These problems can have very simple statements, but then they can be horribly complicated.”

“problem was stuckit had been possible to understand how to solve it exactly up to number 27″.

“What he (Simkin) has found is a procedure for giving an expression that, while not exact, makes an error that is small.”

“And that is satisfying: suddenly you go from knowing nothing about the behavior of the number of solutions, to that problem of queens for large values, to having a fairly precise idea in quantitative terms about how many configurations there are for a board of size arbitrary”.

“In that sense, the problem is solved, not a final solutionone could hope to have an exact formula that would have the fantastic property that giving it the size of the board would give me the exact number of queen setups I can lay down.”

But while it’s theoretically possible to come close to a much more precise answer, Simkin’s achievement is praised by insiders.

“Basically, he has done it with a precision that no one had ever achieved before”, said Sean Eberhard, a postdoctoral researcher at the University of Cambridge, in an article in the journal how much. It is “as realistic as one can hope.”

Simkin says the reason the solution took “so long” is because it is based on recent advances in the field of mathematics known as probabilistic combinatorics, especially algorithm analysis. random computer.

Because it is important?

“Because of the methods that (Simkin) had to develop to solve a problem about which so little was known,” Barbero replies.

“Methods can have application out of context in which they have been conceived and you never know what problems can be solved with them, although there is not always a guarantee that they will work”.

For Simkin, the importance is a mixture of reasons:

“The main thing is what to do mathematics is the combination of creativitywhich is needed to generate new arguments, and rigor, which means that once you have proven a result, what you have in your hand is a piece of absolute truth. It cannot be refuted.”

But there is also the fact that with the problem of the n queens “it improves our understanding of random algorithms, which are used in almost all applications, for example in the machine learning or machine learning.

And there are also connections with other fields, such as circuit design.

“What would you say to someone who wanted to receive the baton from your hand and seek an even more exact answer?” I asked him.

“Good luck! Let me know how it goes. It would be very interesting to see what new ideas would be needed to improve the parameters.”

If any clues help, the mathematician summed up for us what he used: Random Algorithm Analysis, Probabilistic Combinatorics, Entropy, Functional Analysis, and Convex Optimization.

And although he says that he is a “terrible” chess player and that, for now, he will rest from the n queens, surely Max Bezzel would be very proud of him.