Harvard Mathematician Proves 150-Year Old Chess Puzzle

joshuark shares a report from Popular Mechanics: 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.

Read more of this story at Slashdot.