First devised in 1850, the Queens Puzzle originally asked chess players to place eight queens on a standard chessboard in a way that would allow no two queens to attack one another. Although the problem has since been solved by human beings, when the chessboard is increased to a sufficiently large size (think boards with 1,000 by 1,000 squares and upwards), researchers at the University of St. Andrews claim a computer program would take roughly a millennium to solve it. Unless you can prove otherwise.
“On January 1, 2015, a friend of mine on Facebook posted a link to an online discussion about this problem, and said he had a hunch I would be interested in it,” Professor Ian Gent, one of the researchers who threw down the gauntlet, told Digital Trends. “He was right, and so I spent a lot of time with my colleagues working it out.”
Gent and his colleagues managed to work out the math to show how hard the problem is — whch is where the 1,000 years estimation comes from. The really tough bit, however, is to take the next step. “You can [win the $1 million] either by proving that no algorithm can solve the n-Queen Completion puzzle in reasonable time, or by finding an algorithm which does solve it quickly,” he continued.
According to Gent, solving this problem efficiently is, “probably the hardest thing to do in computer science.” The reason is that the current methods of solving it essentially use blunt-force trial and error, which works by figuring out every possible option. An algorithm that could solve the problem quickly, on the other hand, would be a major game-changer.
Even if you don’t think you’re the person for the job, you can check out a research paper describing the problem by Gent and his colleagues, published in the Journal of Artificial Intelligence Research.
In the meantime, Gent has three pointers for anyone hoping to pick up the grand prize: Get a Ph.D. in computational complexity, be brilliant, and get very, very lucky.
