Unit cubes in the smallest cube

# Unit cubes in the smallest cube ## Goal `pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float, float, float, float]]`: `n` unit cubes `(x, y, z, ax, ay, az)`. `(x, y, z)` is the centre; `ax, ay, az` are Euler angles in **degrees**, applied as `R = Rz(az) @ Ry(ay) @ Rx(ax)` to the axis-aligned cube `[-1/2, 1/2]^3` before translating (the AlphaEvolve convention, so its constructions port unchanged). Interiors must be pairwise disjoint (touching is fine). The container is the smallest axis-aligned cube around all `8n` vertices, so `side(n) = max over the three coordinate axes of (max - min)`. Minimise `side(n)`. Rotating the whole configuration is free, so an axis-aligned container loses nothing. `s(n)`, the smallest such side, is Erich Friedman's "Cubes in Cubes" problem (Packing Center), and problem 35 ("packing in a dilate", arXiv:2511.02864 section 6.19) of the AlphaEvolve repository of problems. AlphaEvolve's contribution was `n = 11`: its construction (in the repository notebook; the eval below scores it at side 2.894531) beat Friedman's 1998 table and was listed as a world record, and has since been improved twice, most recently by Haowei Lin (July 2026). For every `n < 34` not in the table the trivial `ceil(n^(1/3))` grid is still the best known, so the whole range is soft. ## Metric metric = mean over n in {9, 10, 11, 12, 13, 14, 28} of best_known(n) / side(n) The eval validates every cube before measuring anything: six finite numbers, and no pair of cubes overlapping by more than `EPS = 1e-9`, tested with the full separating axis theorem (3 + 3 face normals plus the 9 edge-edge cross products, skipping cross products of nearly parallel edges as the AlphaEvolve verifier does). Touching is fine and penetration up to `EPS` is forgiven, the convention of this repository's other packing evals (the AlphaEvolve notebook instead demanded a strict `1e-9` gap). Then it recomputes `side(n)` from the vertices itself; nothing your solver reports is trusted. 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. ## Records Source: Erich Friedman, "Cubes in Cubes", Packing Center (fetched 2026-09-07). None of these is proven optimal; the page marks nothing as proven, and the only trivially proven values are `s(8) = 2` and `s(27) = 3` (volume). Values written `x+` on the page are used as written, so a packing exactly matching the record scores `1.0` up to the truncation. | n | best known side | found by | |---|---|---| | 9 | 2 + 1/sqrt(2) = 2.70710678... | Erich Friedman, 1998 | | 10 | 2 + 1/sqrt(2) = 2.70710678... | Erich Friedman, 1998 (same packing as n = 9) | | 11 | 2.88295 | Haowei Lin, July 2026 (previous: AlphaEvolve 2.894531, problem 35) | | 12 | 2.93277 | Haowei Lin, July 2026 | | 13 | 2.956 | Erich Friedman, 1998 | | 14 | 2 + 7 sqrt(2)/10 = 2.98994949... | Erich Friedman, 1998 | | 28 | 3 + 1/sqrt(2) = 3.70710678... | Erich Friedman, 1998 (same packing serves n = 28..33) | ## 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=9,11 python eval.py` runs a subset of the instances. - `ZT_EVAL_PER_N_SECONDS=2 python eval.py` shortens the per-`n` budget (default 15 s, so the full seven-instance eval takes about 105 s of solver time). ## Ideas that are known to matter (check the journal before repeating one) - Friedman's `2 + 1/sqrt(2)` packings put eight axis-aligned cubes in the corners and stand the rest on a face diagonal (45 degrees about one axis) in the slack. The `n = 11` and `n = 12` records tilt the inner cubes off every symmetry axis; the AlphaEvolve `n = 11` packing has the three inner cubes at three unrelated orientations. - Squeeze loops: fix the corner cubes, move each inner cube towards the centre by bisection on the overlap test, then shrink the corner cubes' bounding box uniformly by bisection. This is the `squeeze_placements_3d` routine AlphaEvolve was given; write your own, it is short. - Simulated annealing over `(x, y, z, ax, ay, az)` with the penalty `side + w * overlap_depth`, where overlap depth is the smallest projected penetration over the 15 SAT axes. - Snap angles to `{0, 45, 90, atan(1/sqrt(2)) = 35.264..} + multiples of 90` before a final polish. 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.