The Courier & Advertiser (Fife Edition)
Can you solve chess puzzle for $1m?
Academics at St Andrews say net security could also benefit from solution
Computer programmers are being offered a $1 million prize for inventing a system to crack a simple chess puzzle that could improve internet security.
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 University 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, Professor 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 the $1m 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 1,000 squares by 1,000, 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.”