The puzzle is 170 years old, first posed in 1850. It simply involves a chessboard and eight queen chess pieces. And it actually is a tactile version of an ancient theoretical problem (P vs NP). The original puzzle is simple: place eight queens on a standard chess board in such a way that no one piece can attack another piece.
This puzzle is actually pretty easy to solve if you use simple mathematical principles. In fact, there are several possible ways to place the queens on the chessboard to reach the solution; and none of these solutions is worth $1 million.
The one-million-dollar question is whether or not a human can design a computer program (an algorithm) to do this on a much larger scale. Just how large? Well, a chess board is 8×8 squares, and you must place 8 queens, if you recall. The prize-winning algorithm, though, will place 1,000 queens on a 1,000×1,000 square chess board.
You see, computers seem to be able to handle this problem as you slowly increase the variables but, apparently, 1,000 is the threshold.
University of St. Andrews professor, Ian Gent developed this idea after a friend challenged him to solve the puzzle on his own. This led to a discussion with colleagues—Dr. Peter Nightingale and Dr. Christopher Jefferson—which led to the prize offer.
Gent comments, “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.”
Dr. Nightingale adds, “In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that – for all practical purposes – it can’t be done.”
Now, the big reason why this problem is so hard to solve—even for our best and brightest super computers—is that the variables are so massive it could still take years to figure them all. And the reason for this is because even our best computers use an algorithm called “backtracking” which looks at every possible solution and then backs away until reaching the final solution(s). Its kind of like narrowing down from a large pile.