n-Queens Completion is NP-Complete

Ian Gent, Chris Jefferson and Peter Nightingale have shown that the n-Queens puzzle (given a chessboard of size n x n, place n queens so that no two queens attack each other) is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30. See these two articles: “Simple” chess puzzle holds key to $1m prize and n-Queens Completion is NP-Complete for further details.