A popular chess problem known as the Queen’s Puzzle has captivated mathematicians and computer scientists for years, yet no one has been able to write a computer program that can solve the conundrum quickly and efficiently. Researchers from the UK now claim that computers will never be up to the task — and they’re offering a $US1 million ($1.3 million) to anyone who can prove them wrong.
Image: FlankerFF/Wikimedia
The Queen’s Puzzle has been around since the 1850s, and it challenges a player to place eight queens on an otherwise empty conventional chessboard such that no queen threatens any other. This is very difficult given the immense power of the queen; the player must ensure that each queen is placed on its own column, but such that no queen threatens another along other diagonals and rows.
Three of 92 solutions to the Queen’s Puzzle. The solutions seem simple, but getting there is a tremendous computational challenge. (Image: Wikimedia)
This puzzle has been solved by humans (there are 92 solutions out of 4,426,165,368 possible arrangements of eight queens on an 8×8 board), but it continues to present a fascinating and complex challenge for mathematicians and computer scientists, particularly when the board is scaled up beyond the standard eight-by-eight dimensions. When the board becomes bigger and more queens are added, it creates a problem that, as a new paper published in The Journal of Artificial Intelligence Research points out, is next to impossible for a computer to solve in a reasonable amount of time.
Computer programs tend to take a “brute force” approach to the problem, systematically going through every possible permutation. This is why the Queen’s Puzzle is considered “computationally expensive”, where the total number of combinations can reach horrendously big numbers (a 27×27 board, for example, offers 2.34 quadrillion possible solutions, or 234,000,000,000,000,000). As the new study points out, once the board’s dimension reaches 1000×1000, and with 1000 queens to place, computers get borked, sinking into an apparently endless abyss of calculations.
As lead researcher Ian Gent from the University of St Andrews points out, efficient solutions to the Queen’s Puzzle remains elusive for computer programmers, requiring computers to churn away at the possibilities for literally thousands of years (the fictional Deep Thought supercomputer from Hitchhiker’s Guide to the Galaxy comes to mind, a machine that required a half million years to calculate the meaning of everything). Gent became aware of the Eight Queen problem after a friend challenged him to solve it on Facebook — a challenge Gent and his colleagues have now turned into a formal study and a prize worth $US1 million ($1.3 million), as offered by the US-based Clay Mathematics Institute.
This problem isn’t just some arcane or self-indulgent exercise for computer geeks. Gent feels that a computer program that can efficiently solve the Queen’s Puzzle would also be capable of solving tasks currently considered impossible, such as decrypting some the toughest security protocols on the internet.
“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,” said Gent in a press release. “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.”
As noted in the paper, the benefits of such a program would be immense, both in terms of what it would mean to the fields of mathematics, computer science and artificial intelligence, and also in terms of financial rewards. The first team to crack this code, in addition to winning a million bucks, would be first to take the technology to market.
But Gent and co-author Peter Nightingale have their doubts that anyone will solve this problem any time soon. The problem has to do with so many options being available to the computer, and the issue of backtracking, where an algorithm considers every single possible option to a problem, and then abandons, or “backs away”, from an apparently invalid solution until the correct solution can be found. This process, even for the fastest computers, can take years.
“However, this is all theoretical. In practice, nobody has ever come close to writing a program that can solve the problem quickly,” said Nightingale. “So what our research has shown is that — for all practical purposes — it can’t be done.”
For those looking for a more technical explanation of this problem — formally known as the P vs NP Problem — I suggest you check out Mike James’ excellent post at I Progammer. The Wikipedia entry on the Eight Queens Puzzle is also very good.