3 ms·
Interesting, 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?
by kevinwang 5y ago
Interesting, 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?