<p>Actually, this has just been shown to be the case.</p>

<p><a href="https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/" rel="nofollow noreferrer">https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/</a>
]</p>

CC BY-SA 3.0
2017-09-02T03:09:29.273Z
No, it hasn't. Read the article, or even its abstract: it deals with $N$-queens **completion**, a *variant* of the problem.
Clement C.
CC BY-SA 3.0
2017-09-02T05:36:43.783Z
@ClementC. Actually, since the original question is not precise enough, I think Kasper has a point even if his way of stating it may be incomplete. Deciding, given n, if there exists a placement is clearly in P since the problem always has solutions for n>3.  Thus, n-queens completion problem (deciding if one can extend a given partial solution) seems a natural decision problem to look at to understand the complexity of the problem.
holf
CC BY-SA 3.0
2017-09-02T11:29:23.057Z
@holf That's indeed a valid point *you* make, but one that this answer does not even mention (and that a reader would absolutely not get by reading it). Having a misleading answer to an ambiguous question is not exactly optimal.
Clement C.
CC BY-SA 3.0
2017-09-02T00:20:44.740Z
2017-09-02T00:20:44.740Z
Kasper
<p>As stated, the answer to this question is NO.</p>

<p>References : 
A polynomial time algorithm <a href="http://dl.acm.org/citation.cfm?id=101343" rel="noreferrer">http://dl.acm.org/citation.cfm?id=101343</a> [courtesy: vzn]</p>

<p>Another much simpler technique : <a href="http://dl.acm.org/citation.cfm?id=122322" rel="noreferrer">http://dl.acm.org/citation.cfm?id=122322</a> [courtesy: Jeffe]</p>

CC BY-SA 3.0
2012-09-25T15:54:09.627Z
you might consider accepting this answer so it doesn't keep reappearing as unanswered.
Suresh Venkat
CC BY-SA 3.0
2012-09-25T16:38:08.960Z
The polynomial-time algorithm in the first reference is not guaranteed to produce a solution.  Whether the algorithm succeeds or not depends on the initial configuration, which is chosen at random, and the authors only give empirical evidence that it seems to take a polynomial number of trials until it succeeds.
Tsuyoshi Ito
CC BY-SA 3.0
2013-12-06T13:17:49.533Z
The second reference isn't a proof either. Just because a single feasible solution to n-queens with n=500000 is found, does not mean that it is in P. (It just makes it more likely)
Geoffrey De Smet
CC BY-SA 3.0
2012-09-25T15:46:01.913Z
2012-09-25T15:46:01.913Z
Anshul Singhle
<p>The N-queen problem is this:</p>

<p>Input : N</p>

<p>Output : A placement of N "queens" on an NXN chessboard such that no two queens lie on the same row, column or diagonal.</p>

<p>Doing a google search on this, I found that many slides by many professors claim this is an NP-Hard problem.(eg. web.mst.edu/~ercal/387/slides/NP-Hard.ppt)</p>

<p>However I havent been able to find a proof (or derive one).
The reason I ask this question is because I think I have an algorithm that solves certain instances of the problem i.e. with N not a multiple of 2 or 3 (N is the number of queens)
Related Issue - Can we consider the input size to be N (where N is the number of queens)? Or do we take the input size to be log(N), since the number 'N' can be represented in log(N) bits? </p>

