10
$\begingroup$

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?

$\endgroup$
  • 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$ – Tsuyoshi Ito Sep 21 '12 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$ – Sasho Nikolov Sep 21 '12 at 13:02
  • 27
    $\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$ – Peter Shor Sep 21 '12 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$ – Marzio De Biasi Sep 21 '12 at 15:49
  • 3
    $\begingroup$ See also: dl.acm.org/citation.cfm?id=122322 $\endgroup$ – Jeffε Sep 21 '12 at 21:58
7
$\begingroup$

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]

$\endgroup$
  • $\begingroup$ you might consider accepting this answer so it doesn't keep reappearing as unanswered. $\endgroup$ – Suresh Venkat Sep 25 '12 at 15:54
  • 11
    $\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$ – Tsuyoshi Ito Sep 25 '12 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$ – Geoffrey De Smet Dec 6 '13 at 13:17
1
$\begingroup$

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

$\endgroup$
  • 5
    $\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 '17 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 '17 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 '17 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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