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?
Asked
Active
Viewed 64 times
1
-
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 '18 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 '18 at 17:07
1 Answers
1
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.
Somos
- 35,251
- 3
- 30
- 76