News for hackers. Stuff that matters.
Re:Mathematician answers chess problem about attacking queens by CaptainNegative on Tuesday September 21, 2021 @01:26PM (#28607362)
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.

There are no comments on this comment yet.