The problem of putting eight queens on the chess board so as no queen attacks another is a solved problem, as is placing n queens on an nxn board. However if you place some queens on the board and ask for a completion then the problem is NP complete.

The 8 queens problem is quite old and I met it first not as a chess player but as part of reading Dijkstra's Notes On Structured Programming. It was used as an example of how recursion-based backtracking can be used to solve a problem far more easily than any other approach. I can't say I've thought about it much since, apart from using it as an advanced example of recursion.

If you have never tried the 8 queens problem give it a go - use a chess board and 8 pawns as if they were queens. As you can imagine, it starts out difficult and gets worse as you add queens. This is the reason that another version of the problem, the n queens completion puzzle in which some of the queens have already been placed, is popular.

A symmetric solution

A new paper by Ian Gent, Peter Nightingale and Christopher Jefferson, all of the School of Computer Science at the University of St Andrews, is the result of a friend challenging Professor Gent to solve it on Facebook. In it, and it's 34 pages long so be warned, it is proved the n queens completion problem is NP Complete and #P Complete.

As a reminder, NP is the set of problems that are hard to solve but for which it is easy to check a proposed solution. Clearly n queens completion is easy to check if I give you a solution, but experience suggests it is hard to find a solution. An NP Complete problem is one that if you can find a way to solve it quickly, i.e. in polynomial time, then you can solve all problems in polynomial time and you have proved P=NP, which would be a big deal because most of our cryptography depends on P≠NP, not to mention the one million dollar prize from the Clay Math Institute.

The #P complexity class is the set of problems related to NP that simply asks how many solutions there are. In the n queens case the question is how many solution are there for any n and this is clearly just as hard is the NP problem itself. As for NP Complete, a #P Complete problem  is one that if you can solve it in polynomial time then you can solve all problems in #P in polynomial time.

Given the size of the space you have to search to find a solution, these results might not suprise you. However the number of solutions for n queens is known only to n=27 and the number of solutions is more than 2.34*10^17. The question is how hard are they to solve in practice. To answer this question three different solvers were implemented for three different variations on the basic problems. Normally NP Complete problems show a "phase transition" from solvable to unsolvable as n increases.

"We have presented generators for hard random instances of the Blocked n-Queens and Excluded Diagonals problems, shown that this hardness persists across three solvers using very different technologies, and that the hardness is associated with a phase transition in solvability. A natural model for n-Queens Completion does not appear to generate consistently hard instances. We have also shown that care must be taken in generation methods to avoid flaws which can be found in extant benchmarks. Our experiments raise many interesting questions for future research. These include the asymptotic scaling of the transition in Blocked n-Queens and the Excluded Diagonals problems. An interesting open problem is to find a direct generator of hard random instances for n-Queens Completion which works by randomly placing queens on a chessboard without using reductions."

If you have never thought about it before. the idea that different generators of examples might create easy or hard examples is intriguing.

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal and yet informative way and devotes a chapter to a discussion of what makes a problem NP-Complete and NP-hard.

More Information

Complexity of n-Queens Completion

Related Articles

New Proof That P≠NP: Update - Probably Not

Rubik's Cube Is Hard - NP Hard

Column Subset Selection Is NP-complete

Unshuffling A Square Is NP-Complete

NP-Complete - Why So Hard?

NP Complete

Classic Nintendo Games Are NP Hard

Physics Is NP Hard

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

 <ASIN:0122005503>