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?
[ Parent
| on HN ]
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 :)