Filling rectangles with integer-sided squares

Problem

The problem statement is simple: Given natural numbers n and m, find the minimum number of integer-sided squares that tile an (n,m) rectangle. (The problem was posed to me by David Radcliffe).

Types of solutions

Square

If the rectangle is a square, then obviously one square is sufficient to fill it.

Scaling

If the two sides (n,m) of the rectangle have a common divisor d, then any solution for a rectangle of size (n/d,m/d) can be scaled up to a solution of size (n,m).

Splitting

Another possible reduction is by splitting a rectangle of size (n,m) into two rectangles horizontally ((h,m) and (n-h,m)) or vertically ((n,v) and (n,m-v)).

Basic solutions

Sometimes none of the reductions mentioned yields an optimal solution. The smallest such case is (13,11).

Basic solutions are represented as a sequence of pairs of numbers, each representing a square. In each step, the area of the rectangle that is already filled has the shape of a Young tableaux. The first number indicates which of the top-left corners of the free area is going to be filled. The second number is the size of the square. The following image illustrates this for the (54,43) rectangle.

Note: conversion to Bouwkamp notation can be done using the interactive browser.

Properties

Let h(n,m) be the minimum number of integer-sided squares that tile an (n,m) rectangle.

Known

1. h(n,m) ≤ max(n,m)
2. h(n+m,m) = h(n,m) + 1 for m ≤ 4
3. h(n+m,m) = h(n,m) + 1 if 3n ≥ m²
4. h(13,11) < h(a,11) + h(13-a,11) and h(13,11) < h(13,b) + h(13,11-b) for 1 ≤ a ≤ 12 and 1 ≤ b ≤ 10

Proofs of these facts are on a separate page.

Conjectures

1. h(n+m,m) = h(n,m) + 1 if n ≥ m
   Counterexample: h(112,53) = h(59,53) = 11.
2. h(dn,dm) = h(n,m)
   (This is likely to be false, see this question on Mathoverflow)

Implementation notes

The implementations operate on sequences of so-called valleys, which may be visualized by turning a Young tableaux by 135 degrees such that the top-left corner moves to the bottom. The empty area can now be described as a sequence of lines from left to right, alternating between downwards and upwards slopes. Each pair of downward and upward slopes is a valley.

In each level of the search, one of the valleys is chosen and filled with a square. To avoid duplicate work, we also keep track of which squares have already been tried for each valley, in the form of a lower bound on the squares that may be used to fill it.

Finally, a simple heuristic is used for truncating the search tree: a sequence of n valleys needs at least n squares to be filled completely.

Rather than iterative deepening, the program searches for solutions starting from an upper bound derived from the simple reductions listed earlier. This is faster in general, but makes the runtime sensitive to the search order. It turns out (contrary to my expectations) that trying to fill valleys with small squares first finds solutions faster than starting with big squares.

Files

• Haskell implementation
• C++ implementation (≈ 60× 2000× faster, using different data structure)
• multi-threaded version
• list of results (Note that between 2016-06-14 and 2017-08-26 this list contained wrong results, see below.)
• Bouwkamp codes of results (gzip format)

Links

• OEIS entry
• Browse tilings (experimental; requires JavaScript and HTML5 canvas)
• Tiling by Squares
• Mathworld on dissecting squares
• CDF demonstration of minimal square tilings
• A paper that uses tilings of rectangles by squares for synthesizing resistors: On the synthesis of quantum Hall array resistance standards, Massimo Ortolano, Marco Abrate, Luca Callegaro, Metrologia 52(1), 2015 (arxiv.org version)

History