Square packing is a packing problem where the objective is to determine how many congruent squares can be packed into some larger shape, often a square or circle.
In a square Square packing in a square is the problem of determining the maximum number of unit squares (squares of side length one) that can be packed inside a larger square of side length . If is an integer, the answer is but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer is an open question.
The smallest value of that allows the packing of unit squares is known when is a perfect square, one less than a perfect square, or two less than a perfect square, as well as for equal to 5, 6, 10, 13, and 46. For all of these numbers except 5 and 10, the packing is the natural one with axis-aligned squares, and the optimal value of is , where is the ceiling (round up) function. The figure shows the optimal packings for 5 and 10 squares, the two smallest numbers of squares for which the optimal packing involves tilted squares.
The smallest unresolved case is . It is known that 12 unit squares cannot be packed in a square of side length less than . By contrast, the tightest known packing of 12 squares is inside a square of side length 4, in three rows of four. The optimal packing for was shown on September 29, 2026 in an AI-assisted proof to be approximately 3.877084, using Walter Trump's original packing from 1979.
The smallest case where the best known packing involves squares at three different angles is . It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length .
Below are the minimum solutions for values up to ; the case remains unresolved. Number of unit squares Minimal side length of big square1 12, 3, 4 256, 7, 8, 93101112, ..., 16 4
Some numbers of unit squares are never the optimal number in a packing. In particular, if a square of size allows the packing of unit squares, then it must be the case that and that a packing of unit squares is also possible.
Asymptotic results
For larger values of the side length , the exact number of unit squares that can pack an square remains unknown. It is always possible to pack a grid of axis-aligned unit squares, but this may leave a large area, approximately , uncovered and wasted. Instead, Paul Erdős and Ronald Graham showed that for a different packing by tilted unit squares, the wasted space could be significantly reduced to (the latter written in little o notation). Later, Graham and Fan Chung further reduced the wasted space to , and subsequent work reduced the wasted space to , and then . However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least . In particular, when is a half-integer, the wasted space is at least proportional to its square root. The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem.
In a circle Square packing in a circle is a related problem of packing n unit squares into a circle with radius as small as possible. For this problem, good solutions are published for n up to 50. Here are the minimum known solutions for up to (although only the cases from to are proven to be optimal):
Number of squaresCircle radius1234561.688...781.978...910112.214...12
In other shapes Packing squares into other shapes can have high computational complexity: testing whether a given number of axis-parallel unit squares can fit into a given polygon is NP-complete. It remains NP-complete even for a simple polygon (with no holes) that is orthogonally convex, with axis-parallel sides, and with half-integer vertex coordinates.
See also Circle packing in a square Squaring the square Rectangle packing Moving sofa problem
References
External links