Peaceable armies of queens on boards of size 16 and up

Place more than 37 white and 37 black mutually non-attacking queens on a 16×16 board, or prove 37 is the maximum.

shoal State the problem, from CSPLib 81a292c · 2周前历史

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

1	# Peaceable armies of queens on boards of size 16 and up
2
3	Place as many white queens and as many black queens as possible on an $n \times n$ chessboard, equal in number, so that no queen attacks a queen of the other colour. The answer is known only for boards up to $15 \times 15$. For larger boards no configuration is known that beats the count $\lfloor 7n^2/48 \rfloor$ from a construction published in 1977, and nobody knows whether that count is optimal.
4
5	## Problem
6
7	Let $a(n)$ be the largest $m$ such that $m$ white and $m$ black queens can stand on distinct squares of an $n \times n$ board with no white queen attacking a black one. Queens attack along rows, columns and both diagonals. Because the nearest pair of opposite colours on a shared line would attack each other, the condition is the same as asking that no row, column or diagonal contains queens of both colours. Determine $a(n)$ for $n \ge 16$, starting with $a(16)$.
8
9	## Background
10
11	The problem appears as problem C1 in Stephen Ainley's 1977 book Mathematical Puzzles, and is sequence A250000 of the OEIS, popularised by N. J. A. Sloane. It entered CSPLib as problem 110, proposed by Özgür Akgün, following constraint models by Smith, Petrie and Gent. It is a two-colour cousin of the classical $n$-queens problem and a clean test for symmetry breaking, integer programming and SAT.
12
13	## What is known
14
15	- Exact values $a(1), \dots, a(15)$ are $0, 0, 1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24, 28, 32$. The last two, $a(14) = 28$ and $a(15) = 32$, were settled by Paul Tabatabai with integer programming in 2018 (OEIS A250000).
16	- Ainley's construction gives $a(n) \ge \lfloor 7n^2/48 \rfloor$, which matches every known value except $n = 5$ and $n = 9$; for $n = 16$ it gives 37. Yao and Zeilberger (2022) conjectured that Ainley's construction is optimal.
17	- Upper bounds are far from the constructions. An integer-programming bound recorded in the OEIS gives $a(16) \le 64$ (Rob Pratt, 2014), and Clinch, Drescher, Huynh and Saffidine (2024) proved $a(n) \le 0.1716\, n^2$ for all large $n$, improving the bound $0.25\, n^2$ of van Bommel and MacEachern (2018). Their local search finds Ainley-type configurations quickly but nothing better.
18
19	## What would count as progress
20
21	- A placement of 38 white and 38 black queens on a $16 \times 16$ board (or, for larger $n$, more than $\lfloor 7n^2/48 \rfloor$ of each), which would refute the conjecture. A script checks the placement in milliseconds by testing every row, column and diagonal.
22	- A proof that $a(16) = 37$, for example an integer-programming or SAT run whose result can be certified and rerun independently. This is a separate and harder kind of progress than a construction.
23	- Better upper bounds for specific $n$, or an asymptotic upper bound below $0.1716\, n^2$.
24
25	## References
26
27	1. K. Clinch, M. Drescher, T. Huynh and A. Saffidine (2024). Constructions, bounds, and algorithms for peaceable queens. arXiv:2406.06974. https://arxiv.org/abs/2406.06974
28	2. Y. Yao and D. Zeilberger (2022). Numerical and symbolic studies of the peaceable queens problem. Experimental Mathematics 31, 269–279. https://doi.org/10.1080/10586458.2019.1616338
29	3. M. van Bommel and K. MacEachern (2018). Armies of chess queens. The Mathematical Intelligencer 40, 10–15. https://doi.org/10.1007/s00283-017-9771-5
30	4. OEIS A250000, Peaceable coexisting armies of queens. https://oeis.org/A250000
31
32	## Source
33
34	Imported from [CSPLib prob110](https://www.csplib.org/Problems/prob110/), 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.