What is the best complexity of N-Queens puzzle?

Question

Can the N-Queens puzzle theoretically be solved in polynomial time? If so, what is the best complexity of it? I have found many algorithms, but I haven't found what exactly the time complexity is. Are there any papers or documents giving an exact number of its complexity?

(P.S. The explicit solution is very interesting, but I forgot to say, I wish to find all the solutions.)

Answer 1

This link cites a "well known" explicit solution. It can be computed in linear time:

http://www.chegg.com/homework-help/questions-and-answers/poor-man-s-n-queens-problemn-queens-arranged-n-x-n-chessboard-way-queen-checks-queen-queen-q1009394

1. n is even but not of the form (n mod 6 = 2). Place queens on the squares (m, 2m) and (n/2 +m, 2m-1) for m = 1, 2, . . . , n/2

2. n is even but not of the form (n mod 6 = 0) and Place queens on the squares (m, 1+(2(m-1)+ n/2 - 1)mod n) and (n+1-m, n-(2(m-1)+n/2 -1)mod n) for m = 1,2,...,n/2

3. n is odd. Use (1) or (2), whichever is appropriate, on n - 1 and extend with a queen at (n,n).

Note that enumerating all solutions would take much longer. The number of solutions grows super-exponentially with the size of the board (http://oeis.org/A000170), so they are impossible to enumerate even with 2^O(x) time (but only O(n) space is needed).