{"id":"erdos-squares-in-square","name":"Erdős squares in a square, maximum total side length","family":"combinatorics","description":"Erdős' 1932 problem (AlphaEvolve repository problem 55): place n squares of any sizes and orientations in the unit square, interiors disjoint, to maximise the sum of their side lengths, for n in {10, 12, 14, 17, 26, 37, 50}. Scored against the conjecturally optimal k + c/k constructions.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["pack.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":"# Erdős squares in a square, maximum total side length\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float, float]]`:\n`n` squares `(cx, cy, theta, s)` inside the unit square `[0, 1] x [0, 1]`, where `(cx, cy)` is the\ncentre, `theta` the rotation in **radians** (0 means axis-aligned; any real value is accepted) and\n`s >= 0` the side length. Interiors must be pairwise disjoint (touching is fine). Maximise `sum(s)`.\n\nLet `f(n)` be the maximum. Erdős asked in 1932 whether `f(k^2 + 1) = k`, i.e. whether one extra\nsquare buys nothing over the trivial `k x k` grid. Erdős–Soifer (1995) and Campbell–Staton (2005)\nindependently gave the construction `f(k^2 + 2c + 1) >= k + c/k` for `-k < c < k` and conjectured\nit is optimal; Praton (2005, arXiv:math/0504341) showed that conjecture is equivalent to the\noriginal one. Baek, Koizumi and Ueoro (2024, arXiv:2411.07274) proved it when all squares are\naxis-parallel, so any improvement must use rotated squares. This is problem 55 of the AlphaEvolve\nrepository of problems (arXiv:2511.02864, section 6.35); AlphaEvolve matched the known\nconstructions for exactly the seven `n` used here and found nothing better. Beat any row of the\ntable below and you have disproved a 90-year-old conjecture.\n\n## Metric\n\n    metric = mean over n in {10, 12, 14, 17, 26, 37, 50} of  sum_s(n) / best_known(n)\n\nThe eval validates every square before it sums anything: finite numbers, `s >= 0`, all four corners\ninside the unit square (tolerance `EPS = 1e-9` per coordinate), and no pair of squares overlapping\nby more than `EPS`, tested with the separating axis theorem on the four edge normals, the same\ngeometry as the AlphaEvolve verifier. The tolerance runs the way this repository's other packing\nevals run it: touching is fine and penetration up to `EPS` is forgiven (the AlphaEvolve notebook\ninstead demanded a strict `1e-9` gap). A square with `s <= EPS` is a point: it must lie in the\nunit square and cannot overlap anything. A wrong answer on any `n` is a failed run. `ZT_EVAL_SEED` only changes\nthe `seed` handed to your solver, so your method must be robust to its starting point.\n\n## Records\n\n`n = k^2 + 2c + 1`, best known `k + c/k`. None is proven optimal in general (only `f(2) = 1`,\n`f(5) = 2` and `f(k^2) = k` are theorems, and the whole table is proven for axis-parallel packings).\n\n| n | k, c | best known | source |\n|---|---|---|---|\n| 10 | 3, 0 | 3 | Erdős–Soifer (1995) construction; AlphaEvolve problem 55 matched it |\n| 12 | 3, 1 | 10/3 = 3.3333... | Campbell–Staton (2005) construction; AlphaEvolve matched it |\n| 14 | 3, 2 | 11/3 = 3.6666... | Campbell–Staton (2005) construction; AlphaEvolve matched it |\n| 17 | 4, 0 | 4 | Erdős–Soifer construction; AlphaEvolve matched it |\n| 26 | 5, 0 | 5 | Erdős–Soifer construction; AlphaEvolve matched it |\n| 37 | 6, 0 | 6 | Erdős–Soifer construction; AlphaEvolve matched it |\n| 50 | 7, 0 | 7 | Erdős–Soifer construction; AlphaEvolve matched it |\n\nThe known constructions are axis-parallel. Start from the `k x k` grid of squares of side `1/k`\n(sum `k`). For `c >= 1`, replace a `c x c` block of it by a `(c + 1) x (c + 1)` grid of squares of\nside `c / (k (c + 1))`: the count rises by `2c + 1` and the sum by `c/k`. For `c = 0` the record is\nthe plain grid plus one zero-side square, which the eval accepts; Erdős' question is precisely\nwhether that extra square can ever be given positive size without losing more elsewhere. (For\n`c < 0`, merge a `|c| x |c|` block into `(|c| - 1)^2` squares of side `|c| / (k (|c| - 1))`.)\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval kills a call at `1.25 * time_budget + 3 s`.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating quickly\n\n- `ZT_EVAL_NS=10,17 python eval.py` runs a subset of the instances.\n- `ZT_EVAL_PER_N_SECONDS=2 python eval.py` shortens the per-`n` budget (default 15 s, so the\n  full seven-instance eval takes about 105 s of solver time).\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Reproducing `k + c/k` is a construction, not a search; write it down and spend the budget on\n  perturbations that rotate a few squares.\n- Any improvement must be non-axis-parallel (Baek–Koizumi–Ueoro). Look at where rotated squares\n  could wedge into the slack a `1/k` grid leaves once one cell is subdivided.\n- Penalty-method gradient descent on `-sum(s) + w * (overlap + outside)` over `(cx, cy, theta, s)`\n  with `w` ramped, then a final feasibility projection that shrinks offending squares slightly.\n- Combinatorial skeleton search: which squares touch which and at what angle, then continuous\n  optimisation of the rest.\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 erdos-squares-in-square. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED             seed handed to pack()\n  ZT_EVAL_PER_N_SECONDS    time budget per n (default 15)\n  ZT_EVAL_NS               comma-separated n values (default \"10,12,14,17,26,37,50\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\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_N_SECONDS\", \"15\"))\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", \"10,12,14,17,26,37,50\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nEPS = 1e-9\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known sum of side lengths for n = k^2 + 2c + 1 squares: k + c/k (Erdős–Soifer 1995,\n# Campbell–Staton 2005; conjectured optimal, see Praton arXiv:math/0504341). AlphaEvolve\n# (repository problem 55) matched exactly these seven. Update when a hub-verified submission\n# exceeds one: that would disprove the Erdős–Soifer conjecture.\nRECORDS = {10: 3.0, 12: 3 + 1 / 3, 14: 3 + 2 / 3, 17: 4.0, 26: 5.0, 37: 6.0, 50: 7.0}\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 pack.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 corners(cx: float, cy: float, theta: float, s: float) -> list[tuple[float, float]]:\n    \"\"\"The four vertices of the square, counter-clockwise.\"\"\"\n    h = s / 2.0\n    ux, uy = h * math.cos(theta), h * math.sin(theta)   # half-edge along the first side\n    vx, vy = -uy, ux                                    # half-edge along the second side\n    return [(cx + ux + vx, cy + uy + vy), (cx - ux + vx, cy - uy + vy),\n            (cx - ux - vx, cy - uy - vy), (cx + ux - vx, cy + uy - vy)]\n\n\ndef axes(pts: list[tuple[float, float]]) -> list[tuple[float, float]]:\n    \"\"\"Unit normals of the first two edges; the other two edges are parallel to these.\"\"\"\n    out = []\n    for i in range(2):\n        (x1, y1), (x2, y2) = pts[i], pts[i + 1]\n        nx, ny = -(y2 - y1), x2 - x1\n        nrm = math.hypot(nx, ny)\n        if nrm > 1e-12:\n            out.append((nx / nrm, ny / nrm))\n    return out\n\n\ndef project(pts: list[tuple[float, float]], ax: tuple[float, float]) -> tuple[float, float]:\n    ps = [x * ax[0] + y * ax[1] for x, y in pts]\n    return min(ps), max(ps)\n\n\ndef overlap(a: tuple, b: tuple) -> bool:\n    \"\"\"Separating axis theorem on two squares; True if they share interior deeper than EPS.\"\"\"\n    if a[3] <= EPS or b[3] <= EPS:\n        return False  # a point has no interior\n    pa, pb = corners(*a), corners(*b)\n    for ax in axes(pa) + axes(pb):\n        lo1, hi1 = project(pa, ax)\n        lo2, hi2 = project(pb, ax)\n        if hi1 <= lo2 + EPS or hi2 <= lo1 + EPS:\n            return False  # separated (touching, or overlapping by at most EPS, counts as separated)\n    return True\n\n\ndef validate(squares: list, n: int) -> float:\n    if not isinstance(squares, (list, tuple)) or len(squares) != n:\n        fail(f\"pack({n}) must return {n} squares\", \"wrong_answer\")\n    sq = []\n    for q in squares:\n        try:\n            cx, cy, theta, s = float(q[0]), float(q[1]), float(q[2]), float(q[3])\n        except Exception:\n            fail(f\"pack({n}) returned a non-square {q!r}\", \"wrong_answer\")\n        if not all(map(math.isfinite, (cx, cy, theta, s))) or s < 0:\n            fail(f\"pack({n}) returned a square with negative or non-finite parameters\", \"wrong_answer\")\n        for x, y in corners(cx, cy, theta, s):\n            if x < -EPS or x > 1 + EPS or y < -EPS or y > 1 + EPS:\n                fail(f\"pack({n}) placed a square outside the unit square: ({cx}, {cy}, theta={theta}, s={s})\", \"wrong_answer\")\n        sq.append((cx, cy, theta, s))\n    for i in range(n):\n        for j in range(i + 1, n):\n            # cheap circumcircle rejection first, then the exact SAT test\n            if math.hypot(sq[i][0] - sq[j][0], sq[i][1] - sq[j][1]) >= (sq[i][3] + sq[j][3]) * math.sqrt(0.5):\n                continue\n            if overlap(sq[i], sq[j]):\n                fail(f\"pack({n}): squares {i} and {j} overlap\", \"wrong_answer\")\n    return sum(q[3] for q in sq)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"pack.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import pack as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import pack.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"pack\"):\n        fail(\"pack.py must define pack(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"erdsq|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    for n in NS:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            squares = cand.pack(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"pack({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"pack({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        s = validate(squares, n)\n        per_n[n] = {\"sum_s\": round(s, 10), \"record\": RECORDS[n], \"ratio\": round(s / RECORDS[n], 6), \"seconds\": round(elapsed, 2)}\n        if s > RECORDS[n] + 1e-9:\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":{"pack.py":"\"\"\"Baseline: n equal axis-aligned squares on a ceil(sqrt(n))-grid. Scores about 0.85-0.95 of the\nrecords (sum n/m against k + c/k). Beat it.\"\"\"\n\nimport math\n\n\ndef pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float, float]]:\n    m = math.ceil(math.sqrt(n))\n    s = 1.0 / m\n    out = []\n    for i in range(m):\n        for j in range(m):\n            if len(out) < n:\n                out.append(((j + 0.5) * s, (i + 0.5) * s, 0.0, s))\n    return out\n"}}