Tiling a Rectangle with the Fewest Squares

hard dp backtracking

Problem

Given an n x m rectangle, return the minimum number of integer-sided squares that tile it completely with no overlaps and no gaps.

Inputn = 5, m = 8

Output5

We track the filled height of each column (a "skyline") and repeatedly drop the largest square that fits at the lowest column.

n (height)

m (width)

def tiling_rectangle(n, m):
    # heights[c] = filled height of column c (the skyline)
    heights = [0] * m
    best = [m * n]

    def fill():
        min_h = min(heights)
        if min_h == n:                       # whole rectangle covered
            best[0] = min(best[0], count[0])
            return
        if count[0] + 1 >= best[0]:          # prune: cannot beat best
            return
        start = heights.index(min_h)         # leftmost lowest column
        end = start
        while end + 1 < m and heights[end + 1] == min_h:
            end += 1
        max_side = min(end - start + 1, n - min_h)
        for side in range(max_side, 0, -1):  # try largest squares first
            for c in range(start, start + side):
                heights[c] += side
            count[0] += 1
            fill()
            count[0] -= 1
            for c in range(start, start + side):
                heights[c] -= side

    count = [0]
    fill()
    return best[0]

function tilingRectangle(n, m) {
  const heights = new Array(m).fill(0);
  let best = m * n, count = 0;
  function fill() {
    const minH = Math.min(...heights);
    if (minH === n) { best = Math.min(best, count); return; }
    if (count + 1 >= best) return;          // prune
    const start = heights.indexOf(minH);
    let end = start;
    while (end + 1 < m && heights[end + 1] === minH) end++;
    const maxSide = Math.min(end - start + 1, n - minH);
    for (let side = maxSide; side >= 1; side--) {
      for (let c = start; c < start + side; c++) heights[c] += side;
      count++;
      fill();
      count--;
      for (let c = start; c < start + side; c++) heights[c] -= side;
    }
  }
  fill();
  return best;
}

class Solution {
    int n, m, best;
    int[] heights;
    public int tilingRectangle(int n, int m) {
        this.n = n; this.m = m; this.best = n * m;
        heights = new int[m];
        fill(0);
        return best;
    }
    void fill(int count) {
        int minH = Integer.MAX_VALUE, start = 0;
        for (int c = 0; c < m; c++)
            if (heights[c] < minH) { minH = heights[c]; start = c; }
        if (minH == n) { best = Math.min(best, count); return; }
        if (count + 1 >= best) return;
        int end = start;
        while (end + 1 < m && heights[end + 1] == minH) end++;
        int maxSide = Math.min(end - start + 1, n - minH);
        for (int side = maxSide; side >= 1; side--) {
            for (int c = start; c < start + side; c++) heights[c] += side;
            fill(count + 1);
            for (int c = start; c < start + side; c++) heights[c] -= side;
        }
    }
}

class Solution {
    int n, m, best;
    vector<int> heights;
    void fill(int count) {
        int minH = INT_MAX, start = 0;
        for (int c = 0; c < m; c++)
            if (heights[c] < minH) { minH = heights[c]; start = c; }
        if (minH == n) { best = min(best, count); return; }
        if (count + 1 >= best) return;
        int end = start;
        while (end + 1 < m && heights[end + 1] == minH) end++;
        int maxSide = min(end - start + 1, n - minH);
        for (int side = maxSide; side >= 1; side--) {
            for (int c = start; c < start + side; c++) heights[c] += side;
            fill(count + 1);
            for (int c = start; c < start + side; c++) heights[c] -= side;
        }
    }
public:
    int tilingRectangle(int n, int m) {
        this->n = n; this->m = m; best = n * m;
        heights.assign(m, 0);
        fill(0);
        return best;
    }
};

Explanation

There is no neat closed-form for the fewest squares, so we search, but we search smartly. We model the partially-tiled rectangle as a skyline: heights[c] is how tall column c has been filled so far. The rectangle is finished when every column reaches height n.

At each step we always fill the lowest, leftmost gap first. This is the key to avoiding duplicate orderings — there is exactly one place we are forced to place the next square, only its size is a choice.

From the leftmost lowest column we find the run of equally-low columns, and the biggest square that fits is limited both by that run's width and by the remaining vertical room n - minH. We try square sizes from large down to 1, place one, recurse, then undo (classic backtracking).

Two prunings keep it fast: trying the largest squares first finds a good solution early, and we abandon any branch whose square count already reaches the best found (count + 1 >= best). Trying largest-first matters because tilings tend to need few big squares.

Example: 5 × 8. The optimal tiling uses one 5×5, then fills the remaining 5×3 strip, reaching a minimum of 5 squares.

Time: exponential (heavily pruned backtracking) Space: O(m) skyline + recursion depth