  In how many ways can $n$ queens be placed on an $n \times n$ 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.
