[Math] How to calculate the total number of unique solutions for the n queen puzzle

polynomialspuzzle

Constructing a fairly optimized algorithm for finding all the possible solutions for the n queen puzzle is fairly easy, at least for up to 20 queens.

Is there a way though to calculate the number of distinct solutions, as well as as the number of fundamental positions without actually waiting for the algorithm to finish and then counting those solutions?

Best Answer

The number of solutions $a(n)$ to the $n$-queen problem is the content of OEIS A000710. In particular, no closed-form formula seems to be known, but the OEIS entry includes an conjecture attributed to Benoit Cloitre:

There is a constant $c$ around $2.54$ such that $a(n)$ is asymptotic to $$\frac{n!}{c^n} .$$

Apparently $a(n)$ has only been computed for $n \leq 26$.

For a detailed and relatively recent survey, see

Bell, J., and Stevens, B. "A survey of known results and research areas for $n$-queens [PDF]." Discrete Mathematics 309 (2009), pp. 1–31.

Related Question