N-Queens Problem Asymptotics

Asymptotic Enumeration of Nonattacking Queens

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

Represent a placement of $n$ queens by a permutation $\pi$ of $[n]$: the queens occupy $(i,\pi(i))$. Nonattack additionally requires the numbers $i-\pi(i)$ to be distinct and the numbers $i+\pi(i)$ to be distinct. Let $Q(n)$ count such permutations on the labelled board, without identifying rotations or reflections. The target is an asymptotic formula for this count. [S1] [S2]

Statement recorded in the supplied source.

In how many ways (asymptotically) $Q(n)$ may $n$ non-attacking queens be placed on an $n \times n$ chessboard? [S1]

Scope and interpretation.

The archive reports the leading logarithmic asymptotic as established. The residual question is an asymptotic enumeration beyond that precision; the known exponential-scale estimate is not being relabelled as open. [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Obtain an asymptotic formula with multiplicative relative error, or otherwise determine the subexponential factor beyond Simkin's exponential rate. [S1]

Short English statement

How many ways can n mutually nonattacking queens be placed on a labelled n by n board, to asymptotically precise accuracy?

Research attempt

Provenance and scope.

This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.

Formal target and existing leading asymptotic.

A labelled placement is a permutation $\pi$ of $[n]$ such that both lists $i-\pi(i)$ and $i+\pi(i)$ have distinct entries. Rotations and reflections are not identified. Simkin's inspected paper determines the leading exponential rate, of the form $Q(n)=((1+o(1))ne^{-\alpha})^n$ for a variational constant $\alpha$. The remaining target asks for finer, relative-error enumeration. We examine a natural independent-attack approximation, compute its exact first moment, and compare its information content with the precision required.

Exact expected number of diagonal conflicts.

Choose a uniform random permutation $\pi$, which already enforces one queen in every row and column. Let $D$ count attacking unordered pairs of rows. For rows at distance $d$, their ordered column values are uniform among $n(n-1)$ distinct pairs. Exactly $2(n-d)$ such pairs have column distance $d$, so the attack probability is $2(n-d)/(n(n-1))$. There are $n-d$ row pairs at that distance. Therefore \[ {\mathbb{E}} D=\frac{2}{n(n-1)}\sum_{d=1}^{n-1}(n-d)^2 =\frac{2n-1}{3} \] for $n\geq2$. The sum uses $\sum_{j=1}^{n-1}j^2=(n-1)n(2n-1)/6$. This calculation is exact and counts both diagonal directions without double-counting: two distinct queens cannot lie on both kinds of diagonal.

Also $Q(n)=n!\Pr(D=0)$. Treating the conflicts as approximately independent with this mean would suggest $\Pr(D=0)\approx e^{-2n/3}$ and hence an exponential constant $1+2/3=5/3$ after Stirling's formula. This differs from the established variational constant near $1.94$. The approximation therefore misses a leading-order effect, not merely a small prefactor.

Dependence is visible in the smallest nontrivial board.

For $n=3$, let $E_{12}$ and $E_{23}$ be the events that queens in the indicated adjacent rows attack. Each has probability $2/3$ by the preceding formula. Their intersection occurs only for the increasing and decreasing permutations, so it has probability $2/6=1/3$, rather than $(2/3)^2=4/9$. The events are not independent. This finite example does not quantify the full large-$n$ dependency structure, but it identifies the failed premise in the product-of-probabilities argument exactly.

Inclusion-exclusion is valid in principle: sum over collections of forbidden diagonal-pair events with alternating signs. Its terms depend on whether their imposed row-column constraints are mutually compatible. Replacing all those intersection probabilities by products loses that compatibility data. A relative asymptotic would require much more delicate control than the first moment or a finite number of local corrections.

A verified infinite family for a basic existence check.

On a board indexed by ${\mathbb{Z}}/n{\mathbb{Z}}$, suppose $\gcd(n,6)=1$ and take $\pi(i)=2i+b\pmod n$, with least nonnegative representatives and arbitrary $b$. Columns are distinct because two is invertible. The residues $\pi(i)-i=i+b$ are distinct, and so are $\pi(i)+i=3i+b$, because three is invertible. Any ordinary diagonal equality would imply one of these forbidden modular equalities. Thus these are valid ordinary-board placements, giving at least $n$ distinct solutions for such $n$. This is only a simple baseline; it is enormously smaller than the known true count and is not an asymptotic enumeration method.

Finite enumeration and its convention checks.

The companion backtracking script places queens row by row, rejecting used columns and used values of row minus column or row plus column. It obtains \[ Q(1),\ldots,Q(10)=1,0,0,2,10,4,40,92,352,724. \] The algorithm counts every permutation once and does not quotient by board symmetries. These counts check the diagonal convention and demonstrate that the samplewise existence statement has exceptional small sizes. They do not certify any extrapolation of a prefactor or periodic correction.

The exact precision gap.

From the known exponential-rate statement one gets $\log Q(n)=n\log n-\alpha n+o(n)$. Multiplying a candidate approximation by $e^{\sqrt n}$ or $e^{-\sqrt n}$ leaves that logarithmic statement unchanged, while changing the relative ratio without bound or driving it to zero. Therefore an $o(n)$ logarithmic error cannot be relabelled as a multiplicative $1+o(1)$ error. The original leading theorem is already established; this attempt does not claim to prove it anew.

The checked output is the exact conflict first moment, an explicit dependence calculation, a modular family, and finite labelled counts. The unresolved step is sufficiently sharp control of the constrained-permutation partition function to identify subexponential factors, with errors on the logarithmic scale tending to zero if a true relative asymptotic is claimed.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1097 (GREEN-097), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Michael Simkin, The number of n-queens configurations, Advances in Mathematics 427 $2023$, 109127. https://doi.org/10.1016/j.aim.2023.109127. Bibliographic information from the supplied record.

• S3 Parth Nobel, Akshay Agrawal, and Stephen Boyd, Computing tighter bounds on the n-queens constant via Newton's method, Optimization Letters 17 $2023$, 1229-1240. https://doi.org/10.1007/s11590-022-01933-2. Bibliographic information from the supplied record.

• S4 Ben Green, 100 Open Problems, Problem 97, updates through December 2025;. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf. The author-hosted document was inspected on 27 September 2026; the archive’s local code is not a problem-number locator in this paper.

• E1 M. Simkin, The number of $n$-queens configurations. https://arxiv.org/abs/2107.13460. Inspected 1 October 2026.