New bounds on the number of n-queens configurations

MaRDI QIDQ6286691zbMATH OpenFDO

Authors Zur Luria

Publication date 15 May 2017

Abstract: In how many ways can $n$ queens be placed on an $nimesn$ chessboard so that no two queens attack each other? This is the famous $n$-queens problem. Let $Q(n)$ denote the number of such configurations, and let $T(n)$ be the number of configurations on a toroidal chessboard. We show that for every $n$ of the form $4^k+1$, $T(n)$ and $Q(n)$ are both at least $n^{Omega(n)}$. This result confirms a conjecture of Rivin, Vardi and Zimmerman for these values of $n$. We also present new upper bounds on $T(n)$ and $Q(n)$ using the entropy method, and conjecture that in the case of $T(n)$ the bound is asymptotically tight. Along the way, we prove an upper bound on the number of perfect matchings in regular hypergraphs, which may be of independent interest.

This page was built for publication: New bounds on the number of n-queens configurations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6286691)