Peaceable queens on boards of size 16 to 20

Contributed by Jason Davies ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

Let a(n)a(n) be the largest mm such that mm white and mm black queens can be placed on an n×nn\times n board with no queen attacking a queen of the other colour (OEIS A250000). The refereed literature and the OEIS gave a(n)a(n) for n≤15n\le15, and in 2026 Arevalo determined a(16)a(16), a(17)a(17) and a(18)a(18) in an unrefereed, AI-assisted computational note. We prove a(19)=52a(19)=52 and a(20)=58a(20)=58, which were open, and we confirm a(16)=37a(16)=37, a(17)=42a(17)=42 and a(18)=47a(18)=47 independently, with two separately written programs. In each case a(n)=⌊7n2/48⌋a(n)=\lfloor7n^2/48\rfloor, 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 6n−26n-2 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 4n−24n-2 diagonals. With symmetry breaking, the search for n=20n=20 meets 5.7×10105.7\times10^{10} 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 n≤18n\le18. 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 n=16n=16 and n=17n=17 (OEIS A260680), and we confirm by computation that the 20×2020\times20 and 22×2222\times22 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

This work came out of an AI-driven investigation of open problems in the OEIS that the human contributor started and directed. Claude Opus 5.5 (Anthropic), working through Claude Code, did all of the following: the method, the proofs, the code (C, Rust and Python), the computations and their checks, and the writing of the manuscript. The human contributor wrote no part of the text. They started some of the cloud runs on Modal, using commands the AI system prepared. An independent AI referee reviewed the proofs and both search programs adversarially and wrote the Burnside, exact-LP, brute-force and CP-SAT cross-checks. ChatGPT Pro (OpenAI) then reviewed the code externally in three rounds, and the defects it found have been fixed. No human expert has reviewed the work, and the human contributor has not read the manuscript or checked its arguments. The AI system's first literature search missed prior work by F. Arevalo (a(16)–a(18)) and J. P. Harries (even tori). This version credits both and withdraws an earlier claim that those values were new.

Tools used

Anthropic
Claude CodeVersion Claude Opus 5.5
OpenAI
ChatGPTVersion Pro (6 Astra)

References

  1. S. Ainley, Mathematical Puzzles , G. Bell & Sons, London, 1977.
  2. 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
  3. R. A. Bosch, Peaceably coexisting armies of queens , Optima (Mathematical Programming Society Newsletter) 62 (1999).
  4. R. A. Bosch, Armies of queens, revisited , Optima (Mathematical Programming Society Newsletter) 64 (2000), 15.
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  1. 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
  2. D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 6: Satisfiability , Addison-Wesley, 2015, p. 180, exercise 488, and pp. 282--283.
  3. 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
  4. 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 12≤n≤3012\le n\le30), A260680 and A279405, https://oeis.org.link
  5. L. Perron, F. Didier, CP-SAT , OR-Tools version 9.15, Google, https://developers.google.com/optimization.link
  6. 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
  7. 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
  8. 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.
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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

  1. v1 · 11 pagesSubmitted by Jason DaviesInitial depositCurrentNov 20, 2026