News for hackers. Stuff that matters.
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 :)

Re:Mathematician answers chess problem about attacking queens by bjourne on Tuesday September 21, 2021 @01:50PM (#28607640)
But you can easily phrase it as an NP-hard problem: Are there at least X unique solutions to a board of particular size?