# Is the N Queens problem NP-hard?

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?

• (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.” Sep 21 '12 at 13:01
• 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. Sep 21 '12 at 13:02
• 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. Sep 21 '12 at 13:13
• Perhaps counting the solutions is a little more interesting problem (beyond #P class as proved in "On the hardness of countingproblems of complete mappings"). Sep 21 '12 at 15:49

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]

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

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

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