And is finding any solution for a given n known to be in P? I saw a paper that found solutions up to 500,000 using a probabilistic method but wasn't sure if it was definitively proven to be in P or not.
And is finding any solution for a given n known to be in P? I saw a paper that found solutions up to 500,000 using a probabilistic method but wasn't sure if it was definitively proven to be in P or not.
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 :)
However, when n is given in unary (meaning we have poly(n) time to find and output a solution), there is a 19th century German-language paper by Pauls that explicitly and efficiently constructs an n-queens solution for all n>3. So the unary version of the problem is in FP (the search version equivalent of P).
tl;dr a solution to n-queens can be found in deterministic poly(n) time.