A Harvard mathematician has basically solved an epic, 150-year-old chess problem

On one level, chess seems like a simple game: 64 individual black or white squares, 16 pieces per side, and two competitors striving for conquest.

Dig a little deeper though, and the game offers incredibly complex possibilities, posing challenges to chess theorists and mathematicians that can go unsolved for decades or even centuries.

In July 2021, one such challenge was finally solved – at least, up to a point. Mathematician Michael Simkin, from Harvard University in Massachusetts, put his mind to the n-queens problem that has been puzzling experts since it was first imagined in the 1840s.

If you know your chess, you know that the queen is the most powerful piece on the board, able to move any number of squares in any direction. The n-queens problem asks this: With a certain number of queens (n), how many arrangements are possible where the queens are far enough apart so none of them can take any of the others?

For eight queens on a standard 8 x 8 board, the answer is 92, although most of these are rotated or reflected variants of just 12 fundamental solutions.

But what about 1,000 queens on a board that's 1,000 x 1,000 squares? What about a million queens? Simkin's approximate solution to the problem is (0.143n)ⁿ – the number of queens multiplied by 0.143, raised to the power of n.

What you're left with is not the precise answer, but it's as close as it's possible to get right now. With a million queens, the figure comes out as a number with five million digits after it – so we won't reproduce it for you here.

It took almost five years for Simkin to come up with the equation, with a variety of approaches and techniques used, and a few barriers on the way to a solution. Ultimately the mathematician was able to calculate the lower bounds and the upper bounds of possible solutions using different methods, finding that they almost matched.

"If you were to tell me I want you to put your queens in such-and-such way on the board, then I would be able to analyze the algorithm and tell you how many solutions there are that match this constraint," says Simkin.

"In formal terms, it reduces the problem to an optimization problem."

Early on, Simkin and colleague Zur Luria at the Swiss Federal Institute of Technology Zurich collaborated on a variation of the n-queens problem known as the torodial or modular problem. In this one, the diagonals wrap around the board, so a queen could move diagonally off the right edge of a board and reappear on the left, for example.

This grants each queen symmetry of attack, but it isn't how a normal chessboard works: a queen in the corner of the board doesn't have as many angles of attack as one in the center.

Ultimately, the pair's work on the toroidal problem stalled (although they published some results), but Simkin ended up adapting some of the fruits of that labor into his final solution. 

As the boards get bigger and the number of queens increases, the research shows that in most allowable configurations the queens tend to congregate along the sides of the board, with fewer queens in the middle, where they are exposed to attack. This knowledge enables a more weighted approach.

In theory, a more precise answer to the n-queen puzzle should be possible – but Simkin has got us closer than ever before, and he's happy to pass the challenge on to someone else to study further.

"I think that I may personally be done with the n-queens problem for a while, not because there isn't anything more to do with it but just because I've been dreaming about chess and I'm ready to move on with my life," says Simkin.

Simkin's paper on the solution is available on the preprint server arXiv.

#Physics | https://sciencespies.com/physics/a-harvard-mathematician-has-basically-solved-an-epic-150-year-old-chess-problem/