Why it matters to you
Solving this complex problem would lead to breakthroughs in a number of areas, including online encryption.
Have a good mind for computational problem-solving? Fancy netting a cool $1 million for your efforts? Then the University of St. Andrews and the Clay Mathematics Institute sure have the competition for you. Announced on Thursday, the prize (awarded by the Clay Mathematics Institute) is available to anyone who can solve a chess puzzle which researchers estimate could take thousands of years to come up with a quick answer to. Were it solved, a program working out the math behind the so-called “Queens Puzzle” would help address a number of currently impossible problems, including breaking any online security measures.
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…