Why does the ratio between total solutions and unique solutions to the n-Queens Problem converge to 8?

64 Views Asked by At

Taking a look at the total solutions and unique solutions to the n-Queens Problem posted here (How many solutions are there to an $n$ by $n$ queens problem?) I realized that the ratio between the total number of solutions and the number of unique solutions converges fast to $8$ as $n$ grows... why? Does it have to do with the existence of three axis of simmetries (lines, columns, and diagonals)?

Thanks in advance!

1

There are 1 best solutions below

0
On BEST ANSWER

I found that in the OEIS Sequence for the unique solutions to the n-Queens Problem described in the link of the OP, the formula to obtain the unique solutions is precisely (I copy from OEIS):

a(n) = (1/8) * (Q(n) + P(n) + 2 * R(n)), where Q(n) = A000170(n) [all solutions], P(n) = A032522(n) [point symmetric solutions] and R(n) = A033148(n) [rotationally symmetric solutions].

As $Q(n)$ grows much faster than $P(n)$ and $R(n)$, convergence of $\frac{Q(n)}{a(n)}$ to $8$ is explained. The factor $\frac{1}{8}$ in the formula for $a(n)$ has been already explained by @WillJagy in the comments to the OP, pointing out that the symmetry group of the square has eight elements.