12

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?

Anshul Singhle
  • 365
  • 1
  • 3
  • 7
  • 6
    (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.” – Tsuyoshi Ito Sep 21 '12 at 13:01
  • 3
    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 Sep 21 '12 at 13:02
  • 28
    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 Sep 21 '12 at 13:13
  • 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 Sep 21 '12 at 15:16
  • ?! actually here is a ref that says its in P time. A polynomial time algorithm for the N-Queens problem by Sosic & Gu. PPT slides. (apparently probabilistic attack?) – vzn Sep 21 '12 at 15:30
  • 2
    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 Sep 21 '12 at 15:49
  • 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 Sep 21 '12 at 16:56
  • 2
    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 Sep 21 '12 at 20:47
  • 3
    See also: http://dl.acm.org/citation.cfm?id=122322 – Jeffε Sep 21 '12 at 21:58
  • @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 Sep 22 '12 at 12:18
  • 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 Sep 22 '12 at 15:05
  • 1
    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 Sep 25 '12 at 15:13

2 Answers2

8

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]

Anshul Singhle
  • 365
  • 1
  • 3
  • 7
  • you might consider accepting this answer so it doesn't keep reappearing as unanswered. – Suresh Venkat Sep 25 '12 at 15:54
  • 12
    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 Sep 25 '12 at 16:38
  • 4
    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 Dec 06 '13 at 13:17
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/ ]

Kasper
  • 27
  • 1
  • 8
    No, it hasn't. Read the article, or even its abstract: it deals with $N$-queens completion, a variant of the problem. – Clement C. Sep 02 '17 at 03:09
  • 1
    @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 02 '17 at 05:36
  • 3
    @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. Sep 02 '17 at 11:29