If you can solve this ‘simple’ 170-year-old Eight Queens Puzzle, scientists will give you $1 million

Evan Gower September 1, 2017

A $1,000,000 (£773,100) prize could be yours if you can solve this seemingly ‘simple’ chess puzzle.

If you can solve this 'simple' 170-year-old Eight Queens Puzzle, scientists will give you $1 million

The Clay Mathematics Institute (CMI) in America is offering the cash prize to anyone who can come up with a computer programme to solve a problem known as the Queens Puzzle, first invented in 1850, which is a form of what’s known as a P vs NP problem.

The puzzle appears quite simple; place eight queens on the board in a way that no two queens could attack each other. The twist, however, is that the researchers want the algorithm to work on a 1,000 by 1,000 square chess board. As the number of squares goes up, so does the number of queens you need to place.

eight-queens-animation

By current estimations placing 1,000 queens on a 1,000 by 1,000 square board could take thousands of years – due to the sheer number of possibilities to consider.

Any algorithm capable of solving the puzzle quickly would also be able to crack the toughest online security measures, the researchers have said, because it would be incredibly powerful.

It is an example of a Millennium Prize Problem, of which there are seven in total. These puzzles were announced at a meeting in 2000 and are said to represent the most difficult problems facing mathematics. The CMI said this was to show people there were still many unanswered questions in maths.

The Board of Directors of CMI designated a $7 million prize fund for the solutions to the problems, with $1 million allocated to the solution of each problem. The first of these was solved in 2003 by Grigori Perelman, a Russian mathematician, but he declined the prize.

The University of St Andrews has now laid down a challenge for anyone to solve this puzzle using a computer.

University of St Andrews professor Ian Gent came up with the idea after he was challenged by a Facebook friend to solve the chess puzzle himself. He and his colleagues Dr Peter Nightingale and Dr Christopher Jefferson attempted to write a computer program themselves.

Their solutions use ‘backtracking’ – an algorithm used in programming where every possible option is considered and then ‘backed away’ from until the correct solution is found – and their ideas are outlined in a paper, published in the Journal of Artificial Intelligence Research.

However, as soon as the chessboard became large enough – 1,000 by 1,000 squares – the algorithm couldn’t cope. These problems are so difficult for computer programs because there are too many options to consider, and it can take many years.

“If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily,” said Professsor Gent. “This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other, or very important ones like cracking the codes that keep all our online transactions safe.”

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