betaFeedback

WorksMathematics

Modular nn-queens in higher dimensions

Abstract

A chess queen in dd-dimensions can move any distance in the direction of any edge or diagonal of the dd-dimensional hypercube. (That is, a queen can move from a position xx to x+cvx+cv for any cc and any nonzero v∈{−1,0,1}dv\in\{-1,0,1\}^d.) We prove that one can place nd−1n^{d-1} non-attacking queens on the dd-dimensional modular board (Z/nZ)d(\mathbb Z/n\mathbb Z)^d if and only if all prime factors of nn exceed 2d2^d. The d=3d=3 case of this result is a conjecture of van Rees from 1981. Our proof involves both human ideas and substantial AI assistance.

Introduction

The nn-queens problem is one of the oldest in combinatorics. The modular version, where attacks may wrap around the edges of the board, dates back at least to 1918, when Pólya [10] proved that nn mutually non-attacking queens can be placed on a modular nn-by-nn chessboard if and only if nn is not a multiple of 2 or 3. In this article, we establish an analogous result for the higher-dimensional version of the problem.

Let n,d>1n,d>1 be integers. We will consider placing “queens” on elements of (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^{d}. Two queens in positions x,y∈(Z/nZ)dx,y \in(\mathbb{Z}/n\mathbb{Z})^{d} are said to attack each other if their difference x−yx-y is a scalar multiple of some nonzero element of {−1,0,1}d\{-1,0,1\}^{d}. It is clear that one cannot place more than nd−1n^{d-1} non-attacking queens in (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^{d}, since no two non-attacking queens may share their first d−1d-1 coordinates. Our main result is to provide necessary and sufficient conditions under which this bound can be attained.

Theorem 1.1. Let d≥2d \ge2. One can place nd−1n^{d-1} non-attacking queens on (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^{d} if and only if all prime factors of nn exceed 2d2^{d}.

History

In 1980, Klarner proved the sufficiency direction of Theorem 1.1 in the case d=3d=3 [5] with an explicit construction. Klarner’s construction naturally generalizes to prove the sufficiency direction of Theorem 1.1 for all dd (see, for example, [4 Corollary 8.2] and [Wil26, Theorem 1]). The new contribution here is the necessity direction.

The d=3d=3 case of Theorem 1.1 was conjectured by van Rees in 1981 [vR81, Conjecture-3.2]. Independently, Allison, Yee, and McGaughey made the same conjecture in [1] (though in the literature the conjecture is usually attributed to van Rees). In their literature review, Bell and Stevens reproduced the conjecture as [3 Conjecture 24] and also posed the conjecture for d≥3d \ge3 (which Theorem 1.1 verifies) as [3 Conjecture 25].

Pólya’s result [10] for d=2d=2 implies an analogous result for d≥2d \ge2: if nd−1n^{d-1} non-attacking queens can be placed in (Z/nZ)3(\mathbb{Z}/n\mathbb{Z})^{3}, then 2∤n2 \nmid n and 3∤n3 \nmid n. The only other progress in this direction (to our knowledge) is a 2026 result of Williams [Wil26, Theorem 4], who showed that, for d=3d=3, either 5∤n5 \nmid n or 25∣n25 \mid n. Williams’ approach is similar to that of Pólya, in that it involves summing polynomials in Z[x,y,z]\mathbb{Z}[x,y,z] over the queen positions (x,y,z)∈(Z/nZ)3(x,y,z) \in(\mathbb{Z}/n\mathbb{Z})^{3}. Our approach is different; we use multiplicative characters of (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^{d} (that is, Fourier analysis) rather than polynomials. This seems to produce stronger results; it is an intriguing question whether the approach with polynomials can be stated in a Fourier-theoretic framework.

We remark additionally that the nn-queens problem is quite storied and there have been multiple variants of the problem proposed in higher dimensions, some of which we discuss later. See the survey of Bell and Stevens [3] and the master’s thesis of Kunt [6] for references.

Organization

We give a proof of the sufficiency direction of Theorem 1.1 (which is not new here) in Section 2. We prove the necessity direction in Section 3. In Section 4, we discuss some variants of the nn-queens problem and some potential extensions of our work.

Our proof of Theorem 1.1 was produced in collaboration with AI. We outline this process and describe the sources behind the various ideas in the proof in Appendix A.

Sufficiency

In this section, we prove the sufficiency direction of Theorem 1.1: if all prime factors of nn are greater than 2d2^d, then nd−1n^{d-1} non-attacking queens can be placed on (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d. This argument is a simple extension of the arguments used in the d=2d=2 case and appears, for example, as [Wil26, Theorem 1] and [4 Corollary 8.2]. The argument in the d=3d=3 case is due to Klarner [5]. We present the full argument here for completeness.

Proof of Theorem 1.1, sufficiency direction. Let ξ:=(1,2,4,…,2d−1)\xi:= (1,2,4,\ldots,2^{d-1}). Place a queen in position x∈(Z/nZ)dx \in(\mathbb{Z}/n\mathbb{Z})^d if and only if ⟨ξ,x⟩=0\langle\xi,x\rangle=0. It is clear that nd−1n^{d-1} queens are placed in this way. Assume for the sake of contradiction that two queens at positions xx and yy are attacking. Then, there exists some nonzero j∈Z/nZj \in\mathbb{Z}/n\mathbb{Z} and v∈{−1,0,1}d∖{0}v \in\{-1,0,1\}^d \setminus\{0\} for which x−y=jvx-y=jv. We conclude that

0=⟨ξ,x⟩−⟨ξ,y⟩=j⟨ξ,v⟩=j∑k=0d−12kvk.0=\langle\xi,x\rangle-\langle\xi,y\rangle=j\langle\xi,v\rangle=j\sum_{k=0}^{d-1}2^k v_k.

Let r=∑k=0d−12kvkr=\sum_{k=0}^{d-1}2^k v_k. Write v=u−wv=u-w for distinct u,w∈{0,1}du,w\in\{0,1\}^d. By the uniqueness of binary representation, we have ∑k=0d−12kuk≠∑k=0d−12kwk\sum_{k=0}^{d-1}2^k u_k\ne\sum_{k=0}^{d-1}2^k w_k. We conclude that, as an integer, rr is nonzero. Moreover, ∣r∣≤2d−1|r|\le2^d-1. Therefore, by our assumption on nn, we have gcd⁡(r,n)=1\gcd(r,n)=1. The property jr=0jr=0 for j∈Z/nZj\in\mathbb{Z}/n\mathbb{Z} nonzero provides a contradiction. □

Remark. The configuration of nd−1n^{d-1} non-attacking queens presented in this proof is an affine configuration; that is, the cells at which we place queens form a hyperplane {x:⟨ξ,x⟩=0}\{x:\langle\xi,x\rangle=0\} in (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d. This proof can be easily extended to show that, in fact, such an affine configuration of nd−1n^{d-1} non-attacking queens only exists if nn has no prime factors less than 2d2^d.

Indeed, let ξ∈(Z/nZ)d\xi\in(\mathbb{Z}/n\mathbb{Z})^d, and suppose that p<2dp<2^d is a prime factor of nn. Since p<2dp<2^d, there exist distinct (u1,…,ud),(w1,…,wd)∈{0,1}d(u_1,\ldots,u_d),(w_1,\ldots,w_d)\in\{0,1\}^d such that

∑k=1dukξk≡∑k=1dwkξk(modp).\sum_{k=1}^{d}u_k\xi_k\equiv\sum_{k=1}^{d}w_k\xi_k\pmod{p}.

This implies that

⟨ξ,(np(u1−w1),…,np(ud−wd))⟩=0.\left\langle\xi,\left(\frac{n}{p}(u_1-w_1),\ldots,\frac{n}{p}(u_d-w_d)\right)\right\rangle=0.

So, the set {x:⟨ξ,x⟩=0}\{x:\langle\xi,x\rangle=0\} contains the attacking positions (0,…,0)(0,\ldots,0) and (n(u1−w1)/p,…,n(ud−wd)/p)(n(u_1-w_1)/p,\ldots,n(u_d-w_d)/p), and is thus not a set of non-attacking queens.

Given this, Theorem 1.1 can be rephrased in the following way: given nn and dd, there exists a configuration of nd−1n^{d-1} non-attacking queens on (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d if and only if there exists such an affine configuration.

Necessity

We now verify the other direction of Theorem 1.1. We first set some notation which we will carry through the proof. Let Γ:=(Z/nZ)d\Gamma:= (\mathbb{Z}/n\mathbb{Z})^d and let Vd:={−1,0,1}d∖{0}V_d := \{-1,0,1\}^d \setminus\{0\}. Write ω:=e2πi/n\omega:= e^{2\pi i/n}. For f:Γ→Cf:\Gamma\to\mathbb{C}, define the Fourier transform f^:Γ→C\hat{f}:\Gamma\to\mathbb{C} by

f^(ξ):=∑x∈Γf(x)ω⟨ξ,x⟩.\hat{f}(\xi) := \sum_{x \in\Gamma} f(x)\omega^{\langle\xi,x\rangle}.

Define the convolution of two functions f,g:Γ→Cf,g:\Gamma\to\mathbb{C} by

(f∗g)(x)=∑y∈Γf(y)g(x−y).(f * g)(x) = \sum_{y \in\Gamma} f(y)g(x-y).

We have (f∗g)^(ξ)=f^(ξ)g^(ξ)\widehat{(f*g)}(\xi)=\hat{f}(\xi)\hat{g}(\xi). For y∈Γy \in\Gamma, write δy\delta_y for the function which evaluates to 1 on yy and 0 everywhere else. Note that δ^y(ξ)=ω⟨ξ,y⟩\hat{\delta}_y(\xi)=\omega^{\langle\xi,y\rangle}.

If S⊆ΓS \subseteq\Gamma is a set of nd−1n^{d-1} non-attacking queens, then each line {x+jv:j∈Z/nZ}\{x+jv:j\in\mathbb{Z}/n\mathbb{Z}\} for x∈Γx\in\Gamma and v∈Vdv\in V_d contains exactly one element of SS. We will use the following lemma, which is a special case of [4 Lemma 7.4], to conclude some important properties of the Fourier transform of the indicator function of SS.

Lemma 3.1. Let f:Γ→Zf:\Gamma\to\mathbb{Z}. Let C∈ZC\in\mathbb{Z}. Suppose that, for every x∈Γx\in\Gamma and every v∈Vdv\in V_d, we have

∑j∈Z/nZf(x+jv)=C.\sum_{j\in\mathbb{Z}/n\mathbb{Z}} f(x+jv)=C.

Let ξ∈Γ^∖{0}\xi\in\hat{\Gamma}\setminus\{0\}. If ⟨ξ,v⟩=0\langle\xi,v\rangle=0 for some v∈Vdv\in V_d, then f^(ξ)=0\hat{f}(\xi)=0.

Proof. For each x∈Γx\in\Gamma, we have

∑j∈Z/nZf(x+jv)ω⟨ξ,x+jv⟩=∑j∈Z/nZf(x+jv)ω⟨ξ,x⟩=Cω⟨ξ,x⟩.\sum_{j\in\mathbb{Z}/n\mathbb{Z}} f(x+jv)\omega^{\langle\xi,x+jv\rangle} = \sum_{j\in\mathbb{Z}/n\mathbb{Z}} f(x+jv)\omega^{\langle\xi,x\rangle} = C\omega^{\langle\xi,x\rangle}.

Therefore

f^(ξ)=∑x∈Γf(x)ω⟨ξ,x⟩=1n∑x∈Γ∑j∈Z/nZf(x+jv)ω⟨ξ,x+jv⟩=Cn∑x∈Γω⟨ξ,x⟩=0.\hat{f}(\xi) = \sum_{x\in\Gamma}f(x)\omega^{\langle\xi,x\rangle} = \frac{1}{n}\sum_{x\in\Gamma}\sum_{j\in\mathbb{Z}/n\mathbb{Z}}f(x+jv)\omega^{\langle\xi,x+jv\rangle} = \frac{C}{n}\sum_{x\in\Gamma}\omega^{\langle\xi,x\rangle} =0.

We now explain the strategy behind the proof of Theorem 1.1. Let S⊂ΓS\subset\Gamma be a set of nd−1n^{d-1} non-attacking positions. Lemma 3.1 implies that, if ξ∈Γ^∖{0}\xi\in\hat{\Gamma}\setminus\{0\} is orthogonal to some element of VdV_d, then 1S^(ξ)=0\widehat{\mathbf{1}_S}(\xi)=0. If n<2dn<2^d, then this condition implies that 1S^(ξ)=0\widehat{\mathbf{1}_S}(\xi)=0 for every nonzero ξ∈Γ\xi\in\Gamma. Thus 1S\mathbf{1}_S is constant, which cannot be.

We will generalize this argument by constructing a function g:Γ→Zg:\Gamma\to\mathbb{Z} with the property that g^(ξ)=0\hat{g}(\xi)=0 whenever ξ∈Γ^∖{0}\xi\in\hat{\Gamma}\setminus\{0\} is not orthogonal to any element of VdV_d. For any such gg, by Lemma 3.1, the function 1S∗g\mathbf{1}_S*g will be constant and integer-valued, and so we will have

nd∣∑x∈Γ(1S∗g)(x)=(1S∗g)(0)=1^S(0)g^(0)=nd−1g^(0).n^d \mid\sum_{x\in\Gamma}(\mathbf{1}_S*g)(x)=(\mathbf{1}_S*g)(0)=\hat{\mathbf{1}}_S(0)\hat{g}(0)=n^{d-1}\hat{g}(0).

If n∤g^(0)n\nmid\hat{g}(0), this provides the desired contradiction.

To construct such a gg, we first prove an auxiliary lemma. Given a vector α∈Z≥0r\alpha\in\mathbb{Z}_{\geq0}^r for some rr, we write wt⁡α\operatorname{wt}\alpha for the sum of coordinates of α\alpha.

Lemma 3.2. For a positive integer r≥2r\geq2, write

hn(z1,…,zr):=∑α∈Z≥0rwt⁡α=n−r+1z1α1⋯zrαrh_n(z_1,\ldots,z_r):= \sum_{\substack{\alpha\in\mathbb{Z}_{\geq0}^r\\ \operatorname{wt}\alpha=n-r+1}} z_1^{\alpha_1}\cdots z_r^{\alpha_r}

for the nnth complete homogeneous symmetric polynomial in the variables z1,…,zrz_1,\ldots,z_r. If z1,…,zrz_1,\ldots,z_r are distinct nnth roots of unity, then hn(z1,…,zr)=0h_n(z_1,\ldots,z_r)=0.

Proof. Let t1,…,trt_1,\ldots,t_r be indeterminates. We have

∑n=r−1∞hn(t1,…,tr)=∑α∈Z≥0rt1α1⋯trαr=∏i=1r11−ti.\sum_{n=r-1}^{\infty} h_n(t_1,\ldots,t_r)=\sum_{\substack{\alpha\in\mathbb{Z}_{\geq0}^r}}t_1^{\alpha_1}\cdots t_r^{\alpha_r}=\prod_{i=1}^{r}\frac{1}{1-t_i}.

Now, define the determinants

Dm:=∣1t1t12⋯t1r−2t1m1t2t22⋯t2r−2t2m⋮⋮⋮⋱⋮⋮1trtr2⋯trr−2trm∣.D_m:=\begin{vmatrix} 1&t_1&t_1^2&\cdots&t_1^{r-2}&t_1^m\\ 1&t_2&t_2^2&\cdots&t_2^{r-2}&t_2^m\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 1&t_r&t_r^2&\cdots&t_r^{r-2}&t_r^m \end{vmatrix}.

We compute

∑m=0∞Dm=∣1t1t12⋯t1r−211−t11t2t22⋯t2r−211−t2⋮⋮⋮⋱⋮⋮1trtr2⋯trr−211−tr∣=∣1−t1t1−t12⋯t1r−2−t1r−111−t2t2−t22⋯t2r−2−t2r−11⋮⋮⋱⋮⋮1−trtr−tr2⋯trr−2−trr−11∣∏i=1r11−ti.\sum_{m=0}^{\infty}D_m= \begin{vmatrix} 1&t_1&t_1^2&\cdots&t_1^{r-2}&\frac{1}{1-t_1}\\ 1&t_2&t_2^2&\cdots&t_2^{r-2}&\frac{1}{1-t_2}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 1&t_r&t_r^2&\cdots&t_r^{r-2}&\frac{1}{1-t_r} \end{vmatrix} = \begin{vmatrix} 1-t_1&t_1-t_1^2&\cdots&t_1^{r-2}-t_1^{r-1}&1\\ 1-t_2&t_2-t_2^2&\cdots&t_2^{r-2}-t_2^{r-1}&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1-t_r&t_r-t_r^2&\cdots&t_r^{r-2}-t_r^{r-1}&1 \end{vmatrix}\prod_{i=1}^{r}\frac{1}{1-t_i}.

Performing column operations and permuting the columns,

∑m=0∞Dm=∣1t1⋯t1r−11t2⋯t2r−1⋮⋮⋱⋮1tr⋯trr−1∣∏i=1r11−ti=Dr−1∏i=1r11−ti.\sum_{m=0}^{\infty}D_m= \begin{vmatrix} 1&t_1&\cdots&t_1^{r-1}\\ 1&t_2&\cdots&t_2^{r-1}\\ \vdots&\vdots&\ddots&\vdots\\ 1&t_r&\cdots&t_r^{r-1} \end{vmatrix}\prod_{i=1}^{r}\frac{1}{1-t_i} =D_{r-1}\prod_{i=1}^{r}\frac{1}{1-t_i}.

We conclude that

∑n=r−1∞hn(t1,…,tr)Dr−1=∑m=0∞Dm.\sum_{n=r-1}^{\infty}h_n(t_1,\ldots,t_r)D_{r-1}=\sum_{m=0}^{\infty}D_m.

The nn term on the left is homogeneous of degree n−r+1+(r2)n-r+1+\binom{r}{2}, while the mm term on the right is homogeneous of degree m+(r−12)m+\binom{r-1}{2}. We conclude that hn(t1,…,tr)=Dn/Dr−1h_n(t_1,\ldots,t_r)=D_n/D_{r-1}. (This is a special case of Jacobi’s bialternant formula for Schur polynomials.) Now, evaluate this identity at distinct nnth roots of unity z1,…,zrz_1,\ldots,z_r. Since the first and last columns of the matrix defining DnD_n are equal, we have Dn=0D_n=0. On the other hand, Dr−1D_{r-1} is the determinant of a Vandermonde matrix, so the distinctness of z1,…,zrz_1,\ldots,z_r implies that Dr−1≠0D_{r-1}\ne0. The result follows. □\square

We now construct our auxiliary function gg.

Lemma 3.3. Let r≤2dr\leq2^d, and let y1,…,yry_1,\ldots,y_r be distinct elements of {0,1}d\{0,1\}^d. Define a function g:Γ→Zg:\Gamma\to\mathbb{Z} by

g=∑α∈Z≥0rwtα=n−r+1δα1y1+⋯+αryr.g=\sum_{\substack{\alpha\in\mathbb{Z}_{\geq0}^r\\ \mathrm{wt}\,\alpha=n-r+1}}\delta_{\alpha_1y_1+\cdots+\alpha_ry_r}.

Let ξ∈Γ^∖{0}\xi\in\widehat{\Gamma}\setminus\{0\}. If ⟨ξ,y⟩≠0\langle\xi,y\rangle\ne0 for every y∈Vdy\in\mathcal{V}_d, then g^(ξ)=0\widehat{g}(\xi)=0.

Proof. For 1≤j≤r1\leq j\leq r, let λj=ω⟨ξ,yj⟩\lambda_j=\omega^{\langle\xi,y_j\rangle}. If λj=λk\lambda_j=\lambda_k for some j≠kj\ne k, then ⟨ξ,yj−yk⟩=0\langle\xi,y_j-y_k\rangle=0, which would contradict our assumption that ξ\xi is not orthogonal to any element of Vd\mathcal{V}_d. Therefore, λ1,…,λr\lambda_1,\ldots,\lambda_r are

distinct nnth roots of unity. We now compute

g^(ξ)=∑α∈Z>0rwt⁡α=n−r+1δ^α1y1+⋯+αryr(ξ)=∑α∈Z>0rwt⁡α=n−r+1ω⟨ξ,α1y1+⋯+αryr⟩=hn(λ1,…,λr).\widehat{g}(\xi)=\sum_{\substack{\alpha\in\mathbb{Z}_{>0}^{r}\\ \operatorname{wt}\alpha=n-r+1}}\widehat{\delta}_{\alpha_1y_1+\cdots+\alpha_ry_r}(\xi)=\sum_{\substack{\alpha\in\mathbb{Z}_{>0}^{r}\\ \operatorname{wt}\alpha=n-r+1}}\omega^{\langle\xi,\alpha_1y_1+\cdots+\alpha_ry_r\rangle}=h_n(\lambda_1,\ldots,\lambda_r).

The result thus follows from Lemma 3.2. □

Proof of Theorem 1.1, necessity direction. Let S⊆ΓS\subseteq\Gamma be a set of nd−1n^{d-1} non-attacking queens and let p<2dp<2^d be a prime. We will prove that p∤np\nmid n.

Since SS has size nd−1n^{d-1}, every line {x+jv:j∈Z/nZ}\{x+jv:j\in\mathbb{Z}/n\mathbb{Z}\} for v∈Vdv\in\mathcal{V}_d has exactly one element of SS. In particular, the indicator function 1S\mathbf{1}_S of SS satisfies the precondition of Lemma 3.1.

Now, let y1,…,yp+1y_1,\ldots,y_{p+1} be distinct elements of {0,1}d\{0,1\}^d (we can choose such elements since p<2dp<2^d). Let gg be as in Lemma 3.3. Lemma 3.1 implies that 1S^(ξ)=0\widehat{\mathbf{1}_S}(\xi)=0 whenever ξ≠0\xi\ne0 is orthogonal to some element of Vd\mathcal{V}_d, while Lemma 3.3 implies that g^(ξ)=0\widehat{g}(\xi)=0 for any ξ≠0\xi\ne0 not orthogonal to any element of Vd\mathcal{V}_d. We conclude that 1S∗g^(ξ)=1S^(ξ)g^(ξ)=0\widehat{\mathbf{1}_S*g}(\xi)=\widehat{\mathbf{1}_S}(\xi)\widehat{g}(\xi)=0 for every ξ∈Γ^∖{0}\xi\in\widehat{\Gamma}\setminus\{0\}. So, 1S∗g\mathbf{1}_S*g is constant. Since 1S\mathbf{1}_S and gg take only integer values, 1S∗g\mathbf{1}_S*g takes only integer values. We conclude that nd∣1S∗g^(0)n^d\mid\widehat{\mathbf{1}_S*g}(0).

On the other hand,

1S∗g^(0)=1S^(0)g^(0)=nd−1⋅(∑α∈Z≥0r+1wt⁡α=n−p1)=(np)nd−1=1pnd(n−1p−1).\widehat{\mathbf{1}_S*g}(0)=\widehat{\mathbf{1}_S}(0)\widehat{g}(0)=n^{d-1}\cdot\left(\sum_{\substack{\alpha\in\mathbb{Z}_{\geq0}^{r+1}\\ \operatorname{wt}\alpha=n-p}}1\right)=\binom{n}{p}n^{d-1}=\frac{1}{p}n^d\binom{n-1}{p-1}.

Hence, 1p(n−1p−1)\frac{1}{p}\binom{n-1}{p-1} is an integer, which implies p∤np\nmid n, as desired. □

Extensions and variants

There remain many open problems about configurations of non-attacking queens in (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d. Moreover, there are many other variants of the nn-queens problem in higher dimensions. We discuss some of those extensions and variants here.

If nn has a prime factor less than 2d2^d, then Theorem 1.1 implies that at most nd−1−1n^{d-1}-1 non-attacking queens can be placed in (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d. It is natural to ask precisely how many can be placed. In two dimensions, this question is answered by a classical result of Monsky [7]. Williams has made some partial progress towards this question for d>2d>2; see [Wil26, Theorem 3] and also [Wil26, Conjecture 2]. On the other hand, if nn has no prime factor less than 2d2^d, then there is another natural question: in how many ways can nd−1n^{d-1} non-attacking queens can be placed on (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d? The 2-dimensional version of case has recently been resolved up to a (1+o(1))n(1+o(1))^n factor by Bowtell and Keevash [2]. Neither of these questions seem particularly amenable to the methods we have introduced here.

Probably the most standard variant of the nn-queens problem (and certainly the most standard in d=2d=2) is the “non-toroidal” version of the problem we have considered. Let nn and dd be positive integers. Two queens in positions x,y∈{1,2,…,n}dx,y\in\{1,2,\ldots,n\}^d are said to attack each other if their difference is a scalar multiple of some {−1,0,1}d∖{0}\{-1,0,1\}^d\setminus\{0\}. (For example, the positions (n−1,0,0)(n-1,0,0) and (0,1,1)(0,1,1) are non-attacking for n>2n>2, while they are attacking in the toroidal problem on (Z/nZ)3(\mathbb{Z}/n\mathbb{Z})^3.) Here it remains clear that no more than nd−1n^{d-1} non-attacking queens can be placed. For d=3d=3, there is a conjecture of van Rees [vR81, Conjecture 3.3] that the existence problem is equivalent to the corresponding existence problem for a toroidal board.

Conjecture 4.1. If gcd⁡(n,210)>1\gcd(n,210)>1, one cannot place n2n^2 non-attacking queens in {1,2,…,n}3\{1,2,\ldots,n\}^3.

We believe that Conjecture 4.1 is false, and that in fact, for fixed d≥2d \ge2, one can place nd−1n^{d-1} non-attacking queens in {1,2,…,n}d\{1,2,\ldots,n\}^{d} for all sufficiently large nn. Like the two-dimensional nn-queens problem, higher-dimensional analogues can be phrased as an rr-partite rr-uniform hypergraph matching problem. Set r=(3d−1)/2r=(3^{d}-1)/2. Construct a hypergraph H\mathcal{H} as follows: create one vertex of H\mathcal{H} for each line in one of the directions v∈{−1,0,1}d∖{0}v \in\{-1,0,1\}^{d} \setminus\{0\}, and create, for each element x∈{1,2,…,n}dx \in\{1,2,\ldots,n\}^{d}, an edge of H\mathcal{H} containing the rr lines passing through xx. A set of non-attacking queen placements corresponds to a matching in H\mathcal{H}, and a set of nd−1n^{d-1} queens is a maximum-size matching, which must necessarily cover all vertices corresponding to lines in the dd coordinate directions. Following the significant applications of the technique of absorption to the standard and toroidal nn-queens problem in two dimensions (see [SL22, BK21, Sim23]), it seems plausible that, at least for d=3d=3, where there are only three classes of vertices (corresponding to the three coordinate directions) which require such a matching to be perfect, that such a statement could be proven using absorption. (Alternatively, such a statement could be proven for some particular nn not relatively prime to 210 by an explicit example. We have attempted, without any luck, to find such an example using computational tools.)

Other attacking rules also exist for toroidal nn-queens problems. Nudelman [8] introduced a different variant, wherein queens in cells xx and yy attack each other if xx and yy lie in the same hyperplane orthogonal to some v∈{−1,0,1}d∖{0}v \in\{-1,0,1\}^{d} \setminus\{0\}, rather than the same line parallel to such a vv. (In d=2d=2, these both collapse to the standard definition.) Nudelman proved that, if nn is divisible by no prime less than 2d2^{d}, then nn “hyperplane queens” can be placed in (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^{d} [8 Theorem 4], but that no more than n−1n-1 can be placed if nn has a prime factor less than 2d2d [8 Theorem 11]. It remains an intriguing open question (and one which may be amenable to our techniques) to determine for which nn one can place nn non-attacking hyperplane queens in (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^{d}.

Acknowledgements

We thank Brett Stevens for answering questions about the literature surrounding nn-queens problems. We thank Jacob Fox and Anubhab Ghosal for helpful advice.

References

AI Disclosure, project history, and methodology

As mentioned in § 1, the main result of this paper was produced in collaboration with AI tools. Here we give a history of the project and describe our AI use as well as our process. We include this information in accordance with a belief that, as AI becomes a larger part of doing mathematics and as process and result are becoming disentangled, it may be useful to report more about the process that led to a result.

ZH and CS first encountered [3] and the conjecture [vR81, Conjecture-3.2] of van Rees (which the d=3d=3 case of Theorem 1.1 verifies) in the process of working on [4] in the summer of 2023, which led to engagement with the modular nn-queens problem in dd dimensions. Initially we believed this conjecture to be false: the sort of argument used by Pólya [10] to resolve the d=2d=2 case seemed not to extend to d>3d>3, and we saw no reason that the classical sufficiency condition (arising from the construction we presented in § 2) should also turn out to be necessary.

All three authors worked intermittently on the problem in the following years. In particular, we (without the use of AI) pushed the polynomial-type methods used in [10] and [Wil26], and were unable to obtain any result stronger than [Wil26, Theorem 4]. Also without AI, and building on our earlier work in [4], we obtained a partial result towards Theorem 1.1 via Fourier analysis. Namely, we proved the following result.

Theorem 1.1’. Suppose that the prime factorization of nn contains a prime power qq which is less than 2d2^d. Then one cannot place nd−1n^{d-1} non-attacking queens on (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d.

Theorem 1.1’ follows from applying Lemma 3.1 to the function f~ ⁣:(Z/qZ)d→Z\tilde{f}\colon(\mathbb{Z}/q\mathbb{Z})^d\to\mathbb{Z} whose values f~(x)\tilde{f}(x) count the number of queens in (Z/nZ)d(\mathbb{Z}/n\mathbb{Z})^d at positions equivalent to xx modulo qq, and noting that f~\tilde{f} cannot be constant if qd∤nd−1q^d\nmid n^{d-1}.

At this point, we continued to believe a counterexample to the van Rees conjecture was possible and considered the computational search problem of finding a counterexample. We believed if there were to be a counterexample, there would likely be one at n=25n=25, which is the smallest modulus not covered by Theorem 1.1’. We ran these searches starting in 2025, but increased our efforts in May 2026. CS ran searches using AlphaEvolve [9], which produced configurations of 25225^2 queens in (Z/25Z)3(\mathbb{Z}/25\mathbb{Z})^3 with few, but not zero, attacking pairs. We tried a mix of strategies, over roughly 40 runs of 12 hours or more (on individual laptops), but none of our configurations came particularly close to working.

This was powerful evidence for the conjecture, so we tried to prove it. First, we attempted to extend our Fourier-analytic proof of Theorem 1.1’ to the full Theorem 1.1, but were unsuccessful. We then began to use AI tools for this purpose. First, we queried Codex, which quickly rederived Theorem 1.1’. Then, Codex derived impossibility proofs for the specific cases of (n,d)=(25,3)(n,d)=(25,3) and (n,d)=(49,3)(n,d)=(49,3). The strategy presented by Codex was as follows. A configuration of n2n^2 queens in (Z/nZ)3(\mathbb{Z}/n\mathbb{Z})^3 gives a solution to Bx=1(modn)Bx=1\pmod n for a “point-line incidence” matrix B∈Z13n2×n3B\in\mathbb{Z}^{13n^2\times n^3}. Codex then found a vector c∈Z13n2c\in\mathbb{Z}^{13n^2} such that cTB=0(modm)c^{\mathsf{T}}B=0\pmod{m} but cT1≠0(modm)c^{\mathsf{T}}1\ne0\pmod{m} for some power mm of nn. (Call such a cc a certificate.) We observed that this computation for (n,d)=(25,3)(n,d)=(25,3) (resp. (n,d)=(49,3)(n,d)=(49,3)) is enough to show Theorem 1.1 in the case of d=3d=3 and ν5(n)=2\nu_5(n)=2 (resp. ν7(n)=2\nu_7(n)=2). Next, Codex obtained a certificate for (n,d)=(125,3)(n,d)=(125,3), which bore some similarity to the certificate for (25,3)(25,3). Codex pointed out a connection of the certificates to Bockstein homomorphisms in homological algebra, which gave us some confidence that this strategy could be extended to all powers of 5. We asked Codex to probe the relationships between the certificates for powers of 55; eventually, it obtained two distinct proofs of Theorem 1.1 in the case of (n,d)=(5k,3)(n,d)=(5^k,3). Finally, Codex produced a proof of the main result.

We reinterpreted this proof, explicated which ingredients had appeared in our non-AI-assisted work and which ingredients were new, and wrote up the exposition which appears in this article. The exposition is entirely ours and we take full responsibility for all the content.

Email address: [email protected]

Department of Economics, Harvard University, Cambridge, MA 02138, USA

Email address: [email protected]

Department of Mathematics, Stanford University, Stanford, CA 94305, USA

References

  1. [1][AYM88] L. Allison, C. N. Yee, and M. McGaughey. Three dimensional queens problems. Technical Report 89/130, Department of Computer Science, Monash University, November 1988. Created 15 November 1988; accessed 27 September 2026.
  2. [2][BK21] Candida Bowtell and Peter Keevash. The n-queens problem, 2021. arXiv:2109.08083.arxiv.org/abs/2109.08083
  3. [3][BS09] Jordan Bell and Brett Stevens. A survey of known results and research areas for n-queens. Discrete Math., 309(1):1–31, 2009.DOI
  4. [4][HS25] Zachary Halberstam and Carl Schildkraut. Words with repeated letters in a grid, 2025. arXiv:2511.19678.arxiv.org/abs/2511.19678
  5. [5][Kla80] David A. Klarner. Queen squares. J. Recreational Math., 12(3):177–178, 1979/80.
  6. [6][Kun23] Tim Kunt. The n-queens problem in higher dimensions. Master’s thesis, Technische Universität Berlin, Berlin, December 2023. Available at arXiv:2406.06260.arxiv.org/abs/2406.06260
  7. [7][Mon89] Paul Monsky. Problems and Solutions: Solutions of Elementary Problems: E3162. Amer. Math. Monthly, 96(3):258–259, 1989.
  8. [8][Nud95] Scott P. Nudelman. The modular n-queens problem in higher dimensions. Discrete Math., 146(1-3):159–167, 1995.DOI
  9. [9][NVE+25] Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borisav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery, 2025. arXiv:2506.13131.arxiv.org/abs/2506.13131
  10. [10][Pól18] George Pólya. Über die “doppelt-periodischen” lösungen des n-Damen-Problems. In Wilhelm Ahrens, editor, Mathematische Unterhaltungen und Spiele, volume 2, pages 364–374. B. G. Teubner, 2 edition, 1918.

Paper details

vlnc:W_x9bz4p9h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex

View statement
Looking for related papers…
Contents