Structure-Guided Search for Packing Unit Squares in a Square: Empirical Regularities of Best-Known Packings and Their Use as Search Priors

Let s(n) be the side of the smallest square that contains n non-overlapping unit squares. For large n a direct search over the 3n positions and angles is expensive, and the best-known packings for n < 1000 come from heavy GPU computations. We ask whether the structure of best-known packings is regular enough to guide a much cheaper search. In 531 certified best-known packings with n < 1000 we observe that 49% of tilted squares are at exactly 45◦, that the dominant tilt is organised by the fractional part of the side, that neighbouring tilted squares share the same angle within 0.5◦ in 90.6% of pairs, and that the waste per unit length of tilted boundary grows from about 0.04 at small tilts to 0.39 near 45◦. A depth-3 decision tree that sees only n and is trained on odd n (or odd ⌈√n⌉) puts the structure class of the best-known packing of even n among its first two choices in 96–99% of cases, and it recovers the side-based regime rule from n alone. Used as a search prior above n = 1000, a structure family with a few parameters per n gives certified upper bounds for 5601 values of n in 1182 ≤ n ≤ 9946 that are below the entries of two public indices, by 0.084 on average and up to 0.207; for K = 100 the number of squares that must be removed from the K × K grid before the side drops below K falls from 87 to 54. For n < 1000 the same family does not beat the GPU records. All statements are labelled as proven, empirical or perspective; no optimality is claimed.