Re:Mathematician answers chess problem about attacking queens
by CJefferson on Tuesday September 21, 2021 @01:11PM
(#28607200)
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.
[ Parent
| on HN ]
Re:Mathematician answers chess problem about attacking queens
by kevinwang on Tuesday September 21, 2021 @01:15PM
(#28607245)
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?
Re:Mathematician answers chess problem about attacking queens
by CJefferson on Tuesday September 21, 2021 @01:25PM
(#28607356)
NP-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 :)