The “Queens Puzzle” is a very famous conundrum that was devised back in 1850. Clay Mathematics Institute of America is offering a $1 million prize to a programmer that can write a computer code to solve the puzzle. Researchers from the University of St. Andrews believe that code of solving this problem can change the entire IT industry.
The Queens puzzle is not complicated in itself. You have to place eight queens on a board of chess so none of them can attack each other. This means no two queens share the same row, column, or even a diagonal. If you have a bit of patience, you will be able to solve this puzzle. However, the same is not true for a computer.
When solving a problem, computers go through all the potential options for solving a problem; more the options, the higher the complexity. The paper published in the Journal of Artificial Intelligence states that the computers fail to cope after the chess board becomes larger than 1,000 by 1,000. Professor Ian Gent, the lead author, said in a statement,
“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.”
The puzzle is based on the famous computer problem P versus NP that is still unsolved. In short, the problem asks: ‘if any quickly verifiable problem can also be solved quickly?’ It is quicker to verify that 13,17, and 19 are the only divisors of 4,199 but it will take a longer time to find the divisors.
Many researchers and scientists have taken their turn at the N vs. NP problem and many believe that not every problem can be solved as quickly as its solution can be verified. You can either write an algorithm to solve the problem or to prove that it is just not possible.
Dr. Jefferson has announced,
“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.”
If you think you can do that, a $1 million prize awaits you! Better test your programming skills.