Counting the solutions of the 28-queens problem

Compute exactly how many ways 28 non-attacking queens fit on a 28×28 board; the counts are known only up to n = 27.

shoal State the problem, from CSPLib 36d29e0 · 2周前历史

34 行 · 3.3 KB 原始文件永久链接历史

1	# Counting the solutions of the 28-queens problem
2
3	In how many ways can $n$ queens be placed on an $n \times n$ board so that no two attack each other? Finding one placement is easy for every $n \ge 4$, but counting them all is not: the count is known up to $n = 27$, and $n = 28$ is the next open case.
4
5	## Problem
6
7	Let $Q(n)$ be the number of ways to place $n$ queens on an $n \times n$ chessboard with no two in the same row, column or diagonal; placements that differ by a rotation or reflection are counted separately (OEIS A000170). Equivalently, $Q(n)$ counts the permutations $p$ of $\{1, \dots, n\}$ with $\|p(j) - p(i)\| \ne j - i$ for all $i < j$. Compute $Q(28)$ exactly.
8
9	## Background
10
11	The $n$-queens problem generalises the classical eight-queens puzzle and is problem 54 of CSPLib, proposed by Bilal Syed Hussain. CSPLib stresses that deciding whether a placement exists is trivial, since explicit constructions exist for every $n \ge 4$, while counting all placements is a genuinely hard benchmark (Bell and Stevens, 2009). Asymptotically, Simkin (2023) proved that $Q(n) = ((1 \pm o(1))\, n e^{-c})^n$ with $c = 1.942 \pm 0.003$, but this says nothing exact about a given $n$.
12
13	## What is known
14
15	- The values up to $n = 27$ are known; for example $Q(26) = 22{,}317{,}699{,}616{,}364{,}044$ and $Q(27) = 234{,}907{,}967{,}154{,}122{,}528$.
16	- $Q(26)$ was computed by the Queens@TUD project in 2009, and $Q(27)$ by the Q27 project of Preußer and Engelhardt, which used FPGA hardware for about a year and reported in 2016.
17	- In 2025 Yao and Li independently confirmed $Q(27)$ in 28.4 days on eight RTX 5090 GPUs, with a GPU depth-first search that avoids shared-memory bank conflicts. They estimate that the same method would need about 11 months on eight such GPUs for $Q(28)$.
18
19	## What would count as progress
20
21	- The exact value of $Q(28)$, with code and a description of the method. A count cannot be checked by inspection, so the claim should come with independent confirmation: two different programs or hardware platforms agreeing, a reproducible run, and consistency checks such as reproducing $Q(n)$ for all $n \le 27$ and the count of symmetry classes (OEIS A002562).
22	- A substantially faster exact counting method, demonstrated on $n \le 27$, that brings $n = 28$ and beyond within reach.
23
24	## References
25
26	1. T. B. Preußer and M. R. Engelhardt (2017). Putting queens in carry chains, No. 27. Journal of Signal Processing Systems 88, 185–201. https://doi.org/10.1007/s11265-016-1176-8
27	2. G. Yao and Y. Li (2025). High-performance N-queens solver on GPU: iterative DFS with zero bank conflicts. arXiv:2511.12009. https://arxiv.org/abs/2511.12009
28	3. M. Simkin (2023). The number of n-queens configurations. Advances in Mathematics 427, 109127. https://doi.org/10.1016/j.aim.2023.109127
29	4. J. Bell and B. Stevens (2009). A survey of known results and research areas for n-queens. Discrete Mathematics 309, 1–31. https://doi.org/10.1016/j.disc.2007.12.043
30	5. OEIS A000170, Number of ways of placing n nonattacking queens on an n X n board. https://oeis.org/A000170
31
32	## Source
33
34	Imported from [CSPLib prob054](https://www.csplib.org/Problems/prob054/), curated by CSPLib editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.