27
$\begingroup$

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:

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I'm wondering if the existing NP-completeness proofs of Sudoku, Latin square completion, (and tons of other similar problems) ... really deals with succinct/sparse representations of the instances (e.g. in the Latin Square Completion NPC proof, Colbourn says "Membership in NP is immediate" but he doesn't mention any instance encoding issue). $\endgroup$
    – Marzio De Biasi
    Dec 30, 2014 at 11:15
  • 1
    $\begingroup$ @Marzio: these proofs are highly dependent on representation, and (even though this is usually not even mentioned) it is often not even trivial to establish membership in NP, for instance see cstheory.stackexchange.com/a/5559/109 $\endgroup$
    – András Salamon
    Dec 30, 2014 at 14:58

2 Answers 2

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice. Congratulations! $\endgroup$
    – Jeffε
    Aug 31, 2017 at 21:49
  • $\begingroup$ I have a naive question: it seems to me that if there is a (correct) prefix of a length $n-1$, then transition to a set of $n$ can be done by checking the diagonal of the prefix, and thus, in linear time. Is that so, or am I missing something? (I do undestand that the original problem in post does not imply correct prefix) $\endgroup$
    – Sergei Rogovtcev
    Jan 22, 2019 at 22:04
6
$\begingroup$

(This points to some related results. I initially thought that the related results are very related, but I can't fill the gaps quickly, so maybe they're not so related after all. Perhaps still helpful.)

Exercise 118 in the (draft of) section 7.2.2.2 of The Art of Computer Programming looks at a very similar problem. In the solution, Knuth credits an article that in turn credits

Exercise 118 proves that BINARY DIGITAL TOMOGRAPHY is NP-complete. The input of this problem consists of line and diagonal sums, all from $[2]=\{0,1\}$.

INPUT: $r,c\in[2]^m$ and $a,b\in[2]^{2m-1}$

OUTPUT: whether there exists $x\in[2]^{m\times m}$ such that $\sum_j x_{ij}=r_i$ and $\sum_i x_{ij}=c_j$ and $\sum_i x_{i,s-i}=a_s$ and $\sum_i x_{i,d+i}=b_{d+m-1}$

It's not clear to me how to reduce this to your problem. One observation that might help is that the output of your problem also depends only on the sums, not on the exact positioning of the queens. (See Theorem 2.4 in [Rivin, A Dynamic Programming Solution to the n-Queens Problem, 1992], although perhaps this is easy to see.)

Knuth proves that BINARY DIGITAL TOMOGRAPHY is NP-complete by a reduction from the BINARY CONTINGENCY PROBLEM. This is a very similar problem, except in 3 dimensions, and without diagonals.

INPUT: ${xi},{xj},{xk}\in[2]^{n\times n}$

OUTPUT: whether there exists $x\in[2]^{n\times n\times n}$ such that $\sum_i x_{ijk}={xi}_{jk}$ and $\sum_j x_{ijk}={xj}_{ik}$ and $\sum_k x_{ijk}={xk}_{ij}$

The article by Gardnera et al. seems to reduce from more standard NP-complete problems. I don't understand well enough either reduction to explain it here, so I'll just leave the pointers from above for you to explore if you wish.

This could all be useless, unless somebody figures out how to reduce BINARY DIGITAL TOMOGRAPHY to the question being asked.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.