"Strong conjecture : there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n"
That would imply that a(n) grows faster than polynomial. That, in turn, would mean that merely counting the number of solutions cannot be done in polynomial time.
N-Queens, by the way, becomes simple once you realize that you cannot have two queens at (p,q) and (r,s) if any of the following is true:
p = r
q = s
p-q = r-s
p+q = r+s
(The first two check for horizontal and vertical attacks, last two for diagonal ones)
"Strong conjecture : there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n"
That would imply that a(n) grows faster than polynomial. That, in turn, would mean that merely counting the number of solutions cannot be done in polynomial time.
N-Queens, by the way, becomes simple once you realize that you cannot have two queens at (p,q) and (r,s) if any of the following is true:
(The first two check for horizontal and vertical attacks, last two for diagonal ones)Real programmers implement Knuth's dancing links (http://arxiv.org/pdf/cs.DS/0011047.pdf) and use it to solve a way larger class of problems.