I have read on Wikipedia that the n-Queens problem is NP-complete when it comes to finding all possible solution implies it that finding one possible solution is also NP-complete?

  • So it would follow the problem to find a single solution is in $\mathcal{O}(1)$ ("These solutions exhibit stair-stepped patterns")? Would you like to formulate it in an answer, I mean I could also delete it but I think it could be very interesting to other people. – baxbear Sep 14 at 14:56
  • The article you referenced doesn't say what you claim. There's a particular decision problem, whether you can complete a position in which some queens are already placed, which was shown to be NP-complete. As a result counting all the solutions to the same problem is #P-complete. This is different than the general n-queens problem where you have freedom to place all the queens. – Kyle Jones Sep 15 at 17:07
up vote 1 down vote accepted

The Wikipedia article states "If the goal is to find a single solution, one can show solutions exist for all n ≥ 4 with no search whatsoever." This means that it is easy to find a solution even though it is hard to find all solutions.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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