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.)
This link cites a "well known" explicit solution. It can be computed in linear time:
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).
Do you mean finding one solution or all solutions? If you only want to find one solution, this can be done trivially, according to Wikipedia.
Explicit solutions exist for placing n queens on an n × n board, requiring no combinatorial search whatsoever.
