The one million dollar chess puzzle

SCIENTISTS have thrown down a million dollar gauntlet to computer programmers to find a solution to a 'simple' chess puzzle which could take thousands of years to solve.

Professor Ian Gent, and Dr Peter Nightingale attempt the puzzle with the giant chess set at Falkland Palace. Picture: Stuart Nicol/Contributed

Computer scientists believe that any programme capable of solving the famous ‘Queens Puzzle’ would be so powerful it could solve impossible tasks such as decrypting the toughest security on the internet.

Anyone who solves the ‘Queens Puzzle’ will be given a $1 million (£777,500) prize by the Clay Mathematics Institute in America.

Professor Ian Gent and Dr Peter Nightingale. Picture: Stuart Nicol/Contributed

The puzzle, which dates back to 1850, challenges a player to place eight queens on a standard chessboard so that no two queens could attack each other.

It requires putting one queen in each row so that no two queens are in the same column and no two can be diagonal.

The puzzle has been completed but once the chess board increases to a large size no computer programme can solve it.

Computer scientist Professor Ian Gent, of the University of St Andrews who threw down the gauntlet, 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.

Professor Ian Gent and Dr Peter Nightingale. Picture: Stuart Nicol/Contributed

“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.”

Prof Gent and his colleagues including senior research fellow Dr Peter Nightingale and reader Dr Christopher Jefferson first became involved in the puzzle when a friend challenged prof Gent to solve it over Facebook.

The team found that once the chess board had reached 1,000 by 1,000 squares computer programmes could no longer cope with the number of options.

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

The team, who published a paper in the Journal of Artificial Intelligence Research, reckon that the financial rewards reaped from a program would be immense, particularly from technological companies.

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