Computational research note · Peaceable queens (OEIS A250000)
Set up two chess armies on a square board: some number of white queens and the same number of black queens. The only rule is that no white queen may be able to capture a black one, and no black queen may be able to capture a white one. Queens attack in straight lines and diagonals, all the way across the board, with nothing allowed to block the line of sight. How large can the two armies be, if they have to be the same size?
On an ordinary 8×8 board the answer has been known for years: nine queens a side, eighteen pieces on the board, and no bigger split works. Mathematicians have pushed the same question up to bigger and bigger boards (it is catalogued as sequence A250000 in the Online Encyclopedia of Integer Sequences), and by 2014 the exact answer was known all the way up to a 15×15 board. For the next two sizes up only ranges were on record: somewhere between 37 and 64 queens per side on a 16×16 board, and between 42 and 72 on a 17×17 one. Both stayed that way for over a decade.
Three sessions pin each range down to a single number: 37 on the 16×16 board, 42 on the 17×17, and 47 on the 18×18. Placements that achieve those counts are drawn below (click any queen to see for yourself why one works), and one queen more per side is proved impossible in each case: not by guessing arrangements and failing to find one, but by a reformulation of the problem that makes checking every last possibility actually finish, and then running that check to exhaustion. At 16×16 the check was run twice, with two independently written programs. At 17×17 and 18×18 it was run once each, which is a real difference and is flagged as one throughout.
Rob Pratt worked out the exact answer for every board up to 15×15 back in 2014, using a standard optimization technique, and for the next boards he narrowed the answer to a range without pinning it down: 37 to 64 at 16×16, 42 to 72 at 17×17, and 47 to 81 at 18×18. That is where the trail went cold.
This note does six things.
Everything below is the technical version: the exact reformulation, the two search engines, the ladder of smaller boards, and the several independent, failure-disjoint ways this was checked before calling any of it certified. The figure in section 5 is the one to look at if you only look at one: it shows what each rung of the ladder actually costs, and why the next one is the expensive one.
The peaceable queens number a(n) (OEIS A250000) is the largest m such that m white and m black queens can be placed on an n × n board with no queen attacking a queen of the opposite color. We give an exact branch-and-bound in a line-labeling reformulation (Lemma 1), with all pruning rules proved here (Lemmas 3–5) and two canonical forms: a color-swap reduction (Lemma 6) and a full order-16 orbit reduction (Lemma 6′, the “SYM16” engine). Two independent implementations agree node-for-node; the method is cross-validated against a SAT pipeline (40/40 verdict agreements on all army sizes for n ≤ 8) whose boundary instances carry DRUP proofs checked by an independent reverse-unit-propagation checker; every witness is re-verified by a from-the-definition checker sharing no code with the search or the encoders. With this machinery we re-derive the complete known ladder a(1..15) from scratch, including a(14) = 28 and a(15) = 32, for which we could locate no published proof artifact, and then decide the two smallest open cases. a(16) = 37, by an exhaustive 5.03-billion-node refutation of army size 38 (SYM16 engine, 16 independently-completed chunks, every chunk UNSAT), paired with a checker-verified 37 + 37 witness; a second, fully independent exhaustion of the same army size by a differently-canonicalized engine (color swap only, Lemma 6) agrees at 45.0 billion nodes, 16/16 chunks UNSAT, a node ratio of 8.95 against the group-order ratio of 8 the two canonical forms predict. Then a(17) = 42, by an exhaustive 21.45-billion-node refutation of army size 43 (SYM16 engine, 16 chunks, every chunk UNSAT, 1,712 s wall on 4 workers), paired with two checker-verified 42 + 42 witnesses, one found by the engine itself and one from the OEIS link file. A third session takes the next rung: a(18) = 47, by an exhaustive 119.11-billion-node refutation of army size 48 (SYM16 engine, 16 chunks, every chunk UNSAT, 32,544 s of engine CPU time), paired with Ainley’s 1977 placement from the OEIS link file, which the from-definition checker accepts with 47 white and 48 black queens. The n = 17 and n = 18 refutations are single-engine: the plain-engine replications are roughly nine times the work and have not been run, so those verdicts rest on the engines’ 16/16 agreement record lower down the ladder rather than on second exhaustions of their own (section 9). Two independent sessions did run the n = 18 refutation on different hardware and reported identical node counts in all sixteen chunks, which replicates the run but not the engine. The OEIS-recorded finite brackets had stood at [37, 64], [42, 72] and [47, 81] since 2014 (Pratt, secondary); A250000 itself still tabulates only a(1..15). Each of the three decided values equals ⌊7n²⁄48⌋, the count of Ainley’s construction.
Queens attack along rows, columns and the two diagonal directions. In this problem (Bosch 1999, secondary; OEIS A250000) attacks are not blocked by intervening pieces, so the only constraint is that no white queen and black queen may share a row, column, or diagonal: adjacency and occlusion never enter. a(n) is the largest m such that m white and m black queens can coexist under that rule on an n × n board.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a(n) | 0 | 0 | 1 | 2 | 4 | 5 | 7 | 9 | 12 | 14 | 17 | 21 | 24 | 28 | 32 | 37 | 42 |
All of these values, and everything said about them below, is secondary-sourced: the session that produced this note ran in a sandbox whose egress was blocked, so nothing from oeis.org, arxiv.org, or any primary host could be fetched, and every citation in this note rests on search snippets retrieved on 2026-08-17. a(1)–a(13) are attributed to Rob Pratt, by integer programming, entered in the OEIS on 2014-12-01. Pratt is recorded as having also logged finite bounds for n = 14..17 without deciding them: 28 ≤ a(14) ≤ 43, 32 ≤ a(15) ≤ 53, 37 ≤ a(16) ≤ 64, 42 ≤ a(17) ≤ 72. The third of these, the n = 16 bracket, is the one this note closes. The values a(14) = 28 and a(15) = 32 are reported as known by a 2024 survey (arXiv:2406.06974, Clinch–Drescher–Huynh–Saffidine, secondary), which also states that only 15 terms of the sequence were known before this session; from this sandbox we could not determine who first established a(14) and a(15) or locate a proof artifact for either (see caveats). Lower bounds for n ≤ 30 come from Ainley’s 1977 constructions, apparently never surpassed except at n = 27 (secondary). The best published upper bound of the right asymptotic order is a(n) ≤ (2 − √2)/2 · n² ≈ 0.1716 n² for all sufficiently large n (arXiv:2406.06974, secondary); it is asymptotic, and, as far as we can tell from the abstract and search snippets, not claimed as a specific finite bound at n = 16.
Everything from here on is self-contained: no external value is assumed anywhere in the search or the proofs. The published ladder above is used only as a cross-check after each value is independently re-derived (see section 5).
Index the board’s lines: rows r ∈ [0,n), columns c ∈ [0,n), sum-diagonals s = r + c ∈ [0,2n−1), difference-diagonals d = r − c + n − 1 ∈ [0,2n−1). Every cell lies on exactly one line of each of these four families, for 4n + 2(2n−1) = 6n − 2 lines in total. Call a placement peaceable if no line carries both colors.
For m ≥ 1, the following are equivalent: (1) there is a peaceable placement with ≥ m white and ≥ m black queens; (2) there is a labeling ℓ of all 6n − 2 lines by {W, B} such that at least m cells have all four of their lines labeled W, and at least m cells have all four labeled B.
Proof. (1 ⇒ 2) Fix a peaceable placement. No line contains both colors, so “label a line by the color it contains” is well defined on non-empty lines; label queen-free lines arbitrarily, say W. Every white queen’s four lines contain a white queen, hence are labeled W, so every white queen sits on an all-W cell, giving ≥ m all-W cells, and likewise for black.
(2 ⇒ 1) Given ℓ, place a white queen on every all-W cell and a black queen on every all-B cell. No cell is both (its row cannot be labeled both ways). If a white and a black queen shared a line, that line would be labeled both W and B, which is impossible. So the placement is peaceable, with ≥ m queens of each color; discard extras to make the armies equal. ∎
Consequently a(n) = max over labelings of min(#all-W cells, #all-B cells), and deciding “a(n) ≥ m” is a finite search over 26n−2 labelings. The engine organizes this search as: choose the row labels (a set S of W-rows), then the column labels T, then the two diagonal families by depth-first search. Given (S, T), call WG = S × T the white grid (cells whose row and column are both W) and BG = S̄ × T̄ the black grid. During the diagonal DFS, a WG cell is live if neither of its diagonals is labeled B; a BG cell is live if neither is labeled W. Write w, b for the counts of live WG, BG cells at the current search node.
If at some node every unlabeled diagonal has live cells of at most one color, the labeling can be completed so that exactly the live cells are the all-W (resp. all-B) cells. In particular, if also w ≥ m and b ≥ m, condition (2) of Lemma 1 holds.
Proof. Label each unlabeled diagonal by the color of its live cells (arbitrarily if none). This kills no live cell: a live white cell dies only when one of its diagonals is labeled B, but any unlabeled diagonal through a live white cell has a live white cell on it, hence gets labeled W (symmetrically for black). Dead cells stay dead, since labels are never retracted. A live white cell now has row and column in S, T and both diagonals labeled W, so it is all-W. ∎
All four bounds below are exact integer statements about any completion of the current partial labeling, checked at every search node: none of them is a heuristic.
Any labeling with ≥ m all-W and ≥ m all-B cells has m ≤ |S|·|T| and m ≤ (n−|S|)(n−|T|).
Proof. All-W cells lie in S × T, of size |S|·|T|; all-B cells lie in S̄ × T̄. ∎
In any completion of the current node, the all-W cells form a subset of the currently live WG cells; hence if w < m or b < m the node is dead.
Proof. Labeling more diagonals can only kill cells, never revive them: a cell with a B-labeled diagonal carries that label forever. ∎
Fix one diagonal family, say the sum-diagonals. Writing aw(s), ab(s) for the currently-live WG/BG cell counts on diagonal s, every completion has (#all-W) + (#all-B) ≤ Σs cap(s), where cap(s) is aw(s) if s is labeled W, ab(s) if labeled B, and max(aw(s), ab(s)) if s is still unlabeled. If Σs cap(s) < 2m the node is dead. The same bound holds for the difference-diagonal family.
Proof. A W-labeled diagonal carries only all-W cells, all currently live, so ≤ aw(s) of them; a B-labeled diagonal carries ≤ ab(s); an unlabeled one ends up one or the other, carrying ≤ max(aw(s), ab(s)). Summing over the family counts every all-W and all-B cell exactly once. ∎
If some labeling achieves ≥ m all-W and ≥ m all-B cells, then some labeling with row 0 labeled W does.
Proof. If not already so, swap the two labels everywhere; the all-W and all-B counts exchange, both still ≥ m. ∎
Let G be the order-16 group generated by row reversal, column reversal, transposition, and the color swap. Each of the three board maps is a bijection of the board sending lines to lines (row reversal fixes rows and columns setwise and exchanges the two diagonal families up to index reversal; similarly for the others), and the color swap exchanges the all-W/all-B counts, so every g ∈ G maps a labeling to one with the same pair {#all-W, #all-B}. The induced action on (S,T) = (W-rows, W-columns) sends it to one of 16 keys, namely (A,B), (B,A), (Ā,B̄), (B̄,Ā) for A ∈ {S, rev S}, B ∈ {T, rev T}: exactly the 16 keys the engine tests. Hence if any labeling achieves both counts ≥ m, so does one whose (S,T) is key-minimal in its G-orbit, and the diagonal DFS need only run at key-minimal pairs. ∎
The plain engine uses Lemma 6 only (“row 0 is white”); the SYM16 engine uses Lemma 6′ and does roughly 16⁄2 = 8× less work per instance in exchange for the extra bookkeeping. Both were checked to give identical verdicts on every boundary instance of the ladder (16/16 instances, n = 3..13, SAT and UNSAT sides both) before the SYM16 engine was trusted on anything new; node counts from the two engines are otherwise not comparable: a smaller count under SYM16 reflects the coarser canonical form, not an easier instance. Search proceeds by branching only on diagonals with live cells of both colors (Lemma 2: none remaining means SAT), checking Lemmas 3–5 at every node. This makes the search exact in both directions: an UNSAT verdict at m proves a(n) ≤ m−1, and a SAT verdict comes with an explicit witness.
A hand-written exact search is exactly the kind of program that is easy to get subtly wrong, so nothing here rests on a single implementation. Five independent checks, each catching a different class of mistake:
The certification basis is not the same at every n, and it matters which one applies where. DRUP proof files, checkable by a program that does not trust the search at all, exist only for the n ≤ 7 boundaries, where the cell-level CNF is still small enough for cadical --plain to finish. Beyond that, and in particular at n = 16, no DRUP proof exists; the certificate is the conjunction of items 1–5 above (two node-identical implementations, cross-validation against SAT, and committed, independently-checkable chunk records for every claimed exhaustion), not a proof-checker-verified refutation. This note says so plainly rather than letting “certified” blur across that boundary.
For 1 ≤ n ≤ 15, a(1..15) = 0, 0, 1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24, 28, 32, each value backed by an explicit witness (checker-verified) and an exhaustive branch-and-bound refutation at m = a(n)+1.
Every value agrees with the literature where the literature could be checked (a(1)–a(13): Pratt, via ILP, secondary), and a(14) = 28, a(15) = 32 come with what appears, from what the first session’s sandbox could see, to be the first independently reproducible derivation with a committed proof artifact; see the provenance caveat in section 9. The table below is the full boundary data behind Theorem A together with the two decided cases, read from results/ladder_bnb.csv and the per-run logs in results/.
| n | a(n) | boundary m | UNSAT nodes | wall time | workers | engine |
|---|---|---|---|---|---|---|
| 3 | 1 | 2 | 18 | <0.01 s | 1 | plain |
| 4 | 2 | 3 | 78 | <0.01 s | 1 | plain |
| 5 | 4 | 5 | 200 | <0.01 s | 1 | plain |
| 6 | 5 | 6 | 4,178 | <0.01 s | 1 | plain |
| 7 | 7 | 8 | 16,796 | <0.01 s | 1 | plain |
| 8 | 9 | 10 | 107,042 | 0.02 s | 1 | plain |
| 9 | 12 | 13 | 257,574 | 0.05 s | 1 | plain |
| 10 | 14 | 15 | 3,767,922 | 0.72 s | 1 | plain |
| 11 | 17 | 18 | 20,324,326 | 3.82 s | 1 | plain |
| 12 | 21 | 22 | 52,285,114 | 11.10 s | 1 | plain |
| 13 | 24 | 25 | 477,786,646 | 99.35 s | 1 | plain |
| 14 | 28 | 29 | 2,264,952,960 | 231 s | 4 | plain |
| 15 | 32 | 33 | 1,476,498,420 | 156 s | 4 | SYM16 |
| 16 | 37 | 38 | 5,032,610,558 | 462 s | 4 | SYM16 |
| 17 | 42 | 43 | 21,454,699,264 | 1,712 s | 4 | SYM16 |
The plain engine found a 37 + 37 peaceable placement on the 16 × 16 board in 177,220,136 nodes (28.98 s), independently of Ainley’s construction. The witness (witnesses/witness_n16_m37.txt) passes the from-definition checker; it is rendered and re-checked live in the figure at the top of this page.
Exhaustive refutation of army size 42 by the SYM16 engine: 607,406,702 nodes, 174 s wall on 4 workers, split into 8 resumable chunks, every chunk UNSAT (results/n16_m42_bnb_sym_chunk*.txt). The best previously recorded finite upper bound at n = 16 was a(16) ≤ 64 (Pratt 2014, secondary; the asymptotic 0.1716 n² bound of arXiv:2406.06974 makes no claim at this n). This alone tightened the recorded bracket from [37, 64] to [37, 41], before the exact value was known.
The upper half is the exhaustive refutation of army size 38: SYM16 engine, 16 resumable chunks, every chunk UNSAT, 5,032,610,558 nodes in 462 s wall on 4 workers (results/n16_m38_bnb_sym_chunk*.txt). The lower half is Theorem B’s witness. A full second exhaustion of army size 38, run as a belt-and-braces check by the plain engine (a different canonical form, Lemma 6 only, and a different outer-loop code path), completed independently and agrees: 45,021,245,984 nodes, 3,691 s wall on 4 workers, all 16 chunks UNSAT (results/n16_m38_bnb_chunk*.txt). The node ratio between the two exhaustions, 45,021,245,984 / 5,032,610,558 ≈ 8.95, sits close to the symmetry-group order ratio 16⁄2 = 8. Not exactly, since orbit-boundary effects mean the reduction is not a uniform 8-to-1 everywhere, but close enough to serve as an internal consistency check on the whole canonicalization argument.
To our knowledge, with the sourcing caveats of section 8, and the OEIS entry and the 2024 survey as the ledger against which we checked, this is the first determination of a(16), the smallest open case of A250000. It confirms the value conjectured from Ainley’s construction and extends the exact-value table reported by Clinch–Drescher–Huynh–Saffidine (secondary).
One number in the source note we could not re-confirm from a committed artifact: alongside Theorem B’s plain-engine witness run, the note additionally reports the SYM16 engine independently reproducing the same witness in 89,333,324 nodes and 17 s, at the same canonical row/column sets (S = 127, T = 3615). Rechecking the repository for this page, only the plain-engine run has a committed result file (results/n16_m37_sat.txt); no separate file for a SYM16 run at m = 37 could be found. The witness itself is independently re-verified above regardless of which engine first produced it, so a(16) ≥ 37 is unaffected. The specific “89,333,324 nodes, 17 s” figure, though, should be read as reported in the source note rather than independently reconfirmed here.
The second session ran the same machinery one rung further, on the same four cores. Nothing in the method changed: the same SYM16 engine rebuilt from source, the same chunked driver, the same from-definition checker.
Two independently obtained 42 + 42 peaceable placements on the 17 × 17 board pass the from-definition checker. The first was found by the SYM16 engine itself in 678,816,342 nodes (116 s), at canonical row/column sets S = 255, T = 7199 (witnesses/witness_n17_m42.txt); the plain engine independently reproduced the same placement, at the same canonical sets, in 1,357,765,356 nodes (212 s). The second is the placement in the A250000 link file (Kamenetsky 2019, attributing the value to Ainley 1977; secondary), which the checker also accepts (witnesses/witness_n17_m42_kamenetsky.txt). Because the engine found its own witness, the lower bound does not depend on the literature placement; the published one serves as a second, independent confirmation that 42 is attainable.
Exhaustive refutation of army size 43 by the SYM16 engine: 16 resumable chunks, every chunk UNSAT, 21,454,699,264 nodes in 1,712 s wall on 4 workers (6,086 s summed engine time; chunk sizes from 7.24 × 107 to 2.56 × 109 nodes), recorded chunk by chunk in results/n17_m43_bnb_sym_chunk*.txt with the driver log in results/n17_m43_run.log. With Theorem E this gives a(17) = 42, confirming Ainley’s 1977 value and matching ⌊7n²⁄48⌋ at n = 17. The recorded bracket had been [42, 72] since 2014 (Pratt, secondary).
This is the one place where the n = 17 result is weaker than the n = 16 one, and it is a defect rather than a caveat, so it is stated as one. At n = 16 the refutation was replicated end to end by the plain engine, which uses a different canonical form and a different outer-loop code path: two exhaustions, 8.95× apart in node count, close to what the group orders predict. At n = 17 that replication is about nine times the SYM16 work, on the order of 1.9 × 1011 nodes and four to five hours, and it was not run: a time-budget decision, not a result. What the verdict rests on instead is the engines’ agreement record, 16/16 identical verdicts on every boundary instance of the ladder plus a full second exhaustion at n = 16, together with the proved pruning lemmas of section 3 and the chunk records above. That is the repository’s stated basis for calling an exact, reproducible, chunk-recorded exhaustion by a validated engine CERTIFIED, but a reader who wants the same two-engine standard the n = 16 result meets should treat a(17) = 42 as one exhaustion short of it until the replication is run. The command is in section 10.
The growth from n = 16 to n = 17 is ×4.26 in nodes, inside the ×3–5 per-rung band the rest of the ladder sets and a little below the 5–8× the first session projected. That projection was written down before the run, in the previous version of this page’s open questions, so it is a forecast that held rather than a description after the fact.
The third session ran the same machinery one rung further again, on the same four cores and with no new code: the SYM16 engine rebuilt from source, the same chunked driver, the same from-definition checker. It ran as a background hedge underneath that day’s main search, at nice 19, which matters for how the timings should be read.
The 18 × 18 board in the A250000 link file (Kamenetsky 2019, attributing the value to Ainley 1977; provenance secondary) passes the from-definition checker, which finds no attacking pair of opposite colours (witnesses/witness_n18_m47_kamenetsky.txt). The placement carries 47 white and 48 black queens, so deleting any black queen leaves a 47 + 47 placement and a(18) ≥ 47. Because the checker re-derives this from the definition, the bound does not depend on trusting the source; but unlike n = 16 and n = 17, no engine search for a witness of its own was run, so the lower bound here is a verified literature placement rather than an independent discovery.
Exhaustive refutation of army size 48 by the SYM16 engine: 16 resumable chunks, every chunk UNSAT, 119,110,352,726 nodes and 32,544 s of summed engine CPU time, chunk sizes from 455,221,604 to 14,077,925,460 nodes, recorded chunk by chunk in results/n18_m48_bnb_sym_chunk*.txt with the driver log in results/n18_m48_run.log. Wall time was 13,470 s on four niced workers under contention, so it is not comparable with the 1,712 s at n = 17; on four dedicated cores the run is about two and a half hours. With Theorem G this gives a(18) = 47, confirming Ainley’s value and matching ⌊7n²⁄48⌋ = 47. The recorded bracket had been [47, 81] since 2014 (Pratt, secondary).
Two sessions, on 2026-09-04 and 2026-09-07, launched this refutation independently on different hardware, neither aware of the other’s branch. They agree on the verdict and on the node count of every one of the sixteen chunks, totalling 119,110,352,726; only the timings differ (32,695 s of engine time against 32,544 s). For a deterministic search that is the expected outcome and it rules out a class of environment-dependent faults, but both runs used SYM16, so this replicates the run and not the engine. The single-engine defect below is unaffected.
The same defect as at n = 17, one rung more expensive. The plain-engine replication is projected at roughly nine times the SYM16 node count, on the order of 1.1 × 1012 nodes and about 80 core-hours, and it was not run. So a(17) = 42 and a(18) = 47 both rest on Lemma 6′ and the validation battery of section 4, not on a second independent exhaustion; a(16) = 37 is the only one of the three that meets the two-engine standard. Both replications remain open threads.
The growth from n = 17 to n = 18 is ×5.55 in nodes (2.15 × 1010 to 1.19 × 1011) and ×5.35 in engine CPU time (6,086 s to 32,544 s), a little above the ×3–5 band the rest of the ladder sets. The previous version of this page forecast “on the order of 9 × 1010 nodes” for this rung; the true figure is 1.19 × 1011, about a third high, which is the honest score for a forecast made before the run.
Three consecutive open cases of A250000 have now been decided here, and all three land on ⌊7n²⁄48⌋. That is Ainley’s construction being exactly optimal three rungs in a row. It is not evidence that the formula continues: it is three data points against a construction that has been the best known since 1977, and nothing on this page bears on whether a(19) equals ⌊7 · 19²⁄48⌋ = 52.