Complexity of n-queens-completion? The classical $n$-queens problems asks, given a positive integer $n$, whether there is an array $Q[1..n]$ of integers satisfying the following conditions:


$1\le Q[i] \le n$ for all $i$
$Q[i] \ne Q[j]$ for all $i\ne j$
$Q[i]-i \ne Q[j]-j$ for all $i\ne j$
$Q[i]+i \ne Q[j]+j$ for all $i\ne j$


Each integer $Q[i]$ represents the position of a queen on the $i$th row of an $n\times n$ chessboard; the constraints encode the requirement that no queen attacks any other queen. It is easy to prove that there are no solutions when $n=2$ or $n=3$, and closed-form solutions are known for all other values of $n$.  Thus, as a decision problem, the $n$-queens problem is completely trivial.

The standard backtracking algorithm for constructing an $n$-queens solution speculatively places queens on a prefix of the rows and then recursively determines whether there is a legal placement of queens on the remaining rows.  The recursive subproblem can be formalized as follows:


Given an integer $n$ and an array $P[1..k]$ of integers, is $P$ a prefix of an array $Q[1..n]$ that describes a solution to the $n$-queens problem?


Is this more general decision problem NP-hard?

Several nearby questions are known to be NP-hard, including Latin square completion [Colbourn 1984], Sudoku completion [Yato and Seta 2002], and a different generalization of $n$-queens [Martin 2007], but this specific question seems to have escaped any serious attention.

Related cstheory.se questions:


Is the N Queens problem NP-hard?

Is the half-filled magic square problem NP-complete?
It's taken years but this post inspired us to write a paper which has come out today.  

The answer is that n Queens Completion is NP-Complete.  However for full disclosure should mention we solve a slight variant of the problem.  In our case the set of queens doesn't have to be a prefix of the full set.  So technically we haven't resolved the exact problem asked here.  However it would be extremely surprising if the version of n Queens Completion from this query wasn't also NP-Complete.

I want to repeat the thanks we put in the paper to Jeffε for raising this question here.  

The complexity of n Queens Completion
Journal of AI Research
Gent, Jefferson, Nightingale
doi:10.1613/jair.5512 
http://www.jair.org/papers/paper5512.html