Technically the answer to the second question is "no" when n is given in binary. As a valid output is Omega(n log n) bits in length, we can't hope to construct

Technically the answer to the second question is "no" when n is given in binary. As a valid output is Omega(n log n) bits in length, we can't hope to construct a solution in time polynomial in the input size, i.e. time poly(log n). 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.