---
jupyter:
  description: 'Square packing with planex2d: 5 unit squares in a square of side 2 + 1/√2, 10 in 3 + 1/√2 and the best
    known packing of 17 in about 4.6755, placed with Translated and Rotated and checked inside the container and free
    of overlaps by Boolean operations.'
---

# Square packing

How small a square holds $n$ squares of side 1? A grid of $\lceil \sqrt{n} \, \rceil$ by $\lceil \sqrt{n} \, \rceil$
always works, and for most small $n$ nothing smaller does. Five squares are the first exception. Four in the corners and
a fifth turned 45° between them fit in a square of side $2 + 1/\sqrt{2} \approx 2.707$ instead of 3. Ten squares fit in
a square of side $3 + 1/\sqrt{2}$, a packing that Frits Göbel found and Walter Stromquist proved best. The best known
packing of 17 squares, found by John Bidwell, turns squares at three different angles and needs a side of about 4.6755
instead of 5.

The example places the squares of all three packings with planex2d's `Translated` and `Rotated` and checks with
Boolean operations that every square lies in the container and that no two overlap.

This page is part of a collection of [geometry and design examples](geometry-and-design.md) using planex2d.

<!-- #raw raw_mimetype="text/restructuredtext" -->
.. rst-class:: px-example-links

`Open this example in the playground <https://planex2d.org/playground/>`__, the interactive code editor in the browser, to change the code and run it.
<!-- #endraw -->

![Ten and seventeen unit squares packed in the smallest known squares, the turned squares in blue](../_static/gallery/square-packing.png){.result}

```python
import math

import planex as px
```

```python nbsphinx="hidden"
from docs_figures import PLANEX, Row
```

## The check

A packing holds when no square sticks out of the container and no two squares overlap. The first is the Boolean
difference of each square and the container, which must be empty. The second is the area of the union of all
squares, which is $n$ only when no two overlap. The container less the squares then has the area $s^2 - n$:

```python
one = px.QuickSketch().Rectangle(1, 1).Face()


def check(s, squares):
    """sticking out, the union's area against n, and the free area against s^2 - n"""
    box = px.QuickSketch().Rectangle(s, s).Face()
    out = sum((square - box).mass for square in squares)
    union = px.Unify(squares)
    print("n", len(squares), "| s", s, "| out", out, "| union", union.mass, "| free", (box - union).mass,
          "s² - n", s * s - len(squares))
    return box
```

## Five squares

Four squares sit in the corners. The fifth is turned 45° about its own corner and moved to the point (1, 1), where
its sides touch the corners of the other four:

```python
s5 = 2 + 1 / math.sqrt(2)
five = [one, one.Translated((s5 - 1, 0)), one.Translated((0, s5 - 1)), one.Translated((s5 - 1, s5 - 1)),
        one.Translated((0, -0.5)).Rotated((0, 0), 45).Translated((1, 1))]
box5 = check(s5, five)
# px.Plot(px.Compound(five))
```

## Ten squares

Three squares form an L in one corner and a single square sits in the next corner. Turned half a turn about the
center, the same four fill the opposite corners. Two squares turned 45° fill the diagonal between them (Figure 1):

```python
s10 = 3 + 1 / math.sqrt(2)
corner = [one, one.Translated((1, 0)), one.Translated((0, 1)), one.Translated((s10 - 1, 0))]
ten = corner + [square.Rotated((s10 / 2, s10 / 2), 180) for square in corner]
ten += [one.Translated((0, dy)).Rotated((0, 0), 45).Translated((1.5, 1.5)) for dy in (-1, 0)]
box10 = check(s10, ten)
# px.Plot(px.Compound(ten))
```

## Seventeen squares

In Bidwell's packing, eight squares stand straight along the bottom and the two sides. A block of six, in three rows
of two that are offset a little, is turned by the angle $a \approx 39.80°$. At the top, one square stands straight
and one is turned back by $b \approx 36.62°$, and one more stands at the right side. The side, the two angles and the
offsets are roots of polynomials. The numbers below are taken to 18 digits from the
[squares-in-squares page](https://kingbird.myphotos.cc/packing/squares_in_squares.html), which also lists the
polynomials:

```python
s17 = 4.67553009360455095
a, b = 39.80495897976779506, 36.62378638344658932
x1, v0, u1, u2 = 0.640176192429266088, 0.056838696870287318, 0.276426766820379851, 0.404478693276882795
x3, y4, r5 = 1.847324826510285097, 3.113460132512564046, 0.505927428006637436

side = [one, one.Translated((1, 0)), one.Translated((0, 1)), one.Translated((0, s17 - 1))]
mirrored = [square.Mirrored((s17 / 2, 0), (0, 1)) for square in side]
block = [one.Translated(d).Rotated((0, 0), a).Translated((x1, 2))
         for d in [(0, 0), (1, v0), (u1, -1), (u1 + 1, -1 + v0), (u2, -2), (u2 + 1, -2 + v0)]]
top = [one.Translated((x3, s17 - 1)), one.Translated((0, -r5)).Rotated((0, 0), -b).Translated((1 + x3, s17 - 1))]
seventeen = side + mirrored + block + top + [one.Translated((s17 - 1, y4 - 1))]
box17 = check(s17, seventeen)
# px.Plot(px.Compound(seventeen))
```

```python nbsphinx="hide-input"
def panel(box, squares, turned, text):
    return (px.Compound(squares), text, {"dashed": [box], "fills": [(q, PLANEX) for q in turned]})


Row(panel(box5, five, five[4:], "5 squares, side 2.707"), panel(box10, ten, ten[8:], "10 squares, side 3.707"),
    panel(box17, seventeen, block + top[1:], "17 squares, side 4.676"),
    caption="The three packings, the turned squares in blue, the container dashed")
```

The squares fill 68 %, 73 % and 78 % of their containers. Seventeen squares in a grid of side 5 would fill 68 %.

See [Many faces](../core/booleans/many-faces.md) for `px.Unify`.

```python nbsphinx="hidden"
import sys
import matplotlib.pyplot as plt
sys.path.insert(0, "..")
from docs_figures import FACE, INK
from gallery import save_figure

fig, ax = plt.subplots(figsize=(6, 4))
for shift, box, squares, turned in ((0, box10, ten, ten[8:]), (s10 + 0.8, box17, seventeen, block + top[1:])):
    for square in squares:
        color = PLANEX if any(square is q for q in turned) else FACE
        square.Translated((shift, 0)).Plot(ax=ax, face_col=color, line_col=INK, legend=False)
    box.Translated((shift, 0)).Plot(ax=ax, face_col=None, line_col=INK, legend=False)
ax.set_xlim(-0.35, s10 + s17 + 1.15)
ax.set_ylim(s17 / 2 - 3.05, s17 / 2 + 3.05)
ax.set_aspect("equal")
ax.axis("off")
save_figure(fig, "square-packing")
plt.close(fig)
```