{"id":"peaceable-queens","name":"Peaceable queens","family":"combinatorics","description":"Ainley's peaceable armies of queens (OEIS A250000): place m white and m black queens on an n x n board so that no white queen attacks a black queen, maximising m, for n = 16..30 where the best-known values (Ainley 1977, floor(7n^2/48)) are unproven.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["queens.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Peaceable queens\n\n## Goal\n\n`queens.py` exposes `queens(n: int, time_budget: float, seed: int) -> tuple[list[tuple[int, int]], list[tuple[int, int]]]`:\na pair `(white, black)` of lists of squares `(row, col)` with `0 <= row, col < n`. The two lists must\nhave the same length, no square may appear twice or in both lists, and no white queen may attack a\nblack queen: a white and a black queen may not share a row, a column, a diagonal (`row - col`) or an\nanti-diagonal (`row + col`). Queens of the same colour may attack each other freely. Maximise the\ncommon size of the two armies. If your search ends with armies of unequal size, drop queens from\nthe larger one before returning: unequal armies are a failed run, not a smaller score.\n\nThis is problem C1 of Stephen Ainley's *Mathematical Puzzles* (1977), OEIS A250000, the subject of\nSloane's Numberphile video \"Peaceable Queens\" (2019). Exact values are known only for `n <= 15`\n(integer programming: Pratt 2014, Tabatabai 2018; the 15 x 15 answer is 32). For every `n` from\n16 to 30 the best-known value is still Ainley's 1977 construction (four pentagonal blocks, the\n\"4-blob\", rediscovered by Jubin in 2015), which gives `floor(7 n^2 / 48)` queens per colour. Nobody\nhas beaten it in almost fifty years, simulated annealing (Karpov 2016) and integer programming\n(Pratt, Tabatabai) both stall exactly at those numbers, and Clinch, Drescher, Huynh and Saffidine\n(arXiv:2406.06974, 2024) give evidence that the 7/48 density is asymptotically right. The gap to\nthe upper bounds is nevertheless huge (`n^2 / 4` in general, 64 for `n = 16`), so a single extra\nqueen on any board from 16 to 30 is a new record.\n\n## Instances and records\n\nEvery instance is scored against the best-known number of queens per colour. `record_ratio` for\nan instance is `queens / record`, so 1.0 is a match and above 1.0 is a new record.\n\n| n | best known | proven optimal | source |\n|---|---|---|---|\n| 16 | 37 | no (upper bound 64) | Ainley 1977 pp. 31-32; Pratt's ILP bounds, OEIS A250000 |\n| 17 | 42 | no (upper bound 72) | same |\n| 18 | 47 | no (upper bound 81) | same |\n| 19 | 52 | no (upper bound 90) | same |\n| 20 | 58 | no (upper bound 100) | same |\n| 21 | 64 | no | Ainley 1977; simulated annealing, Karpov 2016 |\n| 22 | 70 | no | same |\n| 23 | 77 | no | same |\n| 24 | 84 | no | same |\n| 25 | 91 | no | Ainley 1977, quoted by Sloane and Knuth in A250000 |\n| 26 | 98 | no | same |\n| 27 | 106 | no | Kamenetsky 2019 (A250000 file a250000_3.txt); Ainley had 105 |\n| 28 | 114 | no | Ainley 1977 |\n| 29 | 122 | no | same |\n| 30 | 131 | no | same |\n\nEvery value equals `floor(7 n^2 / 48)` (Karpov's observation, A286283). The boards behind them\nare in Dmitry Kamenetsky's file on the OEIS entry (\"Best known solutions for 12 <= n <= 30\",\n15 Oct 2019); every one of them was re-verified with this pack's checker on 2026-09-07 before the\nnumbers were copied. The only upper bounds are Pratt's ILP bounds for `n <= 20` and Jubin's\n`n^2 / 4` (\"amicable rooks\" argument), so none of the 15 instances is settled.\n\n## Metric\n\n    metric = mean over n in {16, ..., 30} of  queens(n) / record(n)\n\nThe eval re-derives everything from the two square lists you return: integer coordinates on the\nboard, no repeated square, equal army sizes, and the attack check between every white and every\nblack queen. Any violation on any `n` is a failed run (`wrong_answer`), and a solver that raises or\noverruns `1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed\nto your solver; the instance set is fixed, so your method has to be robust to its starting point.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy, no SAT or ILP libraries. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The default is 6 s per instance, so a full eval takes\n  about 90 s; use the whole budget, nothing is gained by returning early.\n- Deterministic given `seed`: use `random.Random(seed)`.\n- Coordinates are `0..n-1`; which colour is which does not matter.\n\n## Iterating quickly\n\n- `ZT_EVAL_INSTANCES=16,20` (comma-separated `n` values from the table) runs a subset.\n- `ZT_EVAL_PER_INSTANCE_SECONDS=2` shrinks the per-instance budget.\n\nExample: `ZT_EVAL_INSTANCES=16,17 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py`.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Keep four line sets per colour (rows, columns, `row - col`, `row + col`). A square is legal for\n  white iff none of its four lines carries a black queen. That makes add / remove / check O(1),\n  which every strong search relies on.\n- The records are two pentagons plus their images under the central symmetry (Jubin's description\n  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`,\n  black by central symmetry). Parametrise that shape by a handful of integers and search the\n  parameters before searching squares: every record for `n <= 30` is a lattice version of it.\n- Selcoe's \"cracked block\" boards (`n = 16k + 4`, the 58-queen 20 x 20 board in the OEIS examples)\n  are a different pattern that ties the record; the two families may combine.\n- Simulated annealing on the objective `min(|W|, |B|)` with a penalty for attacked pairs reaches\n  the records up to `n = 24` in minutes (Karpov). The move set that works is swap-colour and\n  move-queen, not add/remove alone.\n- Local optimality is cheap to test: a board is stuck only if no legal empty square exists for the\n  smaller army. Ruin-and-recreate on one corner of the board at a time explores neighbouring\n  pentagon shapes without destroying the other three.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for peaceable-queens. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to queens()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per board size n (default 6)\n  ZT_EVAL_INSTANCES              comma-separated board sizes n (default \"16,...,30\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"6\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"16,17,18,19,20,21,22,23,24,25,26,27,28,29,30\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known number of queens per colour, OEIS A250000 (fetched 2026-09-07). For n = 16..30 every\n# value is Stephen Ainley's 1977 construction (Mathematical Puzzles, pp. 31-32; a(27) = 106 is one\n# better than Ainley's 105, from Kamenetsky's file a250000_3.txt) and equals floor(7*n^2/48). None of\n# them is proven optimal: the best upper bounds are Pratt's ILP bounds (64, 72, 81, 90, 100 for\n# n = 16..20) and n^2/4 in general. Every board in Kamenetsky's file was re-verified with this eval's\n# checker before the numbers were copied here. Update when a hub-verified submission exceeds these.\nRECORDS = {16: 37, 17: 42, 18: 47, 19: 52, 20: 58, 21: 64, 22: 70, 23: 77, 24: 84, 25: 91,\n           26: 98, 27: 106, 28: 114, 29: 122, 30: 131}\nPROVEN: set[int] = set()\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in queens.py: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef _coord(v, n: int) -> int:\n    if isinstance(v, bool) or not isinstance(v, (int, float)) or v != int(v):\n        fail(f\"queens({n}) returned a non-integer coordinate {v!r}\", \"wrong_answer\")\n    return int(v)\n\n\ndef _army(squares, n: int, colour: str) -> list[tuple[int, int]]:\n    if not isinstance(squares, (list, tuple, set, frozenset)):\n        fail(f\"queens({n}) must return two lists of (row, col) pairs; {colour} is {type(squares).__name__}\", \"wrong_answer\")\n    out = []\n    for s in squares:\n        try:\n            r, c = s\n        except Exception:\n            fail(f\"queens({n}) returned a non-square {s!r} in the {colour} army\", \"wrong_answer\")\n        r, c = _coord(r, n), _coord(c, n)\n        if not (0 <= r < n and 0 <= c < n):\n            fail(f\"queens({n}) placed a {colour} queen off the board: ({r}, {c})\", \"wrong_answer\")\n        out.append((r, c))\n    if len(set(out)) != len(out):\n        fail(f\"queens({n}) placed two {colour} queens on one square\", \"wrong_answer\")\n    return out\n\n\ndef validate(result, n: int) -> int:\n    \"\"\"Check the returned armies and return the queens per colour. Nothing the solver reports is trusted.\"\"\"\n    if not isinstance(result, (list, tuple)) or len(result) != 2:\n        fail(f\"queens({n}) must return a pair (white, black) of square lists\", \"wrong_answer\")\n    white = _army(result[0], n, \"white\")\n    black = _army(result[1], n, \"black\")\n    if len(white) != len(black):\n        fail(f\"queens({n}): armies must be equal in size, got {len(white)} white and {len(black)} black\", \"wrong_answer\")\n    shared = set(white) & set(black)\n    if shared:\n        fail(f\"queens({n}): square {sorted(shared)[0]} holds a queen of each colour\", \"wrong_answer\")\n    rows = {r for r, _ in black}\n    cols = {c for _, c in black}\n    diag = {r - c for r, c in black}\n    anti = {r + c for r, c in black}\n    for r, c in white:\n        if r in rows or c in cols or (r - c) in diag or (r + c) in anti:\n            for r2, c2 in black:\n                if r == r2 or c == c2 or r - c == r2 - c2 or r + c == r2 + c2:\n                    fail(f\"queens({n}): white queen {(r, c)} attacks black queen {(r2, c2)}\", \"wrong_answer\")\n    return len(white)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"queens.py\")\n    sys.dont_write_bytecode = True  # a stale queens.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import queens as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import queens.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"queens\"):\n        fail(\"queens.py must define queens(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"peaceable|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    for n in INSTANCES:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            result = cand.queens(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"queens({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"queens({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        m = validate(result, n)\n        per_n[n] = {\"queens\": m, \"record\": RECORDS[n], \"proven_optimal\": n in PROVEN,\n                    \"ratio\": round(m / RECORDS[n], 6), \"seconds\": round(elapsed, 2)}\n        if m > RECORDS[n]:\n            beaten.append(n)\n    metric = sum(v[\"ratio\"] for v in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_n\": per_n, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"queens.py":"\"\"\"Baseline: alternate greedy placement (prefer squares on lines the colour already uses) plus a\nfixed number of ruin-and-recreate rounds. Scores well under the records. Beat it.\"\"\"\n\nimport random\nimport time\n\n\nclass Armies:\n    \"\"\"Two armies with O(1) 'may colour k occupy (r, c)?' via the other colour's line sets.\"\"\"\n\n    def __init__(self):\n        self.queens = [[], []]\n        self.occ = set()\n        self.rows = [set(), set()]\n        self.cols = [set(), set()]\n        self.diag = [set(), set()]\n        self.anti = [set(), set()]\n\n    def free(self, k, r, c):\n        o = 1 - k\n        return ((r, c) not in self.occ and r not in self.rows[o] and c not in self.cols[o]\n                and (r - c) not in self.diag[o] and (r + c) not in self.anti[o])\n\n    def own_lines(self, k, r, c):\n        return (r in self.rows[k]) + (c in self.cols[k]) + ((r - c) in self.diag[k]) + ((r + c) in self.anti[k])\n\n    def add(self, k, r, c):\n        self.queens[k].append((r, c))\n        self.occ.add((r, c))\n        self.rows[k].add(r)\n        self.cols[k].add(c)\n        self.diag[k].add(r - c)\n        self.anti[k].add(r + c)\n\n\ndef queens(n: int, time_budget: float, seed: int) -> tuple[list[tuple[int, int]], list[tuple[int, int]]]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + time_budget\n    cells = [(r, c) for r in range(n) for c in range(n)]\n\n    def build(keep):\n        a = Armies()\n        for k in (0, 1):\n            for r, c in keep[k]:\n                a.add(k, r, c)\n        order = cells[:]\n        rng.shuffle(order)\n        k = 0\n        while True:\n            best, best_score = None, -1\n            for r, c in order:\n                if a.free(k, r, c):\n                    s = a.own_lines(k, r, c)\n                    if s > best_score:\n                        best, best_score = (r, c), s\n                        if s == 4:\n                            break\n            if best is None:\n                break\n            a.add(k, *best)\n            k = 1 - k\n        return a.queens\n\n    best = build(([], []))\n    for _ in range(300):  # a fixed round count keeps the result deterministic under seed\n        if time.perf_counter() > deadline:  # only bites when the budget is cut short\n            break\n        keep = tuple(rng.sample(army, int(len(army) * 0.75)) for army in best)\n        cand = build(keep)\n        if min(map(len, cand)) >= min(map(len, best)):\n            best = cand\n    m = min(map(len, best))\n    return best[0][:m], best[1][:m]\n"}}