Mission impossible? Million dollar prize for chess puzzle

● ‘Queens Puzzle’ winning program would attract IT firms worldwide

been solved by human beings, once the chess board increases to a large size no computer programme has been able solve it so far.

Prof Gent said he and his colleagues – senior research fellow Dr Peter Nightingale and Reader Dr Christopher Jefferson, from the university’s school of computer science – first became intrigued by the puzzle after a friend challenged him to solve it on Facebook.

The team found that once the chess board reached 1,000 squares by 1,000, computer programs 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 mean- ing of life, the universe and everything. Prof Gent said: “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.

“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 reason these problems are so difficult for computer programs is there are so many options to consider that it can take many years. This is 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.

Dr Nightingale said: “However, this is all theoretical. 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.”

Dr Jefferson added: “There is a $1 million (£773,000) prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly so the rewards are high.”

The institute, in Peterborough, New Hampshire, offers a number of cash prizes to solve scientific conundrums.

0 Grand masters: Prof Ian Gent, left, with Dr Peter Nightingale