CC BY-SA 3.0
2012-09-21T13:01:53.903Z
(1) Why do you use both N and n?  Are they the same variable or different variables?  (2) For every integer n except for 2 and 3, there is a way to put n queens on the n×n board satisfying the n-queen condition (see [Wikipedia](http://en.wikipedia.org/wiki/Eight_queens_puzzle)), so I do not know what problem you are talking about when you say “this is an NP-hard problem.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-21T13:02:57.707Z
I recall there is a hardness result when the board is not necessarily square: i.e., board shape is given as part of the input.
Sasho Nikolov
CC BY-SA 3.0
2012-09-21T13:13:26.280Z
There can't be an NP-completeness proof for the $n \times n$ chessboard, because this problem has unary input ... that is, there is only one input for size $n$, while the witness needs a polynomial-size description. Mahaney's theorem says that showing a problem like this to be NP-complete would imply that P = NP. You need funny board shapes for the problem to be NP-complete.
Peter Shor 
CC BY-SA 3.0
2012-09-21T15:16:04.407Z
AS re TIs comment, it has to be turned into some kind of decision problem with a Y/N answer to study its hardness. what can be said is that all known solutions require at least Exptime to compute the function that returns positions/layouts passing the constraints.
vzn
CC BY-SA 3.0
2012-09-21T15:30:00.170Z
?! actually here is a ref that says its in P time. [A polynomial time algorithm for the N-Queens problem](http://dl.acm.org/citation.cfm?id=101343) by Sosic & Gu. [PPT slides](http://www.mcl.ie.cuhk.edu.hk/internal/2003_seminars/20030731_alex_n-queen.ppt). (apparently probabilistic attack?)
vzn
CC BY-SA 3.0
2012-09-21T15:49:38.087Z
Perhaps counting the solutions is a little more interesting problem (beyond #P class as proved in "On the hardness of countingproblems of complete mappings").
Marzio De Biasi
CC BY-SA 3.0
2012-09-21T16:56:25.257Z
At best it could be in one of the search classes like PPAD etc, given that for any N there's always a solution.
Suresh Venkat
CC BY-SA 3.0
2012-09-21T20:47:52.220Z
It is not our duty to guess how the question might make sense. As asked, the question has a trivial answer, already provided by Tsuyoshi. Either Anshul should edit the question and make some sense of it, or we downvote. Like I am. Because it is a badly phrased question.
Andrej Bauer
CC BY-SA 3.0
2012-09-21T21:58:13.380Z
See also: http://dl.acm.org/citation.cfm?id=122322
Jeffε
CC BY-SA 3.0
2012-09-22T12:18:10.667Z
@vzn: A quibble. There are lots of ways of studying the hardness of problems which don't have yes/no answers. Technically, these problems cannot be NP-complete, but they can be NP-hard.
Peter Shor 
CC BY-SA 3.0
2012-09-22T15:05:56.200Z
ok @peter agreed but that distinction is somewhat subtle to beginners and seemingly glossed over in many accts & Ive not seen a good summary/overview of how it works, leading to some confusion. like the above poster talking about professors saying the problem is in NP-- yes that seems to happen a lot where the problem being in NP is due to some special construction [eg here it is apparently due to irregular board layouts], but the shorthand on slides or whatever is only "its in NP".
vzn
CC BY-SA 3.0
2012-09-25T15:13:10.410Z
what I can't understand is what people mean in slides such as here:
web.mst.edu/~ercal/387/slides/NP-Hard.ppt
The slide says that most combinatorial optimization problems are hard and then goes on to say that "N-queens problem" is a popular NP-Hard problem.
As someone pointed out, there is a theorem that states the solutions always exist for the n-queens problem. However, finding those solutions is quite hard (based on what i've read).
I am aware that NP-hard problems need to be formulated as decision problems, which is why I was confused regarding this claim. It's much clearer now, thanks!
Anshul Singhle
<cc.complexity-theory><np-hardness><csp>
Is the N Queens problem NP-hard?
Anshul Singhle
# Is the N Queens problem NP-hard?

(Asked by: username_0 on 2012-09-21)

The N-queen problem is this:

Input : N

Output : A placement of N "queens" on an NXN chessboard such that no two queens lie on the same row, column or diagonal.

Doing a google search on this, I found that many slides by many professors claim this is an NP-Hard problem.(eg. web.mst.edu/~ercal/387/slides/NP-Hard.ppt)

However I havent been able to find a proof (or derive one).
The reason I ask this question is because I think I have an algorithm that solves certain instances of the problem i.e. with N not a multiple of 2 or 3 (N is the number of queens)
Related Issue - Can we consider the input size to be N (where N is the number of queens)? Or do we take the input size to be log(N), since the number 'N' can be represented in log(N) bits?

**Tags:** cc.complexity-theory, np-hardness, csp

> **Comments:**
> **username_1**: (1) Why do you use both N and n?  Are they the same variable or different variables?  (2) For every integer n except for 2 and 3, there is a way to put n queens on the n×n board satisfying the n-queen condition (see [Wikipedia](http://en.wikipedia.org/wiki/Eight_queens_puzzle)), so I do not know what problem you are talking about when you say “this is an NP-hard problem.”  
> **username_2**: I recall there is a hardness result when the board is not necessarily square: i.e., board shape is given as part of the input.  
> **username_3**: There can't be an NP-completeness proof for the $n \times n$ chessboard, because this problem has unary input ... that is, there is only one input for size $n$, while the witness needs a polynomial-size description. Mahaney's theorem says that showing a problem like this to be NP-complete would imply that P = NP. You need funny board shapes for the problem to be NP-complete.  
> **username_4**: AS re TIs comment, it has to be turned into some kind of decision problem with a Y/N answer to study its hardness. what can be said is that all known solutions require at least Exptime to compute the function that returns positions/layouts passing the constraints.  
> **username_4**: ?! actually here is a ref that says its in P time. [A polynomial time algorithm for the N-Queens problem](http://dl.acm.org/citation.cfm?id=101343) by Sosic & Gu. [PPT slides](http://www.mcl.ie.cuhk.edu.hk/internal/2003_seminars/20030731_alex_n-queen.ppt). (apparently probabilistic attack?)  
> **username_5**: Perhaps counting the solutions is a little more interesting problem (beyond #P class as proved in "On the hardness of countingproblems of complete mappings").  
> **username_6**: At best it could be in one of the search classes like PPAD etc, given that for any N there's always a solution.  
> **username_7**: It is not our duty to guess how the question might make sense. As asked, the question has a trivial answer, already provided by Tsuyoshi. Either Anshul should edit the question and make some sense of it, or we downvote. Like I am. Because it is a badly phrased question.  
> **username_8**: See also: http://dl.acm.org/citation.cfm?id=122322  
> **username_3**: @username_4: A quibble. There are lots of ways of studying the hardness of problems which don't have yes/no answers. Technically, these problems cannot be NP-complete, but they can be NP-hard.  
> **username_4**: ok @peter agreed but that distinction is somewhat subtle to beginners and seemingly glossed over in many accts & Ive not seen a good summary/overview of how it works, leading to some confusion. like the above poster talking about professors saying the problem is in NP-- yes that seems to happen a lot where the problem being in NP is due to some special construction [eg here it is apparently due to irregular board layouts], but the shorthand on slides or whatever is only "its in NP".  
> **username_0**: what I can't understand is what people mean in slides such as here: web.mst.edu/~ercal/387/slides/NP-Hard.ppt The slide says that most combinatorial optimization problems are hard and then goes on to say that "N-queens problem" is a popular NP-Hard problem. As someone pointed out, there is a theorem that states the solutions always exist for the n-queens problem. However, finding those solutions is quite hard (based on what i've read). I am aware that NP-hard problems need to be formulated as decision problems, which is why I was confused regarding this claim. It's much clearer now, thanks!  

---

## 2 answers

### Answer by username_0 on 2012-09-25. Score: 8 | Accepted answer

As stated, the answer to this question is NO.

References :
A polynomial time algorithm <http://dl.acm.org/citation.cfm?id=101343> [courtesy: username_4]

Another much simpler technique : <http://dl.acm.org/citation.cfm?id=122322> [courtesy: Jeffe]

> **Comments:**
> **username_6**: you might consider accepting this answer so it doesn't keep reappearing as unanswered.  
> **username_1**: The polynomial-time algorithm in the first reference is not guaranteed to produce a solution.  Whether the algorithm succeeds or not depends on the initial configuration, which is chosen at random, and the authors only give empirical evidence that it seems to take a polynomial number of trials until it succeeds.  
> **username_12**: The second reference isn't a proof either. Just because a single feasible solution to n-queens with n=500000 is found, does not mean that it is in P. (It just makes it more likely)  

---

### Answer by username_9 on 2017-09-02. Score: 0

Actually, this has just been shown to be the case.

<https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/>
]

> **Comments:**
> **username_10**: No, it hasn't. Read the article, or even its abstract: it deals with $N$-queens **completion**, a *variant* of the problem.  
> **username_11**: @ClementC. Actually, since the original question is not precise enough, I think username_9 has a point even if his way of stating it may be incomplete. Deciding, given n, if there exists a placement is clearly in P since the problem always has solutions for n>3.  Thus, n-queens completion problem (deciding if one can extend a given partial solution) seems a natural decision problem to look at to understand the complexity of the problem.  
> **username_10**: @username_11 That's indeed a valid point *you* make, but one that this answer does not even mention (and that a reader would absolutely not get by reading it). Having a misleading answer to an ambiguous question is not exactly optimal.  

---

