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

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

<ul>
<li>Gardnera, Gritzmannb, Prangenbergc, <a href="http://scholar.google.com/scholar?hl=en&amp;q=On%20the%20computational%20complexity%20of%20reconstructing%20lattice%20sets%20from%20their%20X-rays" rel="nofollow">On the computational complexity of reconstructing lattice sets from their X-rays</a>, 1999</li>
</ul>

<p>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\}$.</p>

<blockquote>
  <p>INPUT: $r,c\in[2]^m$ and $a,b\in[2]^{2m-1}$</p>
  
  <p>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}$</p>
</blockquote>

<p>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, <em>A Dynamic Programming Solution to the n-Queens Problem,</em> 1992], although perhaps this is easy to see.)</p>

<p>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.</p>

<blockquote>
  <p>INPUT: ${xi},{xj},{xk}\in[2]^{n\times n}$</p>
  
  <p>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}$</p>
</blockquote>

<p>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.</p>

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

CC BY-SA 3.0
2014-12-30T20:50:05.527Z
2014-12-30T23:38:19.787Z
2014-12-30T23:38:19.787Z
Radu GRIGore
<p>It's taken years but this post inspired us to write a paper which has come out today.  </p>

<p>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.</p>

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

<p>The complexity of n Queens Completion
Journal of AI Research
Gent, Jefferson, Nightingale
doi:10.1613/jair.5512 
<a href="http://www.jair.org/papers/paper5512.html" rel="noreferrer">http://www.jair.org/papers/paper5512.html</a></p>

CC BY-SA 3.0
2017-08-31T21:49:57.877Z
Nice.  Congratulations!
Jeffε
CC BY-SA 4.0
2019-01-22T22:04:57.233Z
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)
Sergei Rogovtcev
CC BY-SA 3.0
2017-08-31T08:39:14.917Z
2017-08-31T08:39:14.917Z
Ian Gent
<p>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:</p>

<ul>
<li>$1\le Q[i] \le n$ for all $i$</li>
<li>$Q[i] \ne Q[j]$ for all $i\ne j$</li>
<li>$Q[i]-i \ne Q[j]-j$ for all $i\ne j$</li>
<li>$Q[i]+i \ne Q[j]+j$ for all $i\ne j$</li>
</ul>

<p>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 <em>decision</em> problem, the $n$-queens problem is completely trivial.</p>

<p>The standard backtracking algorithm for <em>constructing</em> 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:</p>

<ul>
<li>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?</li>
</ul>

<p><strong>Is this more general decision problem NP-hard?</strong></p>

<p>Several nearby questions are known to be NP-hard, including Latin square completion [<a href="http://dx.doi.org/10.1016/0166-218X(84)90075-1" rel="noreferrer">Colbourn 1984</a>], Sudoku completion [<a href="http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf" rel="noreferrer">Yato and Seta 2002</a>], and a different generalization of $n$-queens [<a href="http://arxiv.org/abs/cs/0701049v2" rel="noreferrer">Martin 2007</a>], but this specific question seems to have escaped any serious attention.</p>

<p>Related cstheory.se questions:</p>

<ul>
<li><a href="https://cstheory.stackexchange.com/q/12682/111">Is the N Queens problem NP-hard?
</a></li>
<li><a href="https://cstheory.stackexchange.com/q/3903/111">Is the half-filled magic square problem NP-complete?</a></li>
</ul>

CC BY-SA 3.0
2014-12-30T11:15:10.440Z
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).
Marzio De Biasi
CC BY-SA 3.0
2014-12-30T14:58:12.037Z
@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 http://cstheory.stackexchange.com/a/5559/109
András Salamon
<cc.complexity-theory><board-games>
Complexity of n-queens-completion?
Jeffε
# Complexity of n-queens-completion?

(Asked by: username_0 on 2014-12-29)

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](http://dx.doi.org/10.1016/0166-218X(84)90075-1)], Sudoku completion [[Yato and Seta 2002](http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf)], and a different generalization of $n$-queens [[Martin 2007](http://arxiv.org/abs/cs/0701049v2)], but this specific question seems to have escaped any serious attention.

Related cstheory.se questions:

* [Is the N Queens problem NP-hard?](https://cstheory.stackexchange.com/q/12682/111)
* [Is the half-filled magic square problem NP-complete?](https://cstheory.stackexchange.com/q/3903/111)

**Tags:** cc.complexity-theory, board-games

> **Comments:**
> **username_1**: 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).  
> **username_2**: @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 http://cstheory.stackexchange.com/a/5559/109  

---

## 2 answers

### Answer by username_4 on 2017-08-31. Score: 16 | Accepted answer

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 username_0 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>

> **Comments:**
> **username_0**: Nice.  Congratulations!  
> **username_5**: 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)  

---

### Answer by username_3 on 2014-12-30. Score: 6

(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

* Gardnera, Gritzmannb, Prangenbergc, [On the computational complexity of reconstructing lattice sets from their X-rays](http://scholar.google.com/scholar?hl=en&q=On%20the%20computational%20complexity%20of%20reconstructing%20lattice%20sets%20from%20their%20X-rays), 1999

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.


---

