UNIVERSITY OF St Andrews researchers are offering a $1m prize to programmers able to device an algorithm capable of cracking a legendary chess problem quickly.
The "Queen's Puzzle" (sometimes known as "8 Queens" or "Queens on the Board") was first published in 1848, with solutions starting to appear two years later, but it still fascinates mathematicians to this day.
The object is to arrange 8 Queens on a board so none are able to attack the others. That means one queen per row, no two queens in the same column, and no queens in the same diagonal.
In all, there are 4,426,165,368 possible arrangements of eight queens on an 8×8 board, but only 92 solutions. When boards are scaled up with more rows and columns, the computing problem becomes enormous as there are so many options to consider as the processor backtracks.
The researchers, Professor Ian Gent and colleagues believe that to scale out a computer enough to solve this puzzle quickly as well as human beings are able to do would also give it enough power to solve encryption, and maybe even unlock some medical mysteries.
Gent says, "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."
Senior Research Fellow Dr Peter Nightingale added, "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."
Reader Dr Christopher Jefferson points out, "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."
We'd expect a cocky little supercomputer from DeepMind that has already "solved" board game Go would have something to say about this. Except it's locked in a display case at Google's London HQ. µ
Someone could be in for a NASty surpise
An assault course on the senses
Boasting Bionic boosting