# 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.”