Unit squares in a square, minimum container side

# Unit squares in a square, minimum container side ## Goal `pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`: `n` unit squares `(cx, cy, theta)`, where `(cx, cy)` is the centre and `theta` the rotation in **radians** (0 means axis-aligned; any real value is accepted). Interiors must be pairwise disjoint (touching is fine). The container is the smallest **axis-aligned** square that holds every corner you return; the eval derives its side `s` from your placements, you never report it. Minimise `s`. This is "Squares in Squares" from Erich Friedman's Packing Center (Friedman, *Packing unit squares in squares: a survey and new results*, Electronic Journal of Combinatorics DS7), now maintained by David Ellsworth. `s(n)` is the side of the smallest square containing `n` unit squares. It is known exactly for small `n` and for `n = k^2, k^2 - 1, k^2 - 2` (and a few more), but for most `n` the best packing on record is a construction found by hand or by simulated annealing, and several rows of the table were improved as recently as 2025-2026. The 24 instances here are exactly the values of `n` between 11 and 69 whose record is **not** proven optimal. Beat any row and you have a new Packing Center record. ## Metric metric = mean over the 24 instances of best_known(n) / s(n) `s(n)` is `max(width, height)` of the bounding box of the `4n` corners, so a packing that matches a record scores exactly `1.0` on that `n` and anything better scores above `1.0`. The eval validates every square before it measures anything: finite numbers, and no pair of squares overlapping by more than `EPS = 1e-9`, tested with the separating axis theorem on the four edge normals (the same geometry as this repository's `erdos-squares-in-square` pack). Touching is fine and penetration up to `EPS` is forgiven. A wrong answer on any `n` is a failed run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver, so your method must be robust to its starting point. The container's orientation is fixed (axis-aligned) but yours is not: rotate the whole packing so that the container's edges are axis-parallel, and translate it anywhere; only the bounding box is measured. ## Records Source: https://erich-friedman.github.io/packing/squinsqu/ (redirecting to Ellsworth's https://kingbird.myphotos.cc/packing/squares_in_squares.html), read 2026-09-07. The page prints each `s` to 14 decimals followed by an ellipsis, i.e. **truncated**, and those digits are used verbatim as the reference; the truncation is below `1e-14`, far under the eval's `1e-9` tolerance. "Rigid" and the polynomial forms are the page's. None of these rows is proven optimal (the page marks proven values "Proved by"; every row below reads "Found by"). | n | best known s | exact form (per the page) | found by | |---|---|---|---| | 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) | | 17 | 4.67553009360455 | degree-18 algebraic number (polynomial on the page) | John Bidwell, 1998, based on Pertti Hämäläinen's 1980 packing | | 18 | 4.82287565553229 | 7/2 + sqrt(7)/2 | Pertti Hämäläinen, 1980 (alternative with minimal rotated squares: Mats Gustafsson, 1981) | | 19 | 4.88561808316412 | 3 + 4 sqrt(2)/3 | Robert Wainwright, late 1979, based on Charles F. Cottingham's early-1979 packing | | 26 | 5.62132034355964 | 7/2 + 3 sqrt(2)/2 | Erich Friedman, 1997 | | 27 | 5.70710678118654 | 5 + sqrt(2)/2 | Frits Göbel, early 1979 | | 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) | | 29 | 5.93383346267692 | no closed form given | Thomas Schadt, December 2025 (simulated annealing); optimised by David Ellsworth | | 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 | | 38 | 6.70710678118654 | 6 + sqrt(2)/2 | Frits Göbel, early 1979 | | 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 | | 40 | 6.82842712474619 | 4 + 2 sqrt(2) | Frits Göbel, early 1979 (rigid) | | 41 | 6.92669309446880 | degree-42 algebraic number (polynomial on the page) | Thomas Schadt, December 2025; refined and optimised by David Ellsworth, January 2026 | | 50 | 7.57142857142857 | 7 + 4/7 | Thomas Schadt, December 2025; optimised by David Ellsworth (tilt from the 3-4-5 triple) | | 51 | 7.70079923541701 | degree-12 algebraic number (polynomial on the page) | Thomas Schadt, January 2026; optimised by David Ellsworth, February 2026 | | 52 | 7.70710678118654 | 7 + sqrt(2)/2 | Frits Göbel, early 1979 | | 53 | 7.82287565553229 | 13/2 + sqrt(7)/2 | David W. Cantrell, September 2002; improved December 2024 and by David Ellsworth, February 2026 | | 54 | 7.84666719284348 | 7 - sqrt(2)/2 + sqrt(1 + sqrt(2)) | David W. Cantrell, October 2005; improved by Joe DeVincentis, April 2014 | | 55 | 7.94577100750391 | no closed form given | Thomas Schadt, January 2026; improved and optimised by David Ellsworth, February 2026 | | 65 | 8.53553390593273 | 5 + 5 sqrt(2)/2 | Frits Göbel, early 1979 | | 66 | 8.65685424949238 | 3 + 4 sqrt(2) | Evert Stenlund, early 1980 | | 67 | 8.70710678118654 | 8 + sqrt(2)/2 | Evert Stenlund, early 1980, extending Göbel's s(52) | | 68 | 8.80345993651653 | no closed form given | Sigvart Brendberg, June 2023; improved by Thomas Schadt, December 2025; optimised by David Ellsworth | | 69 | 8.82721205592900 | degree-82 algebraic number (polynomial on the page) | Maurizio Morandi, June 2010; improved by David W. Cantrell, August 2023 | Not included, for the record: `s(n) = ceil(sqrt(n))` is proven for `n <= 10, 13-16, 22-24, 33-35, 46-48, 62-63` (Göbel, Friedman, Kearney-Shiu, Stromquist, Nagamochi, Bentz), and for the other `n <= 324` not pictured on the page the trivial grid is the best known. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval kills a call at `1.25 * time_budget + 3 s`. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_NS=11,17 python eval.py` runs a subset of the instances. - `ZT_EVAL_PER_N_SECONDS=1 python eval.py` shortens the per-`n` budget (default 4 s, so the full 24-instance eval takes about 100 s of solver time). ## Ideas that are known to matter (check the journal before repeating one) - Most records are a `k x k` grid with one corner region rebuilt: a strip of squares tilted by 45 degrees (Göbel's `k + sqrt(2)/2` family, n = 27, 38, 52, 67), or a diagonal band of tilted squares between two grid blocks (Stenlund, Friedman). Reproduce those families first; they cover a third of the table and cost nothing. - The 2025-2026 records (n = 28, 29, 39, 41, 50, 51, 55, 68) all came from simulated annealing on `(cx, cy, theta)` with a penalty for overlap and for the bounding box, started from randomness. Anneal on `s + w * overlap`, shrink `s` whenever the packing is feasible, and restart often. - Rational tilt angles from Pythagorean triples (3-4-5 gives `s(50) = 7 + 4/7`) let many squares share one tilt and pack exactly against each other. Try tilts `atan(3/4)`, `atan(5/12)`, ... - Finish every candidate with a local optimisation (coordinate descent on the corners' extreme coordinates) and a feasibility projection that pushes overlapping pairs apart along their SAT axis. 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.