The 8-Queens Puzzle

A recent paper on the complexity of the n-Queens Completion Problem by researchers at the University of St Andrews may point the way to a new attack on one of the Millennium Prize Problems, the P vs NP problem.  The paper is an exciting contribution to complexity theory, but it does not say that finding a correct solution to the 8-Queens puzzle or even to the n-Queens puzzle for all n would justify the award of the Millennium Prize.  

As Ian Gent, one of the authors, comments: “The 8-Queens puzzle on the chessboard is a classic puzzle, and all solutions to it have long been known. It is also known that the more general n-Queens puzzle can be solved on all larger size chessboards: that is the puzzle of placing n queens on an n-by-n chessboard so that no queen is attacking another. The new research concerns the n-Queens Completion Problem, where not only is the board larger, but also some queens have already been placed. That is, if some queens have already been placed on the n-by-n board, can you find a solution to the n-Queens puzzle without moving any of those queens?  The technical contribution claimed in this paper is that the n-Queens Completion Problem falls into the class known as NP-Complete.  If correct, this means that any algorithm that can solve the n-Queens Completion Problem can be used indirectly to solve any other problem in the NP class.  This does not apply to the original n-Queens puzzle, because the addition of pre-placed queens is critical.

"Unfortunately, some reports of our work have given the impression that solving the 8-queens puzzle, or the n-queens puzzle for all n, might result in the award of the Millennium Prize. This is not the case, for two reasons. First, as just mentioned, the paper is about the n-Queens Completion problem, not the original n-Queens puzzle. Second, even the discovery of an algorithmic solution to the n-Queens Completion puzzle for all n would not be enough. What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”