4 ms·
Checking if a partially filled in n-queens problem has a solution at all is NP complete. It might be there is an easy way of counting solutions for an empty gri
by CJefferson 5y ago
Checking if a partially filled in n-queens problem has a solution at all is NP complete. It might be there is an easy way of counting solutions for an empty grid, but usually the way we count solutions is divide and conquer, by giving different computers partially filled in grids.
- kevinwang 5y agoInteresting, so we don't know that it's np hard, but we basically assume it is? Do you know if anyone has tried to prove that it is?
- CJefferson 5y agoNP-hardness is about yes/no questions, and we already know thwre is an answer to all n-queens instances except 2 and 3 :) It also can't really be #P (which is to do with hardness of counting), as that has to do with "input problem size", and N-queens with an empty grid doesn't have enough structure (as it's just a number) -- this is hard to explain in full in a short message :)
- bjourne 5y agoBut you can easily phrase it as an NP-hard problem: Are there at least X unique solutions to a board of particular size?