Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers, offering a $1 million prize to those who can solve the famous ‘Queen’s Puzzle’. However, before all you computer programmers get you hopes up for a big win, the ‘simple’ puzzle is by no means straightforward and could actually take thousands of years to solve.
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. Although the problem has been solved by human beings, once the chess board increases to a large size no computer program can solve it.
Computer Scientist Professor Ian Gent and his colleagues, Senior Research Fellow Dr Peter Nightingale and Reader Dr Christopher Jefferson, found that once the chess board board reached 1000 squares by 1000, computer programs could no longer cope with the vast number of options.
The challenege was detailed in a paper published in the Journal of Artificial Intelligence Research, with the $1m prize offered by the Clay Mathematics Institute in America.
The team likened the potentially eternal struggle 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.
Although many may say that a solution to the puzzle will not bring about the answer to the meaning of life, the university researchers believe that any program capable of solving the problem would be so powerful that it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet.
Professsor 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.”
Content from our partners
Computer programs, however, have a problem with problems such as the Queen’s Puzzle due to the number of possibilities. Due to there being so many options to consider, a solution 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,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly so the rewards are high.”
Over to you computer programmers – think you can solve it?
