solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看227次
New bounds on the number of n-queens configurations. (arXiv:1705.05225v2 [math.CO] UPDATED)
来源于:arXiv
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. 查看全文>>