Peaceable queens

# Peaceable queens ## Goal `queens.py` exposes `queens(n: int, time_budget: float, seed: int) -> tuple[list[tuple[int, int]], list[tuple[int, int]]]`: a pair `(white, black)` of lists of squares `(row, col)` with `0 <= row, col < n`. The two lists must have the same length, no square may appear twice or in both lists, and no white queen may attack a black queen: a white and a black queen may not share a row, a column, a diagonal (`row - col`) or an anti-diagonal (`row + col`). Queens of the same colour may attack each other freely. Maximise the common size of the two armies. If your search ends with armies of unequal size, drop queens from the larger one before returning: unequal armies are a failed run, not a smaller score. This is problem C1 of Stephen Ainley's *Mathematical Puzzles* (1977), OEIS A250000, the subject of Sloane's Numberphile video "Peaceable Queens" (2019). Exact values are known only for `n <= 15` (integer programming: Pratt 2014, Tabatabai 2018; the 15 x 15 answer is 32). For every `n` from 16 to 30 the best-known value is still Ainley's 1977 construction (four pentagonal blocks, the "4-blob", rediscovered by Jubin in 2015), which gives `floor(7 n^2 / 48)` queens per colour. Nobody has beaten it in almost fifty years, simulated annealing (Karpov 2016) and integer programming (Pratt, Tabatabai) both stall exactly at those numbers, and Clinch, Drescher, Huynh and Saffidine (arXiv:2406.06974, 2024) give evidence that the 7/48 density is asymptotically right. The gap to the upper bounds is nevertheless huge (`n^2 / 4` in general, 64 for `n = 16`), so a single extra queen on any board from 16 to 30 is a new record. ## Instances and records Every instance is scored against the best-known number of queens per colour. `record_ratio` for an instance is `queens / record`, so 1.0 is a match and above 1.0 is a new record. | n | best known | proven optimal | source | |---|---|---|---| | 16 | 37 | no (upper bound 64) | Ainley 1977 pp. 31-32; Pratt's ILP bounds, OEIS A250000 | | 17 | 42 | no (upper bound 72) | same | | 18 | 47 | no (upper bound 81) | same | | 19 | 52 | no (upper bound 90) | same | | 20 | 58 | no (upper bound 100) | same | | 21 | 64 | no | Ainley 1977; simulated annealing, Karpov 2016 | | 22 | 70 | no | same | | 23 | 77 | no | same | | 24 | 84 | no | same | | 25 | 91 | no | Ainley 1977, quoted by Sloane and Knuth in A250000 | | 26 | 98 | no | same | | 27 | 106 | no | Kamenetsky 2019 (A250000 file a250000_3.txt); Ainley had 105 | | 28 | 114 | no | Ainley 1977 | | 29 | 122 | no | same | | 30 | 131 | no | same | Every value equals `floor(7 n^2 / 48)` (Karpov's observation, A286283). The boards behind them are in Dmitry Kamenetsky's file on the OEIS entry ("Best known solutions for 12 <= n <= 30", 15 Oct 2019); every one of them was re-verified with this pack's checker on 2026-09-07 before the numbers were copied. The only upper bounds are Pratt's ILP bounds for `n <= 20` and Jubin's `n^2 / 4` ("amicable rooks" argument), so none of the 15 instances is settled. ## Metric metric = mean over n in {16, ..., 30} of queens(n) / record(n) The eval re-derives everything from the two square lists you return: integer coordinates on the board, no repeated square, equal army sizes, and the attack check between every white and every black queen. Any violation on any `n` is a failed run (`wrong_answer`), and a solver that raises or overruns `1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed, so your method has to be robust to its starting point. ## Constraints - Standard library only. No numpy, no scipy, no SAT or ILP libraries. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The default is 6 s per instance, so a full eval takes about 90 s; use the whole budget, nothing is gained by returning early. - Deterministic given `seed`: use `random.Random(seed)`. - Coordinates are `0..n-1`; which colour is which does not matter. ## Iterating quickly - `ZT_EVAL_INSTANCES=16,20` (comma-separated `n` values from the table) runs a subset. - `ZT_EVAL_PER_INSTANCE_SECONDS=2` shrinks the per-instance budget. Example: `ZT_EVAL_INSTANCES=16,17 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py`. ## Ideas that are known to matter (check the journal before repeating one) - Keep four line sets per colour (rows, columns, `row - col`, `row + col`). A square is legal for white iff none of its four lines carries a black queen. That makes add / remove / check O(1), which every strong search relies on. - The records are two pentagons plus their images under the central symmetry (Jubin's description in A250000: white in `x < 1/4, y < 1/2, x < y < x + 1/3` and `1/2 < x < 3/4, y < x - 1/3, y < 1 - x`, black by central symmetry). Parametrise that shape by a handful of integers and search the parameters before searching squares: every record for `n <= 30` is a lattice version of it. - Selcoe's "cracked block" boards (`n = 16k + 4`, the 58-queen 20 x 20 board in the OEIS examples) are a different pattern that ties the record; the two families may combine. - Simulated annealing on the objective `min(|W|, |B|)` with a penalty for attacked pairs reaches the records up to `n = 24` in minutes (Karpov). The move set that works is swap-colour and move-queen, not add/remove alone. - Local optimality is cheap to test: a board is stuck only if no legal empty square exists for the smaller army. Ruin-and-recreate on one corner of the board at a time explores neighbouring pentagon shapes without destroying the other three. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.