Peaceable queens on boards of size 16 to 20
Version 1 / Nov 20, 2026 / CC BY 4.0
Abstract
Let be the largest such that white and black queens can be placed on an board with no queen attacking a queen of the other colour (OEIS A250000). The refereed literature and the OEIS gave for , and in 2026 Arevalo determined , and in an unrefereed, AI-assisted computational note. We prove and , which were open, and we confirm , and independently, with two separately written programs. In each case , so the constructions that Ainley gave in 1977 are optimal on these boards. The proof is computer-assisted. As in earlier work, we label each of the lines of the board white or black, which turns the problem into maximising the smaller of two cell counts. Our new ingredient is the bound: for fixed rows and columns we bound that quantity by Lagrangian duality, and each Lagrangian subproblem is a minimum cut on the diagonals. With symmetry breaking, the search for meets row/column labellings up to symmetry, and a single family of minimum cuts prunes every one of them. That search took 221.9 CPU hours, mostly on cloud machines. A second implementation repeats the whole search for every . Orbit counts by Burnside's lemma confirm that every search is complete, and exact LP certificates and SAT proofs checked by drat-trim give further checks. As side results we find 26 and 5 inequivalent optimal configurations for and (OEIS A260680), and we confirm by computation that the and tori admit 51 and 64 queens of each colour but not more (A279405), values that also follow from Harries's exact formula for even tori.
Provenance statement
Tools used
- Anthropic
- Claude CodeVersion Claude Opus 5.5
- OpenAI
- ChatGPTVersion Pro (6 Astra)
References
- S. Ainley, Mathematical Puzzles , G. Bell & Sons, London, 1977.
- F. Arevalo, The sixteenth, seventeenth and eighteenth peaceable queens numbers: 37, 42, 47 , computational research note (AI-assisted), August 17, 2026, updated September 3 and 7, 2026, https://fabianarevalo.com/peaceable-queens; code at https://github.com/farev/Matematica/tree/main/conjectures/peaceable-queens.link
- R. A. Bosch, Peaceably coexisting armies of queens , Optima (Mathematical Programming Society Newsletter) 62 (1999).
- R. A. Bosch, Armies of queens, revisited , Optima (Mathematical Programming Society Newsletter) 64 (2000), 15.
- K. Clinch, M. Drescher, T. Huynh, A. Saffidine, Constructions, bounds, and algorithms for peaceable queens , in: Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 2025), SIAM, 2025, 160--167. doi:10.1137/1.9781611978339.13 (https://doi.org/10.1137/1.9781611978339.13); arXiv:2406.06974, doi:10.48550/arXiv.2406.06974 (https://doi.org/10.48550/arXiv.2406.06974).arXivDOI
- A. V. Goldberg, R. E. Tarjan, A new approach to the maximum-flow problem , J.\ ACM 35 (1988), 921--940. doi:10.1145/48014.61051 (https://doi.org/10.1145/48014.61051).DOI
- J. P. Harries, Peaceable queens on even tori: an exact parity formula , preprint, September 6, 2026 (first version July 27, 2026), with a Lean proof of the main theorem, https://github.com/jphme/math-problems/tree/main/peaceable-queens-even-torus.link
- P. L. Ivănescu (Hammer), Some network flow problems solved with pseudo-Boolean programming , Oper.\ Res.\ 13 (1965), 388--399. doi:10.1287/opre.13.3.388 (https://doi.org/10.1287/opre.13.3.388).DOI
- Q. Huangfu, J. A. J. Hall, Parallelizing the dual revised simplex method , Math.\ Program.\ Comput.\ 10 (2018), 119--142. doi:10.1007/s12532-017-0130-5 (https://doi.org/10.1007/s12532-017-0130-5).DOI
- A. Ignatiev, A. Morgado, J. Marques-Silva, PySAT: a Python toolkit for prototyping with SAT oracles , in: SAT 2018, Lecture Notes in Comput.\ Sci.\ 10929 , Springer, 2018, 428--437. doi:10.1007/978-3-319-94144-8_26 (https://doi.org/10.1007/978-3-319-94144-8_26).DOI
Show all 23 referencesShow fewer references
- D. M. Kane, Asymptotic results for the queen packing problem , preprint (2017), arXiv:1703.04538. doi:10.48550/arXiv.1703.04538 (https://doi.org/10.48550/arXiv.1703.04538).arXivDOI
- D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 6: Satisfiability , Addison-Wesley, 2015, p. 180, exercise 488, and pp. 282--283.
- V. Kolmogorov, R. Zabih, What energy functions can be minimized via graph cuts? , IEEE Trans.\ Pattern Anal.\ Mach.\ Intell.\ 26 (2004), 147--159. doi:10.1109/TPAMI.2004.1262177 (https://doi.org/10.1109/TPAMI.2004.1262177).DOI
- OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences , sequences A250000 (revision 379, including the comments, the extensions, and D. Kamenetsky's file of best known solutions for ), A260680 and A279405, https://oeis.org.link
- L. Perron, F. Didier, CP-SAT , OR-Tools version 9.15, Google, https://developers.google.com/optimization.link
- K. E. Petrie, Symmetry breaking in peaceably coexisting armies of queens , in: CP 2002, Lecture Notes in Comput.\ Sci.\ 2470 , Springer, 2002, 763. doi:10.1007/3-540-46135-3_61 (https://doi.org/10.1007/3-540-46135-3_61).DOI
- J.-C. Picard, Maximal closure of a graph and applications to combinatorial problems , Management Sci.\ 22 (1976), 1268--1272. doi:10.1287/mnsc.22.11.1268 (https://doi.org/10.1287/mnsc.22.11.1268).DOI
- S. Prestwich, J. C. Beck, Exploiting dominance in three symmetric problems , in: Proceedings of the Fourth International Workshop on Symmetry and Constraint Satisfaction Problems (SymCon'04), 2004, 63--70.
- P. Virtanen et al., SciPy 1.0: fundamental algorithms for scientific computing in Python , Nature Methods 17 (2020), 261--272. doi:10.1038/s41592-019-0686-2 (https://doi.org/10.1038/s41592-019-0686-2).DOI
- B. M. Smith, K. E. Petrie, I. P. Gent, Models and symmetry breaking for `peaceable armies of queens' , in: CPAIOR 2004, Lecture Notes in Comput.\ Sci.\ 3011 , Springer, 2004, 271--286. doi:10.1007/978-3-540-24664-0_19 (https://doi.org/10.1007/978-3-540-24664-0_19).DOI
- M. F. van Bommel, K. T. MacEachern, Armies of chess queens , Math.\ Intelligencer 40 (2) (2018), 10--15. doi:10.1007/s00283-017-9771-5 (https://doi.org/10.1007/s00283-017-9771-5).DOI
- N. Wetzler, M. J. H. Heule, W. A. Hunt, DRAT-trim: efficient checking and trimming using expressive clausal proofs , in: SAT 2014, Lecture Notes in Comput.\ Sci.\ 8561 , Springer, 2014, 422--429. doi:10.1007/978-3-319-09284-3_31 (https://doi.org/10.1007/978-3-319-09284-3_31).DOI
- Y. Yao, D. Zeilberger, Numerical and symbolic studies of the peaceable queens problem , Exp.\ Math.\ 31 (2022), 269--279; arXiv:1902.05886. doi:10.1080/10586458.2019.1616338 (https://doi.org/10.1080/10586458.2019.1616338).arXivDOI
Version history
- v1 · 11 pagesSubmitted by Jason DaviesInitial depositCurrentNov 20, 2026