Square packing

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 ${\displaystyle a}$. If ${\displaystyle a}$ is an integer, the answer is ${\displaystyle a^{2},}$ but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer ${\displaystyle a}$ is an open question.^[1]

5 unit squares in a square of side length ${\displaystyle 2+1/{\sqrt {2}}\approx 2.707}$

10 unit squares in a square of side length ${\displaystyle 3+1/{\sqrt {2}}\approx 3.707}$

11 unit squares in a square of side length ${\displaystyle a\approx 3.877084}$

The smallest value of ${\displaystyle a}$ that allows the packing of ${\displaystyle n}$ unit squares is known when ${\displaystyle n}$ is a perfect square, one less than a perfect square, or two less than a perfect square, as well as for ${\displaystyle n}$ 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 ${\displaystyle a}$ is ${\displaystyle \lceil {\sqrt {n}}\,\rceil }$, where ${\displaystyle \lceil \,\ \rceil }$ is the ceiling (round up) function.^[2][3] 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.^[4][5]

The smallest unresolved case is ${\displaystyle n=11}$. It is known that 11 unit squares cannot be packed in a square of side length less than ${\displaystyle \textstyle 2+{\frac {4}{\sqrt {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.^[4][6]

The smallest case where the best known packing involves squares at three different angles is ${\displaystyle n=17}$. It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length ${\displaystyle a\approx 4.6756}$.^[4]

Below are the minimum solutions for values up to ${\displaystyle n=16}$; the case ${\displaystyle n=11}$ remains unresolved.^[7]

More information Number of unit squares ...

Number of unit squares ${\displaystyle n}$	Minimal side length ${\displaystyle a}$ of big square
1	1
2, 3, 4	2
5	${\displaystyle 2+{\frac {\sqrt {2}}{2}}\approx 2.707\ldots }$
6, 7, 8, 9	3
10	${\displaystyle 3+{\frac {\sqrt {2}}{2}}\approx 3.707\ldots }$
11	3.877... ?
12, ..., 16	4

Close

Some numbers of unit squares are never the optimal number in a packing. In particular, if a square of size ${\displaystyle a\times a}$ allows the packing of ${\displaystyle n^{2}-2}$ unit squares, then it must be the case that ${\displaystyle a\geq n}$ and that a packing of ${\displaystyle n^{2}}$ unit squares is also possible.^[2]

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 ${\displaystyle n=12}$ (although only the cases ${\displaystyle n=1,2}$ and ${\displaystyle n=4}$ are known to be optimal):^[13]

More information , ...

Number of squares	Circle radius
1	${\displaystyle {\sqrt {2}}/2\approx 0.707\ldots }$
2	${\displaystyle {\sqrt {5}}/2\approx 1.118\ldots }$
3	${\displaystyle 5{\sqrt {17}}/16\approx 1.288\ldots }$
4	${\displaystyle {\sqrt {2}}\approx 1.414\ldots }$
5	${\displaystyle {\sqrt {10}}/2\approx 1.581\ldots }$
6	1.688...
7	${\displaystyle {\sqrt {13}}/2\approx 1.802\ldots }$
8	1.978...
9	${\displaystyle {\sqrt {1105}}/16\approx 2.077\ldots }$
10	${\displaystyle 3{\sqrt {2}}/2\approx 2.121\ldots }$
11	2.214...
12	${\displaystyle {\sqrt {5}}\approx 2.236\ldots }$

Close

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.^[14]

• Circle packing in a square
• Squaring the square
• Rectangle packing
• Moving sofa problem