Tiling a Rectangle with the Fewest Squares — Hard Problem & Solution

Problem statement

Cover an n x m rectangle completely with squares whose sides are whole numbers. The squares may not overlap or stick out of the rectangle, and different squares may have different sizes.

Return the minimum number of squares needed.

Example 1

Input: n = 2, m = 3
Output: 3
Explanation: One 2x2 square and two 1x1 squares.

Example 2

Input: n = 5, m = 8
Output: 5
Explanation: A 5x5, a 3x3, a 2x2 and two 1x1 squares.

Example 3

Input: n = 11, m = 13
Output: 6
Explanation: The famous case where cutting the rectangle into two smaller rectangles is not optimal.

Constraints

• 1 <= n, m <= 13

How to solve Tiling a Rectangle with the Fewest Squares

Every tiling can be built by repeatedly covering the lowest-leftmost uncovered cell with a square anchored there. Branch over the square's size, track the filled profile as column heights, and use branch-and-bound to cut the search.

Approach

1. Keep h[c], the filled height of each of the m columns, and best = n * m (all unit squares).
2. dfs(count): if count >= best, return. Find the lowest height mn and its leftmost column i; if mn == n, the rectangle is full — set best = count.
3. The square anchored at column i can be as wide as the run of columns at height mn starting at i, and no taller than n - mn.
4. For each size from that maximum down to 1, raise those columns by the size, recurse with count + 1, and lower them back.
5. Return best.

Why it works

The lowest-leftmost uncovered cell must be the top-left corner of the square that covers it (anything to its left or below is already covered), so branching over that square's size enumerates every tiling. Trying big squares first finds a good tiling quickly, after which the count >= best bound discards almost everything else.

Complexity

• Time — Exponential in the worst case; a few thousand nodes for every input with n, m ≤ 13
• Space — O(m)

Pitfalls

• The "cut into two rectangles" DP is incorrect for 11 x 13 (it gives 8).
• The square anchored at the lowest cell is limited both by the run of equal-height columns and by the remaining height.
• n == m is a single square — handle it or let the search find it.

Reference solution

Python

def tilingRectangle(n: int, m: int) -> int:
    h = [0] * m
    best = [n * m]

    def dfs(cnt):
        if cnt >= best[0]:
            return
        mn = min(h)
        if mn == n:
            best[0] = cnt
            return
        i = h.index(mn)
        j = i
        while j < m and h[j] == mn and j - i < n - mn:
            j += 1
        for size in range(j - i, 0, -1):
            for k in range(i, i + size):
                h[k] += size
            dfs(cnt + 1)
            for k in range(i, i + size):
                h[k] -= size

    dfs(0)
    return best[0]

JavaScript

var tilingRectangle = function(n, m) {
    var h = new Array(m).fill(0);
    var best = n * m;
    var dfs = function(cnt) {
        if (cnt >= best) return;
        var mn = n + 1, at = -1;
        for (var c = 0; c < m; c++) if (h[c] < mn) { mn = h[c]; at = c; }
        if (mn === n) { best = cnt; return; }
        var j = at;
        while (j < m && h[j] === mn && j - at < n - mn) j++;
        for (var size = j - at; size >= 1; size--) {
            for (var k = at; k < at + size; k++) h[k] += size;
            dfs(cnt + 1);
            for (var k2 = at; k2 < at + size; k2++) h[k2] -= size;
        }
    };
    dfs(0);
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More backtracking problems

• Number of Squareful Arrays Hard
• Maximum Number of Achievable Transfer Requests Hard
• Stickers to Spell Word Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard
• Distribute Repeating Integers Hard