2
$\begingroup$

The OEIS lists the number of solutions of N-queens problem (Number of ways of placing n nonattacking queens on an n X n board). However, no formula is given. It is easy to observe that each number in the sequence is more than double its predecessor.

Is there any proven asymptotic exponential lower bound on the number of solutions?

$\endgroup$
1
$\begingroup$

Let $Q(N)$ be the number we are interested in. In Corollary 1 on the paper below it is proven that $Q(N) > 4^{N/5}$ for any $N$ divisible by $5$. They also conjecture that $\lim_{n \to \infty} \frac{log Q(n)}{n \log n} > 0$

Rivin, Igor; Vardi, Ilan; Zimmermann, Paul, The $n$-queens problem, Am. Math. Mon. 101, No. 7, 629-639 (1994). ZBL0825.68479.

You may also be interested in arXiv:1705.05225 by Zur Luria where Theorem 1.1 gives a lower bound on the toroidal version (hence, also the usual version) of the problem of $n^{\Omega(n)}$ fro $n = 2^{2k}+1$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.