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 using planex2d.

Open this example in the playground, the interactive code editor in the browser, to change the code and run it.

import math

import planex as px

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\):

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:

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))

n 5 | s 2.7071067811865475 | out 0.0 | union 5.0 | free 2.32842712474619 s² - n 2.32842712474619

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):

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))

n 10 | s 3.7071067811865475 | out 0.0 | union 10.000000000000002 | free 3.7426406871192843 s² - n 3.742640687119284

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, which also lists the polynomials:

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))

n 17 | s 4.675530093604551 | out 0.0 | union 17.000000000000004 | free 4.860581656201783 s² - n 4.860581656201781

(a) 5 squares, side 2.707

(b) 10 squares, side 3.707

(c) 17 squares, side 4.676

Figure 1: 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 for px.Unify.