The one million dollar chess puzzle
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.
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.
“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.”