# Is the n-Queens problem only np-complete for the task of finding all setups or also for finding any solution?

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 '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 Answer

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.