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?

  • 6
    $\begingroup$ (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), so I do not know what problem you are talking about when you say “this is an NP-hard problem.” $\endgroup$ Sep 21, 2012 at 13:01
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 21, 2012 at 13:02
  • 28
    $\begingroup$ 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. $\endgroup$ Sep 21, 2012 at 13:13
  • 2
    $\begingroup$ Perhaps counting the solutions is a little more interesting problem (beyond #P class as proved in "On the hardness of countingproblems of complete mappings"). $\endgroup$ Sep 21, 2012 at 15:49
  • 3
    $\begingroup$ See also: dl.acm.org/citation.cfm?id=122322 $\endgroup$
    – Jeffε
    Sep 21, 2012 at 21:58

2 Answers 2


As stated, the answer to this question is NO.

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

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

  • $\begingroup$ you might consider accepting this answer so it doesn't keep reappearing as unanswered. $\endgroup$ Sep 25, 2012 at 15:54
  • 12
    $\begingroup$ 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. $\endgroup$ Sep 25, 2012 at 16:38
  • 4
    $\begingroup$ 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) $\endgroup$ Dec 6, 2013 at 13:17

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/ ]

  • 8
    $\begingroup$ No, it hasn't. Read the article, or even its abstract: it deals with $N$-queens completion, a variant of the problem. $\endgroup$
    – Clement C.
    Sep 2, 2017 at 3:09
  • 1
    $\begingroup$ @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. $\endgroup$
    – holf
    Sep 2, 2017 at 5:36
  • 3
    $\begingroup$ @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. $\endgroup$
    – Clement C.
    Sep 2, 2017 at 11:29

Your Answer

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

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