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 $1 million to anyone who can prove them wrong.

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.

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 combination can reach horrendously big numbers (a 27x27 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 1,000x1,000, and with 1,000 queens to place, computers get borked, sinking into an apparently endless abyss of calculations.

Advertisement

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 $1 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.â€ť

Advertisement

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, but 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.â€ť

Advertisement

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.

**Correction**: A previous version of this article stated 2.34 septendecillion when itâ€™s actually 2.34 quadrillion. Sorry for the error.

[The Journal of Artificial Intelligence Research]

Advertisement