Computer programmers are being offered a $1 million prize for inventing a system to crack a simple chess puzzle.
The eight queens puzzle, which has been solved by humans on a regular chess board, sends computer programmes into meltdown.
A team of St Andrews academics concluded that devising a computer programme to solve the problem could reap immense rewards.
In a paper published in the Journal of Artificial Intelligence Research, Professsor Ian Gent from the university’s school of computer science said it could be the key to tightening up internet security.
“If you could write a computer programme that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily,” he said.
“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.”
The Clay Mathematics Institute in America has offered a $1 million reward for whoever solves a similar conundrum called the P vs NP Problem.
Professor Gent and his colleagues, Dr Peter Nightingale and Dr Christopher Jefferson, first became intrigued by the puzzle after a friend challenged Professor Gent to solve it on Facebook.
The team found that when the chess board reached 1000 squares by 1000, computer programmes could no longer cope with the vast number of options and sunk into a potentially eternal struggle akin to the fictional “super computer” Deep Thought in Douglas Adams’ Hitchhiker’s Guide to the Galaxy, which took seven and a half million years to provide an answer to the meaning of everything.
Dr Nightingale said: “In practice, nobody has ever come close to writing a programme that can solve the problem quickly.
“So what our research has shown is that, for all practical purposes, it can’t be done.”
Dr Jefferson added: “There is a $1m prize for anyone who can prove whether or not the queens puzzle can be solved quickly so the rewards are high.”
The 8 Queens puzzle
Devised in 1850, the queens puzzle originally challenged a player to place eight queens on a standard chessboard so that no two queens could attack each other.
This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal (see below).
There is more than one potential solution.
The reason such problems are so difficult for computer programmes is that there are so many options to consider that it can take many years due to a process of “backtracking” – an algorithm used in programming where every possible option is considered and then “backed away” from until the correct solution is found.
Chess has long provided the source for puzzles such as the traditional fable of the servant who, when asked to choose a reward by his king, asked for one grain of rice to be placed on the first square of a standard 8×8 chessboard, doubled in the next and so on until it was found there was not enough rice in the entire world.
The fable indicates the huge numbers involved when using just a standard sized chess board. When the board size increases the numbers become vast.
