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: