If you’re the type of person who loves solving seemingly impossible computational problems and puzzles, why not try this one? Did we mention you’ll be rewarded an awesome $1 million if you solve it? Surely, that riled you up! The University of St. Andrews and the Clay Mathematics Institute announced recently that the prize (which is awarded by the Clay Mathematics Institute) is available for anyone who can solve a chess puzzle which they estimate could take thousands of years to come up with a quick answer to. If it were to be solved, this could mean that a problem that is working out the math behind the so-called “Queens Puzzle” will help address a number of currently impossible problems, this includes breaking any online security measures.
Source: University St. Andrews
As a short history of the Queens Puzzle, it was first devised in 1850. Originally, this puzzle asked chess players to place eight queens on a standard chessboard in such a way that allows no two queens to attach one another. Though this problem has since been solved by human beings, once the chessboard increases to a large size no computer program is able to solve it.
The researchers found that once the chessboard reached 1000 squares by 1000, computer programs can no longer cope with the vast number of options.
Professsor Gent, one of the researchers 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.”
Gent and his colleagues were able to work out the math to demonstrate how difficult the problem is, which is where their 1,000 years estimation comes from. But it’s the next step that’s the tough bit, “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,” Gent said.
According to Professor Gent, to solve 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 brute trial and error, which works by finding every possible option. If there was an algorithm that could solve this problem quickly, it would be a major game-changer.
Article Source:
