Harvard mathematician answers 150-year-old chess problem

Credit: CC0 Public Domain

The queen is the most powerful piece on the chessboard. Unlike any other (including the king), it can move any number of squares vertically, horizontally, or diagonally.

Now consider the queen’s gambit: if you placed eight of them on a standard eight square by eight square board, how many ways could they be arranged so that one couldn’t attack the other? It turns out there are 92. But what if you put an even greater number of queens on a chessboard of the same relative size, say 1,000 queens on a 1,000 by 1,000 square chessboard, or even a million queens on a similarly sized board?

The original version of the n-queens math problem first appeared in a German chess magazine in 1848 as the eight-queens problem, and the correct answer appeared a few years later. Then, in 1869, the more elaborate version of the problem surfaced and went unanswered until late last year, when a Harvard mathematician gave a nearly definitive answer.

Michael Simkin, a postdoctoral researcher at the Center of Mathematical Sciences and Applications, calculated that there are about (0.143n)N ways the queens can be placed so that no one attacks each other on giant one-for-n chessboards.

Simkin’s last equation doesn’t give the exact answer, but instead says that this figure is as close to the actual number as you can get right now. The figure of 0.143, which represents an average level of uncertainty in the possible outcome of the variable, is multiplied by whatever n is and then raised to the power of n to get the answer.

For example, on the extremely large chessboard with one million queens, 0.143 would be multiplied by one million, which amounts to about 143,000. That figure would then be raised to the power of one million, meaning it’s multiplied by one million every so often. The final answer is a five million digit number.

Simkin was able to devise the equation by understanding the underlying pattern of how large numbers of queens should be distributed among these massive chessboards — whether concentrated in the center or at the edges — and then using known mathematical techniques and algorithms. .

“If you told me I want you to place your queens on the board like this and that way, I could analyze the algorithm and tell you how many solutions there are that meet this constraint,” Simkin said. “Formally, it reduces the problem to an optimization problem.”

By focusing on the spaces most likely to be occupied, Simkin figured out how many queens there would be in each section of the board and devised a formula to get a valid number of configurations. The calculations resulted in what is known as the lower bound: the minimum number of possible configurations.

Once he got that number, Simkin used a strategy known as the entropy method to find the upper bound, the highest number of possible configurations.

Simkin found that the lower bound answer matches the upper bound answer almost perfectly. Simply put, it showed that the exact answer lies somewhere between the two limits in a relatively small mathematical space.

Simkin has been working on the n-queens problem for nearly five years. He says he’s a bad chess player personally, but wants to improve his game. “I still enjoy the challenge of playing, but I think math is more forgiving,” said Simkin, who became interested in the problem because of the way he was able to apply breakthroughs to the area of ​​math he works in, called combinatorics. , which focuses on counting and problems with selection and arrangements.

Working on the problem was a test of patience and resilience. Four years ago as a Ph.D. student at the Hebrew University of Jerusalem, he attended mathematician and chess wiz Zur Luria at the Swiss Federal Institute of Technology in Zurich. The couple worked together and developed new techniques to arrive at an answer. In the end, after two years of work, they only came up with a better lower limit figure and they knew they were missing something.

Simkin completed his Ph.D. in 2020 and moved to Boston to work at Harvard. The problem was always in the back of his mind, and he came back to it when he realized he needed to start focusing on the spaces that would be the queens, rather than giving each space an equal weight.

While it’s theoretically possible to get an even more precise answer, Simkin is happy to let someone else come for the time being.

“I personally think I may be done with the n-queens problem for a while, not because it has nothing to do with it anymore, but just because I dreamed about playing chess and I’m ready to move on with my life,” he said.


Solve problems on a quantum chessboard


More information:
Michael Simkin, The number of n-queens configurations. arXiv:2107.13460v2 [math.CO], arxiv.org/abs/2107.13460

Provided by Harvard University

This story is published courtesy of the Harvard Gazette, the official newspaper of Harvard University. For more university news, visit Harvard.edu.

Quote: Harvard mathematician answers 150-year-old chess problem (2022, January 24) retrieved January 24, 2022 from https://phys.org/news/2022-01-harvard-mathematician-year-old-chess-problem.html

This document is copyrighted. Other than fair dealing for personal study or research, nothing may be reproduced without written permission. The content is provided for informational purposes only.

Leave a Comment

Your email address will not be published.