# Square packing

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 $a$. If $a$ is an integer, the answer is $a^{2},$ but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer $a$ is an open question.
$2+1/{\sqrt {2}}\approx 2.707$
$3+1/{\sqrt {2}}\approx 3.707$
$a\approx 3.877084$
The smallest value of $a$ that allows the packing of $n$ unit squares is known when $n$ is a perfect square (in which case it is ${\sqrt {n}}$), as well as for $n=$2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, and 48. For most of these numbers (with the exceptions only of 5 and 10), the packing is the natural one with axis-aligned squares, and $a$ is $\lceil {\sqrt {n}}\,\rceil$, where $\lceil \,\ \rceil$ 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 $n=11$. It is known that 11 unit squares cannot be packed in a square of side length less than $\textstyle 2+2{\sqrt {4/5}}\approx 3.789$. By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.877084 found by Walter Trump.
The smallest case where the best known packing involves squares at three different angles is $n=17$. It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length $a\approx 4.6756$.
Below are the minimum solutions for values up to $n=12$; the case $n=11$ remains unresolved:
| Number of unit squares $n$ | Minimal side length $a$ of big square | Minimal side length $a$ of big square |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 2 | 2 |
| 4 | 2 | 2 |
| 5 | 2.707... | $2+{\frac {\sqrt {2}}{2}}$ |
| 6 | 3 | 3 |
| 7 | 3 | 3 |
| 8 | 3 | 3 |
| 9 | 3 | 3 |
| 10 | 3.707... | $3+{\frac {\sqrt {2}}{2}}$ |
| 11 | 3.877... ? | 3.877... ? |
| 12 | 4 | 4 |

### Asymptotic results

For larger values of the side length $a$, the exact number of unit squares that can pack an $a\times a$ square remains unknown. It is always possible to pack a $\lfloor a\rfloor \!\times \!\lfloor a\rfloor$ grid of axis-aligned unit squares, but this may leave a large area, approximately $2a(a-\lfloor a\rfloor )$, 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 $o(a^{7/11})$ (here written in little o notation). Later, Graham and Fan Chung further reduced the wasted space to $O(a^{3/5})$. However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least $\Omega {\bigla^{1/2}(a-\lfloor a\rfloor ){\bigr )}$. In particular, when $a$ 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.
Some numbers of unit squares are never the optimal number in a packing. In particular, if a square of size $a\times a$ allows the packing of $n^{2}-2$ unit squares, then it must be the case that $a\geq n$ and that a packing of $n^{2}$ unit squares is also possible.

## 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 known for n up to 35. Here are the minimum known solutions for up to $n=12$ (although only the cases $n=1$ and $n=2$ are known to be optimal):
| Number of squares | Circle radius |
| 1 | ${\sqrt {2}}/2\approx 0.707\ldots$ |
| 2 | ${\sqrt {5}}/2\approx 1.118\ldots$ |
| 3 | $5{\sqrt {17}}/16\approx 1.288\ldots$ |
| 4 | ${\sqrt {2}}\approx 1.414\ldots$ |
| 5 | ${\sqrt {10}}/2\approx 1.581\ldots$ |
| 6 | 1.688... |
| 7 | ${\sqrt {13}}/2\approx 1.802\ldots$ |
| 8 | 1.978... |
| 9 | ${\sqrt {1105}}/16\approx 2.077\ldots$ |
| 10 | $3{\sqrt {2}}/2\approx 2.121\ldots$ |
| 11 | 2.214... |
| 12 | ${\sqrt {5}}\approx 2.236\ldots$ |

## 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.