Tiling a Rectangle with the Fewest Squares

Tiling a Rectangle with the Fewest Squares asks you to cover a rectangle using whole squares, minimizing how many you use. It is a classic backtracking problem: there is no clean formula, so we search every reasonable arrangement while aggressively pruning the hopeless ones.

The slow way first

You might hope for a formula, but minimal square tilings are surprisingly irregular — for some sizes the optimal layout looks nothing like a neat grid. The honest approach is to try placements and search. The danger is that the naive search explodes: at every empty cell you could place many square sizes, and the tree of choices grows enormous. We need structure to tame it.

The key question: where should I place the next square, and how do I avoid exploring layouts that already lost?

The idea: lowest-leftmost gap, then prune by best

Two ideas keep the search small. First, always fill the lowest, leftmost empty cell. Track a heights array — how high each column is filled. The next square must sit at the shortest column. This removes the freedom to place squares in random order, so each distinct tiling is reached once.

Second, prune by the best answer so far. Keep best, the fewest squares seen in any complete tiling. If a partial layout already used count >= best squares and is not finished, it can never win — abandon it immediately.

At each gap we try squares from the largest that fits down to 1 × 1. Trying big first tends to find a good best quickly, which makes pruning sharper for everything after.

Walk through it

Step through the animation on a 3 × 2 board. The shortest column starts at the far left, where a 2 × 2 fits. After placing it, the only gaps are the two cells of the rightmost column, each taking a 1 × 1. That completes the board with count = 3, so best = 3. Backtracking then explores other openings, but any path that reaches count = 3 without finishing is pruned. The answer is 3.

Pseudocode

best = W * H                      # worst case: every cell is its own 1x1
function dfs(heights, count):
    if every column is full:
        best = min(best, count); return
    if count >= best:             # this branch cannot beat best
        return
    c = index of the shortest column
    max_size = min(remaining height at c, remaining width from c)
    for size from max_size down to 1:
        place a size x size square at column c
        dfs(heights, count + 1)
        remove that square (backtrack)
dfs(all zeros, 0)
return best

The Python solution

def tiling(W, H):
    best = W * H            # worst case: all 1x1
    def dfs(heights, count):
        nonlocal best
        if all(h == H for h in heights):
            best = min(best, count); return
        if count >= best:
            return             # prune: cannot beat best
        c = heights.index(min(heights))
        for size in range(min(H - heights[c], W - c), 0, -1):
            place(heights, c, size); dfs(heights, count + 1); unplace(heights, c, size)
    dfs([0] * W, 0)
    return best

• best starts at W * H, the all-1 × 1 worst case, so any complete tiling improves it.
• The first if is the goal test: when every column reaches height H, the board is full — record best and return.
• if count >= best is the prune: an unfinished layout already at the budget cannot win, so we stop.
• heights.index(min(heights)) picks the lowest, leftmost column — our fixed placement rule.
• min(H - heights[c], W - c) is the largest square that fits without overflowing height or width; we try sizes largest first, then backtrack with unplace.

Complexity

The worst case is still exponential, but the lowest-leftmost rule plus pruning by best shrinks the real search to something instant for the constrained sizes these problems use.

When this pattern shows up

Practice