The $1m challenge to solve 'simple' chess puzzle that could take thousands of years

The University of St Andrews has issued a lucrative challenge to computer programmers to find a solution to a "simple" chess conundrum that could take thousands of years to solve.

The Queen's Puzzle, whereby players are challenged to place eight queens on a standard chessboard so that no two queens could attack each other, was created in 1850 and while human brains have managed to work it out when the problem is scaled up on a larger board no machine could due to the sheer number of options involved.

Researchers at the university published the challenge in the Journal of Artificial Intelligence Research and believe any programme that could crack the puzzle would be so powerful it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet.

Due to the immense implications of finding a solution, those who manage to succeed in writing a programme "no one has even come close to" will be rewarded with a substantial $1m prize.

The key to solving the Queen's Puzzle is putting one queen in each row, so that no two queens are in the same column, and no two queens are in the same diagonal. However, when computer scientists were challenged to solve the problem on chess boards of 1000 squares by 1000, their computer system could not handle the huge number of options it would take years upon years to calculate.

Computer programmes in this situation use a process known as 'backtracking' where it gathers every possible option then whittles them down by 'backing away' from each incorrect one until the right answer is found. In this case, it would be a long, painstaking process that could stretch into hundreds, if not thousands, of 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 Professor Ian Gent, computer scientist at the university.

"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."