Scientists are offering $1 million to crack one of chess’ most famous unsolved puzzles

Scientists are hoping to solve one of chess’ most iconic puzzles by offering up a million-dollar prize to anyone who can discover its solution.

The n-queens problem is an expanded version of the eight queens puzzle first proposed in 1850, which poses the challenge of placing eight queens on a standard eight-by-eight chessboard without any of the queens being able to attack each other – that is, by being in the same row, column or diagonal as another queen.

The n-queens variant blows the simple conundrum up to an infinite size, aiming to uncover a method that works for any size of chessboard, where the number of queens used is equal to the number of squares along one side.

At the moment, the highest known answer is for a chessboard measuring 27-by-27 squares, which has more than 234 quadrillion (that’s a thousand trillion) potential solutions.

What makes the deceptively simple problem so hard to solve is that computers cannot calculate the huge number of potential placements of the queens once the chessboard measures more than a thousand squares along one edge, explained Professor Ian Gent and his team of researchers at Scotland’s University of St Andrews, who recently put out a call to finally crack the 167-year-old conundrum. 

This means that any algorithm that could solve the puzzle quickly could then be used to work out other incredibly complicated problems with a huge number of potential solutions – such as technological security or finding connections between two random people in an epic version of Seven Degrees of Separation.

“However, this is all theoretical," added senior research fellow Dr Peter Nightingale. "In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that – for all practical purposes – it can’t be done.”

The US Clay Mathematics Institute is stumping up the $1 million prize as part of the Millennium Prize Problems, a series of seven mathematical puzzles deemed to be the most challenging in the world back in 2000. Only one of the problems, the Poincaré conjecture, has been solved so far – although the mathematician who discovered the solution ultimately refused the cash reward.