What is the best complexity of N-Queens puzzle?
algorithm, complexity-theory, n-queens
Solution
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
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
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
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).
Problem
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.)