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

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 :)