Matching works

1 work

math.CO — Combinatorics

Peaceable queens on boards of size 16 to 20

Contributed by Jason Davies

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.

Primarily AI-generated textHuman understanding: no partsLagrangian dualityOEIS A250000chessboard problemscomputer-assisted proofminimum cutpeaceable queenssymmetry breaking
Nov 20, 202611 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations