A Harvard Mathematician Finally Cracked This 150-Year-Old Chess Puzzle
By Caroline Delbert
• A 50-page proof shows the new estimated answer to the n queens problem.
• A chess board is a matrix, so it involves an entire field of math called linear algebra.
• The n queens puzzle dates back over 150 years and is solved up to n=27.
A mathematician from Harvard University has (mostly) solved a 150-year-old Queen's gambit of sorts: the delightful n queens puzzle.
In newly self-published research (meaning it has not yet been peer-reviewed), Michael Simkin, a postdoctoral fellow at Harvard's Center of Mathematical Sciences and Applications, estimated the solution to the thorny math problem, which is based loosely on the rules of chess.
The queen is largely understood to be the most powerful piece on the board because she can move in any direction, including diagonals. So how many queens can fit on the chess board without falling into each other's paths? The logic at play here is similar to a sudoku puzzle, dotting queens on the board so that they don't intersect.
Picture a classic chess board, which is an eight-by-eight matrix of squares. The most well-known version of the puzzle matches the board because it involves eight queens—and there are 92 solutions in this case. But the "n queens problem" doesn't stop there; that's because its nature is asymptotic, meaning its answers approach an undefined value that reaches for the infinite.
Up until now, experts have explicitly solved for all the natural numbers (the counting numbers) up to 27 queens in a 27-by-27 board. However, there is no solution for two or three, because there's no possible positioning of queens that satisfies the criteria. But what about numbers above 27?
Consider this: for eight queens, there are just 92 solutions, but for 27 queens, there are over 200 quadrillion solutions. It's easy to see how solving the problem for numbers higher than 27 becomes extremely unwieldy or even impossible without more computing power than we have at the moment.
That's where Simkin's work enters the arena. His work approached the topic through a sharp mathematical estimate of the number of solutions as n increases. Ultimately, he arrived at the following formula: (0.143n)n. In other words, there are approximately (0.143n)n ways that you can place the queens so that none are attacking one another on an n-by-n chessboard.
The math itself is a complex assortment of matrix algebra that takes 50 pages to walk through and prove. And it's interesting that, technically, Simkin's results are still just an estimate! But it's better than what mathematicians have been working with up until now.
"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 that many times. The final answer is a figure with five million digits," Harvard explains in a press release.
To come to his solution, Simkin first took the averages of the distribution of queens around the board. He used those values to establish the lower-bound value, meaning the minimum number of solutions that a particular value of n will have. Using a strategy known as the "entropy method," Simkin studied a subunit of the grid that he created (and named a "queenon") to find the upper-bound value.
Both approaches use averageness and/or randomness as a way to help model the correct value. Simkin discovered that the two different functions he established for lower-bound and upper-bound values are almost the same—that means the candidate pool of answers is smushed between them very tightly, establishing a solid mathematical estimate.
All of this hard work means that, for the first time since 1869, we have an inkling of a solution to the n queens problem. For Simkin and his department at Harvard, this is a huge achievement, but an ironic one: he doesn't play chess. "I still enjoy the challenge of playing, but, I guess, math is more forgiving," he explains in the release. – Men’sHealth
