Researchers from the University of St. Andrews have concluded that any programmer that could make a computer solve the famous “Queens puzzle” would change the entire IT industry as well as bag the $1m prize offered by the Clay Mathematics Institute in America.
The Queens puzzle is a very simple conundrum. Can you place eight queens on a chess board in such a way that no two queens can attack each other? So no queen can share the same row, column, or diagonal. It was first devised in 1850 and any human with a bit of patience can solve it.
So where’s the catch? Computers can’t do it as easily. Computers go through all potential options and the more options you have, the more it takes computers to work the solution out. According to the paper, Journal of Artificial Intelligence, after the chess board becomes larger than 1,000 by 1,000 the computers can’t cope anymore.
“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,” lead author Professor Ian Gent said in a statement.
“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.”
This is just a variation of the famous computer problem known as P versus NP. The crux of it is quite straightforward: can every problem that can be verified quickly also be solved quickly? For example, if I ask to find the divisors of 4,199 it would take you a fair bit of time to try many numbers. But it’s quick and easy to verify that 4,199 is only divisible by 13, 17, and 19 (apart from 1 and itself).
Many believe that not every problem can be solved as quickly as it can be verified, but if you think you can write an algorithm that can do that (or prove that it’s impossible), researchers want to hear from you.
“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,” co-author Dr Christopher Jefferson added.
So, computer scientists and programming buffs, get coding.
Source:-.iflscience.
