Why Computers Are Having Such A Hard Time With This Deceptively Simple Chess Puzzle

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 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 1000x1000, 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.

[The Journal of Artificial Intelligence Research]



    I would have thought this would have been approached by reduction of the initial set,

    Just using excel, shift each queen 1 up and 2 tiles right, when you reach the edge shift right until no intersection for that 1 queen is found.

    As this pattern allows 2 diagonals to fit through itself, and to fit all instances only takes at most 3 cycles of the pattern to complete, it should work for any board size greater than 5x5 (It appears there is no way to solve n queens in an n by n grid less than 5.

    This works if they wish to show that "A" solution can be derived very quickly (computational time n + 10 at worst) if they wanted every solution like the study implies, then it gets hard.

      Hmm, I just thought about it, and it really is a reduced set problem, each step in the chain carves down the number of places to look in the next.

      At and Above 5x5, it can only be 1 queen per horizontal line, (yes there is 1x1, but why would you care), so it would be a recursive set, but each recursion happens faster than the next,

      you can also rule out reflections of the board, both in x and y, so 1 solution earns you 4, 1 bad solution rules out 4, (force multiplying)

      Because of this reflection, your 1000x1000 board only really needs to try placing the queen on the first line in 500 spots. anything else would be covered by the reflection, this reduces the set in half, but only really works for the first.

      Each future queen has to move up 1, and shift either left or right 2 spaces, ruling out 2-3 spaces for each new iteration, it still spirals off into an insane number quickly, but its less than all solutions. a few orders of magnitude.

      There's a solution for 4x4.

      the P=NP problem an order of magnitude problem.
      Because the solving of n-queens takes P time (as of now), so the time it takes grows exponentially. using a reduced set doesn't change it from a polynomial solution.

      The million dollar questions is that can all Polynomial algorithms be reduced to a NP algorithm/formula. If yes, how, and if not, why not.

        Finding the solution to the specific 'queen' problem doesn't seam to be the answer they are looking for. As finding all solutions to a (up to) 1024x1024 grid in three moves won't make finding unconnected Facebook friends or crack a bike lock code any easier.
        The focus looks more to be finding a generic solution to resolving the running through lots of infinite-possible calculations quickly. If I'm not mistaken isn't that what the focus of quantum bits is all about?

          my understanding is that the solution algorithms already exist for a bunch of problems (including the breaking of our standard encryption), but these algorithms are Polynomial in nature, thus the time it takes to resolve the algorithms increase exponentially, so with a sufficient encryption key 256+ bits it will just simply take too long to solve.
          Using quantum will still only just solve things faster, it doesn't reduce the complexity of the algorithm.

          While on the other hand, NP algorithms are faster to resolve and even an increase in complexity doesn't cause an equivalent increase in time to resolve.

          So the question is, can ALL P algorithms be reduced to NP algorithms. If not, why not? If so, how?

          Currently, there isn't even proof that P algorithms can't be reduced to NP.

    This is very difficult given the immense power of the queen

    It's not difficult. Finding all the successful configurations would be difficult however.

Join the discussion!