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. If 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. “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,” is the action to do.
According to competition’s launchers, solving this problem efficiently is, “probably the hardest thing to do in computer science.” Professor Ian Gent, one of the researchers of the St. Andrews University 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. “The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem,” he noted about the announced brain’s competition. Do you want to give a try ?
