{"id":"squares-in-square-side","name":"Unit squares in a square, minimum container side","family":"combinatorics","description":"Erich Friedman's Packing Center problem: pack n unit squares, any orientation, into the smallest square, for 24 values of n between 11 and 69 whose best-known packing is not proven optimal. Scored as best-known side / your side, averaged over n.","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":"# Unit squares in a square, minimum container side\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`:\n`n` unit squares `(cx, cy, theta)`, where `(cx, cy)` is the centre and `theta` the rotation in\n**radians** (0 means axis-aligned; any real value is accepted). Interiors must be pairwise disjoint\n(touching is fine). The container is the smallest **axis-aligned** square that holds every corner\nyou return; the eval derives its side `s` from your placements, you never report it. Minimise `s`.\n\nThis is \"Squares in Squares\" from Erich Friedman's Packing Center (Friedman, *Packing unit squares\nin squares: a survey and new results*, Electronic Journal of Combinatorics DS7), now maintained by\nDavid Ellsworth. `s(n)` is the side of the smallest square containing `n` unit squares. It is known\nexactly for small `n` and for `n = k^2, k^2 - 1, k^2 - 2` (and a few more), but for most `n` the\nbest packing on record is a construction found by hand or by simulated annealing, and several rows\nof the table were improved as recently as 2025-2026. The 24 instances here are exactly the values\nof `n` between 11 and 69 whose record is **not** proven optimal. Beat any row and you have a new\nPacking Center record.\n\n## Metric\n\n    metric = mean over the 24 instances of  best_known(n) / s(n)\n\n`s(n)` is `max(width, height)` of the bounding box of the `4n` corners, so a packing that matches a\nrecord scores exactly `1.0` on that `n` and anything better scores above `1.0`. The eval validates\nevery square before it measures anything: finite numbers, and no pair of squares overlapping by\nmore than `EPS = 1e-9`, tested with the separating axis theorem on the four edge normals (the same\ngeometry as this repository's `erdos-squares-in-square` pack). Touching is fine and penetration up\nto `EPS` is forgiven. A wrong answer on any `n` is a failed run. `ZT_EVAL_SEED` only changes the\n`seed` handed to your solver, so your method must be robust to its starting point.\n\nThe container's orientation is fixed (axis-aligned) but yours is not: rotate the whole packing so\nthat the container's edges are axis-parallel, and translate it anywhere; only the bounding box is\nmeasured.\n\n## Records\n\nSource: https://erich-friedman.github.io/packing/squinsqu/ (redirecting to Ellsworth's\nhttps://kingbird.myphotos.cc/packing/squares_in_squares.html), read 2026-09-07. The page prints\neach `s` to 14 decimals followed by an ellipsis, i.e. **truncated**, and those digits are used\nverbatim as the reference; the truncation is below `1e-14`, far under the eval's `1e-9` tolerance.\n\"Rigid\" and the polynomial forms are the page's. None of these rows is proven optimal (the page marks\nproven values \"Proved by\"; every row below reads \"Found by\").\n\n| n | best known s | exact form (per the page) | found by |\n|---|---|---|---|\n| 11 | 3.87708359002281 | root of s^8 - 20s^7 + 178s^6 - 842s^5 + 1923s^4 - 496s^3 - 6754s^2 + 12420s - 6865 | Walter Trump, 1979 (rigid) |\n| 17 | 4.67553009360455 | degree-18 algebraic number (polynomial on the page) | John Bidwell, 1998, based on Pertti Hämäläinen's 1980 packing |\n| 18 | 4.82287565553229 | 7/2 + sqrt(7)/2 | Pertti Hämäläinen, 1980 (alternative with minimal rotated squares: Mats Gustafsson, 1981) |\n| 19 | 4.88561808316412 | 3 + 4 sqrt(2)/3 | Robert Wainwright, late 1979, based on Charles F. Cottingham's early-1979 packing |\n| 26 | 5.62132034355964 | 7/2 + 3 sqrt(2)/2 | Erich Friedman, 1997 |\n| 27 | 5.70710678118654 | 5 + sqrt(2)/2 | Frits Göbel, early 1979 |\n| 28 | 5.82444461667405 | root of s^6 - 24s^5 + 212s^4 - 812s^3 + 1025s^2 + 882s - 1615 | David Ellsworth, December 2025 (rigid; simulated annealing from randomness) |\n| 29 | 5.93383346267692 | no closed form given | Thomas Schadt, December 2025 (simulated annealing); optimised by David Ellsworth |\n| 37 | 6.59861960924436 | root of 36s^8 - 2496s^7 + 59768s^6 - 733760s^5 + 5289248s^4 - 23462672s^3 + 63458276s^2 - 96673872s + 64068561 | David W. Cantrell, September 2002 |\n| 38 | 6.70710678118654 | 6 + sqrt(2)/2 | Frits Göbel, early 1979 |\n| 39 | 6.81072208306864 | root of 9s^5 - 171s^4 + 999s^3 - 1959s^2 + 1636s + 166 | Thomas Schadt, January 2026; refined and optimised by David Ellsworth, January 2026 |\n| 40 | 6.82842712474619 | 4 + 2 sqrt(2) | Frits Göbel, early 1979 (rigid) |\n| 41 | 6.92669309446880 | degree-42 algebraic number (polynomial on the page) | Thomas Schadt, December 2025; refined and optimised by David Ellsworth, January 2026 |\n| 50 | 7.57142857142857 | 7 + 4/7 | Thomas Schadt, December 2025; optimised by David Ellsworth (tilt from the 3-4-5 triple) |\n| 51 | 7.70079923541701 | degree-12 algebraic number (polynomial on the page) | Thomas Schadt, January 2026; optimised by David Ellsworth, February 2026 |\n| 52 | 7.70710678118654 | 7 + sqrt(2)/2 | Frits Göbel, early 1979 |\n| 53 | 7.82287565553229 | 13/2 + sqrt(7)/2 | David W. Cantrell, September 2002; improved December 2024 and by David Ellsworth, February 2026 |\n| 54 | 7.84666719284348 | 7 - sqrt(2)/2 + sqrt(1 + sqrt(2)) | David W. Cantrell, October 2005; improved by Joe DeVincentis, April 2014 |\n| 55 | 7.94577100750391 | no closed form given | Thomas Schadt, January 2026; improved and optimised by David Ellsworth, February 2026 |\n| 65 | 8.53553390593273 | 5 + 5 sqrt(2)/2 | Frits Göbel, early 1979 |\n| 66 | 8.65685424949238 | 3 + 4 sqrt(2) | Evert Stenlund, early 1980 |\n| 67 | 8.70710678118654 | 8 + sqrt(2)/2 | Evert Stenlund, early 1980, extending Göbel's s(52) |\n| 68 | 8.80345993651653 | no closed form given | Sigvart Brendberg, June 2023; improved by Thomas Schadt, December 2025; optimised by David Ellsworth |\n| 69 | 8.82721205592900 | degree-82 algebraic number (polynomial on the page) | Maurizio Morandi, June 2010; improved by David W. Cantrell, August 2023 |\n\nNot included, for the record: `s(n) = ceil(sqrt(n))` is proven for `n <= 10, 13-16, 22-24, 33-35,\n46-48, 62-63` (Göbel, Friedman, Kearney-Shiu, Stromquist, Nagamochi, Bentz), and for the other\n`n <= 324` not pictured on the page the trivial grid is the best known.\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=11,17 python eval.py` runs a subset of the instances.\n- `ZT_EVAL_PER_N_SECONDS=1 python eval.py` shortens the per-`n` budget (default 4 s, so the full\n  24-instance eval takes about 100 s of solver time).\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Most records are a `k x k` grid with one corner region rebuilt: a strip of squares tilted by\n  45 degrees (Göbel's `k + sqrt(2)/2` family, n = 27, 38, 52, 67), or a diagonal band of tilted\n  squares between two grid blocks (Stenlund, Friedman). Reproduce those families first; they cover\n  a third of the table and cost nothing.\n- The 2025-2026 records (n = 28, 29, 39, 41, 50, 51, 55, 68) all came from simulated annealing on\n  `(cx, cy, theta)` with a penalty for overlap and for the bounding box, started from randomness.\n  Anneal on `s + w * overlap`, shrink `s` whenever the packing is feasible, and restart often.\n- Rational tilt angles from Pythagorean triples (3-4-5 gives `s(50) = 7 + 4/7`) let many squares\n  share one tilt and pack exactly against each other. Try tilts `atan(3/4)`, `atan(5/12)`, ...\n- Finish every candidate with a local optimisation (coordinate descent on the corners' extreme\n  coordinates) and a feasibility projection that pushes overlapping pairs apart along their SAT axis.\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 squares-in-square-side. 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 4)\n  ZT_EVAL_NS               comma-separated n values (default: the 24 instances below)\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\nDEFAULT_NS = \"11,17,18,19,26,27,28,29,37,38,39,40,41,50,51,52,53,54,55,65,66,67,68,69\"\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_N_SECONDS\", \"4\"))\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", DEFAULT_NS).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 side s(n) of a square holding n unit squares. Source: Erich Friedman's Packing Center,\n# \"Squares in Squares\" (https://erich-friedman.github.io/packing/squinsqu/), maintained since 2024 by\n# David Ellsworth at https://kingbird.myphotos.cc/packing/squares_in_squares.html; read 2026-09-07.\n# The page prints each s to 14 decimals followed by \"...\" (truncated, not rounded); those digits are\n# copied verbatim. None of these n is proven optimal there (every row reads \"Found by\", not \"Proved by\").\n# Update when a hub-verified submission beats one: that is a new record for the Packing Center.\nRECORDS = {\n    11: 3.87708359002281,   # Walter Trump 1979 (rigid); degree-8 algebraic\n    17: 4.67553009360455,   # John Bidwell 1998, from Pertti Hamalainen's 1980 packing; degree-18 algebraic\n    18: 4.82287565553229,   # Pertti Hamalainen 1980; 7/2 + sqrt(7)/2\n    19: 4.88561808316412,   # Robert Wainwright late 1979, from Charles Cottingham early 1979; 3 + 4 sqrt(2)/3\n    26: 5.62132034355964,   # Erich Friedman 1997; 7/2 + 3 sqrt(2)/2\n    27: 5.70710678118654,   # Frits Gobel early 1979; 5 + sqrt(2)/2\n    28: 5.82444461667405,   # David Ellsworth Dec 2025 (rigid); degree-6 algebraic\n    29: 5.93383346267692,   # Thomas Schadt Dec 2025, optimised by David Ellsworth\n    37: 6.59861960924436,   # David W. Cantrell Sep 2002; degree-8 algebraic\n    38: 6.70710678118654,   # Frits Gobel early 1979; 6 + sqrt(2)/2\n    39: 6.81072208306864,   # Thomas Schadt Jan 2026, optimised by David Ellsworth; degree-5 algebraic\n    40: 6.82842712474619,   # Frits Gobel early 1979 (rigid); 4 + 2 sqrt(2)\n    41: 6.92669309446880,   # Thomas Schadt Dec 2025, refined by David Ellsworth Jan 2026; degree-42 algebraic\n    50: 7.57142857142857,   # Thomas Schadt Dec 2025, optimised by David Ellsworth; 7 + 4/7\n    51: 7.70079923541701,   # Thomas Schadt Jan 2026, optimised by David Ellsworth Feb 2026; degree-12 algebraic\n    52: 7.70710678118654,   # Frits Gobel early 1979; 7 + sqrt(2)/2\n    53: 7.82287565553229,   # David W. Cantrell Sep 2002, improved Dec 2024 and by David Ellsworth Feb 2026; 13/2 + sqrt(7)/2\n    54: 7.84666719284348,   # David W. Cantrell Oct 2005, improved by Joe DeVincentis Apr 2014; 7 - sqrt(2)/2 + sqrt(1 + sqrt(2))\n    55: 7.94577100750391,   # Thomas Schadt Jan 2026, improved and optimised by David Ellsworth Feb 2026\n    65: 8.53553390593273,   # Frits Gobel early 1979; 5 + 5 sqrt(2)/2\n    66: 8.65685424949238,   # Evert Stenlund early 1980; 3 + 4 sqrt(2)\n    67: 8.70710678118654,   # Evert Stenlund early 1980; 8 + sqrt(2)/2\n    68: 8.80345993651653,   # Sigvart Brendberg Jun 2023, improved by Thomas Schadt Dec 2025, optimised by David Ellsworth\n    69: 8.82721205592900,   # Maurizio Morandi Jun 2010, improved by David W. Cantrell Aug 2023; degree-82 algebraic\n}\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) -> list[tuple[float, float]]:\n    \"\"\"The four vertices of the unit square centred at (cx, cy) rotated by theta, counter-clockwise.\"\"\"\n    ux, uy = 0.5 * math.cos(theta), 0.5 * 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(pa: list, pb: list) -> bool:\n    \"\"\"Separating axis theorem on two squares (given by corners); True if they share interior deeper than EPS.\"\"\"\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    \"\"\"Check the packing and return the side of the smallest axis-aligned square containing it.\"\"\"\n    if not isinstance(squares, (list, tuple)) or len(squares) != n:\n        fail(f\"pack({n}) must return {n} squares\", \"wrong_answer\")\n    centres, pts = [], []\n    for q in squares:\n        try:\n            cx, cy, theta = float(q[0]), float(q[1]), float(q[2])\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))):\n            fail(f\"pack({n}) returned a square with non-finite parameters\", \"wrong_answer\")\n        centres.append((cx, cy))\n        pts.append(corners(cx, cy, theta))\n    for i in range(n):\n        for j in range(i + 1, n):\n            # cheap circumcircle rejection first (two unit squares cannot overlap if centres are sqrt(2) apart)\n            if math.hypot(centres[i][0] - centres[j][0], centres[i][1] - centres[j][1]) >= math.sqrt(2.0):\n                continue\n            if overlap(pts[i], pts[j]):\n                fail(f\"pack({n}): squares {i} and {j} overlap\", \"wrong_answer\")\n    xs = [x for p in pts for x, _ in p]\n    ys = [y for p in pts for _, y in p]\n    return max(max(xs) - min(xs), max(ys) - min(ys))\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\"sqside|{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        if s <= 0:\n            fail(f\"pack({n}) returned a degenerate packing\", \"wrong_answer\")\n        per_n[n] = {\"side\": round(s, 10), \"record\": RECORDS[n], \"ratio\": round(RECORDS[n] / s, 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 axis-aligned unit squares on a ceil(sqrt(n)) grid, so the container side is\nceil(sqrt(n)). Scores about 0.93-0.99 of the records. Beat it.\"\"\"\n\nimport math\n\n\ndef pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]:\n    m = math.ceil(math.sqrt(n))\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, i + 0.5, 0.0))\n    return out\n"}}