In this paper
AbstractIntroductionHistoryOrganizationSufficiencyNecessityExtensions and variantsAcknowledgementsReferencesAI Disclosure, project history, and methodologyWorksMathematics
Modular -queens in higher dimensions
Abstract
A chess queen in -dimensions can move any distance in the direction of any edge or diagonal of the -dimensional hypercube. (That is, a queen can move from a position to for any and any nonzero .) We prove that one can place non-attacking queens on the -dimensional modular board if and only if all prime factors of exceed . The case of this result is a conjecture of van Rees from 1981. Our proof involves both human ideas and substantial AI assistance.
Introduction
The -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 mutually non-attacking queens can be placed on a modular -by- chessboard if and only if 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 be integers. We will consider placing “queens” on elements of . Two queens in positions are said to attack each other if their difference is a scalar multiple of some nonzero element of . It is clear that one cannot place more than non-attacking queens in , since no two non-attacking queens may share their first coordinates. Our main result is to provide necessary and sufficient conditions under which this bound can be attained.
Theorem 1.1. Let . One can place non-attacking queens on if and only if all prime factors of exceed .
History
In 1980, Klarner proved the sufficiency direction of Theorem 1.1 in the case [5] with an explicit construction. Klarner’s construction naturally generalizes to prove the sufficiency direction of Theorem 1.1 for all (see, for example, [4 Corollary 8.2] and [Wil26, Theorem 1]). The new contribution here is the necessity direction.
The 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 (which Theorem 1.1 verifies) as [3 Conjecture 25].
Pólya’s result [10] for implies an analogous result for : if non-attacking queens can be placed in , then and . The only other progress in this direction (to our knowledge) is a 2026 result of Williams [Wil26, Theorem 4], who showed that, for , either or . Williams’ approach is similar to that of Pólya, in that it involves summing polynomials in over the queen positions . Our approach is different; we use multiplicative characters of (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 -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 -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 are greater than , then non-attacking queens can be placed on . This argument is a simple extension of the arguments used in the case and appears, for example, as [Wil26, Theorem 1] and [4 Corollary 8.2]. The argument in the case is due to Klarner [5]. We present the full argument here for completeness.
Proof of Theorem 1.1, sufficiency direction. Let . Place a queen in position if and only if . It is clear that queens are placed in this way. Assume for the sake of contradiction that two queens at positions and are attacking. Then, there exists some nonzero and for which . We conclude that
Let . Write for distinct . By the uniqueness of binary representation, we have . We conclude that, as an integer, is nonzero. Moreover, . Therefore, by our assumption on , we have . The property for nonzero provides a contradiction. □
Remark. The configuration of non-attacking queens presented in this proof is an affine configuration; that is, the cells at which we place queens form a hyperplane in . This proof can be easily extended to show that, in fact, such an affine configuration of non-attacking queens only exists if has no prime factors less than .
Indeed, let , and suppose that is a prime factor of . Since , there exist distinct such that
This implies that
So, the set contains the attacking positions and , and is thus not a set of non-attacking queens.
Given this, Theorem 1.1 can be rephrased in the following way: given and , there exists a configuration of non-attacking queens on 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 and let . Write . For , define the Fourier transform by
Define the convolution of two functions by
We have . For , write for the function which evaluates to 1 on and 0 everywhere else. Note that .
If is a set of non-attacking queens, then each line for and contains exactly one element of . 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 .
Lemma 3.1. Let . Let . Suppose that, for every and every , we have
Let . If for some , then .
Proof. For each , we have
Therefore
We now explain the strategy behind the proof of Theorem 1.1. Let be a set of non-attacking positions. Lemma 3.1 implies that, if is orthogonal to some element of , then . If , then this condition implies that for every nonzero . Thus is constant, which cannot be.
We will generalize this argument by constructing a function with the property that whenever is not orthogonal to any element of . For any such , by Lemma 3.1, the function will be constant and integer-valued, and so we will have
If , this provides the desired contradiction.
To construct such a , we first prove an auxiliary lemma. Given a vector for some , we write for the sum of coordinates of .
Lemma 3.2. For a positive integer , write
for the th complete homogeneous symmetric polynomial in the variables . If are distinct th roots of unity, then .
Proof. Let be indeterminates. We have
Now, define the determinants
We compute
Performing column operations and permuting the columns,
We conclude that
The term on the left is homogeneous of degree , while the term on the right is homogeneous of degree . We conclude that . (This is a special case of Jacobi’s bialternant formula for Schur polynomials.) Now, evaluate this identity at distinct th roots of unity . Since the first and last columns of the matrix defining are equal, we have . On the other hand, is the determinant of a Vandermonde matrix, so the distinctness of implies that . The result follows.
We now construct our auxiliary function .
Lemma 3.3. Let , and let be distinct elements of . Define a function by
Let . If for every , then .
Proof. For , let . If for some , then , which would contradict our assumption that is not orthogonal to any element of . Therefore, are
distinct th roots of unity. We now compute
The result thus follows from Lemma 3.2. □
Proof of Theorem 1.1, necessity direction. Let be a set of non-attacking queens and let be a prime. We will prove that .
Since has size , every line for has exactly one element of . In particular, the indicator function of satisfies the precondition of Lemma 3.1.
Now, let be distinct elements of (we can choose such elements since ). Let be as in Lemma 3.3. Lemma 3.1 implies that whenever is orthogonal to some element of , while Lemma 3.3 implies that for any not orthogonal to any element of . We conclude that for every . So, is constant. Since and take only integer values, takes only integer values. We conclude that .
On the other hand,
Hence, is an integer, which implies , as desired. □
Extensions and variants
There remain many open problems about configurations of non-attacking queens in . Moreover, there are many other variants of the -queens problem in higher dimensions. We discuss some of those extensions and variants here.
If has a prime factor less than , then Theorem 1.1 implies that at most non-attacking queens can be placed in . 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 ; see [Wil26, Theorem 3] and also [Wil26, Conjecture 2]. On the other hand, if has no prime factor less than , then there is another natural question: in how many ways can non-attacking queens can be placed on ? The 2-dimensional version of case has recently been resolved up to a 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 -queens problem (and certainly the most standard in ) is the “non-toroidal” version of the problem we have considered. Let and be positive integers. Two queens in positions are said to attack each other if their difference is a scalar multiple of some . (For example, the positions and are non-attacking for , while they are attacking in the toroidal problem on .) Here it remains clear that no more than non-attacking queens can be placed. For , 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 , one cannot place non-attacking queens in .
We believe that Conjecture 4.1 is false, and that in fact, for fixed , one can place non-attacking queens in for all sufficiently large . Like the two-dimensional -queens problem, higher-dimensional analogues can be phrased as an -partite -uniform hypergraph matching problem. Set . Construct a hypergraph as follows: create one vertex of for each line in one of the directions , and create, for each element , an edge of containing the lines passing through . A set of non-attacking queen placements corresponds to a matching in , and a set of queens is a maximum-size matching, which must necessarily cover all vertices corresponding to lines in the coordinate directions. Following the significant applications of the technique of absorption to the standard and toroidal -queens problem in two dimensions (see [SL22, BK21, Sim23]), it seems plausible that, at least for , 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 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 -queens problems. Nudelman [8] introduced a different variant, wherein queens in cells and attack each other if and lie in the same hyperplane orthogonal to some , rather than the same line parallel to such a . (In , these both collapse to the standard definition.) Nudelman proved that, if is divisible by no prime less than , then “hyperplane queens” can be placed in [8 Theorem 4], but that no more than can be placed if has a prime factor less than [8 Theorem 11]. It remains an intriguing open question (and one which may be amenable to our techniques) to determine for which one can place non-attacking hyperplane queens in .
Acknowledgements
We thank Brett Stevens for answering questions about the literature surrounding -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 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 -queens problem in dimensions. Initially we believed this conjecture to be false: the sort of argument used by Pólya [10] to resolve the case seemed not to extend to , 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 contains a prime power which is less than . Then one cannot place non-attacking queens on .
Theorem 1.1’ follows from applying Lemma 3.1 to the function whose values count the number of queens in at positions equivalent to modulo , and noting that cannot be constant if .
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 , 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 queens in 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 and . The strategy presented by Codex was as follows. A configuration of queens in gives a solution to for a “point-line incidence” matrix . Codex then found a vector such that but for some power of . (Call such a a certificate.) We observed that this computation for (resp. ) is enough to show Theorem 1.1 in the case of and (resp. ). Next, Codex obtained a certificate for , which bore some similarity to the certificate for . 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 ; eventually, it obtained two distinct proofs of Theorem 1.1 in the case of . 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][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][BK21] Candida Bowtell and Peter Keevash. The n-queens problem, 2021. arXiv:2109.08083.arxiv.org/abs/2109.08083
- [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][HS25] Zachary Halberstam and Carl Schildkraut. Words with repeated letters in a grid, 2025. arXiv:2511.19678.arxiv.org/abs/2511.19678
- [5][Kla80] David A. Klarner. Queen squares. J. Recreational Math., 12(3):177–178, 1979/80.
- [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][Mon89] Paul Monsky. Problems and Solutions: Solutions of Elementary Problems: E3162. Amer. Math. Monthly, 96(3):258–259, 1989.
- [8][Nud95] Scott P. Nudelman. The modular n-queens problem in higher dimensions. Discrete Math., 146(1-3):159–167, 1995.DOI
- [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][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.