Tiling a Rectangle with the Fewest Squares

hard backtracking pruning skyline

Problem

Given a rectangle of size n × m, return the minimum number of integer-sided squares that tile it. Squares may not overlap and must cover the whole rectangle.

Inputn = 2, m = 3

Output3

Three squares suffice: one 2×2 plus two 1×1 (a 2×3 area cannot be tiled by fewer).

n (height)

m (width)

def tilingRectangle(n, m):
    filled = [0] * n          # filled[r] is a bitmask of covered columns
    best = [n * m]

    def fits(r, c, side):
        if r + side > n or c + side > m:
            return False
        for i in range(r, r + side):
            for j in range(c, c + side):
                if filled[i] >> j & 1:
                    return False
        return True

    def mark(r, c, side, on):
        for i in range(r, r + side):
            for j in range(c, c + side):
                if on:
                    filled[i] |= 1 << j
                else:
                    filled[i] &= ~(1 << j)

    def dfs(count):
        if count >= best[0]:
            return
        pos = next(((r, c) for r in range(n) for c in range(m)
                    if not filled[r] >> c & 1), None)
        if pos is None:
            best[0] = count
            return
        r, c = pos
        side = 1
        while fits(r, c, side + 1):
            side += 1
        for s in range(side, 0, -1):
            mark(r, c, s, True)
            dfs(count + 1)
            mark(r, c, s, False)

    dfs(0)
    return best[0]

function tilingRectangle(n, m) {
  const filled = new Array(n).fill(0);   // bitmask of covered columns per row
  let best = n * m;

  function fits(r, c, side) {
    if (r + side > n || c + side > m) return false;
    for (let i = r; i < r + side; i++)
      for (let j = c; j < c + side; j++)
        if (filled[i] >> j & 1) return false;
    return true;
  }
  function mark(r, c, side, on) {
    for (let i = r; i < r + side; i++)
      for (let j = c; j < c + side; j++)
        filled[i] = on ? filled[i] | (1 << j) : filled[i] & ~(1 << j);
  }

  function dfs(count) {
    if (count >= best) return;
    let r = -1, c = -1;
    for (let i = 0; i < n && r < 0; i++)
      for (let j = 0; j < m; j++)
        if (!(filled[i] >> j & 1)) { r = i; c = j; break; }
    if (r < 0) { best = count; return; }
    let side = 1;
    while (fits(r, c, side + 1)) side++;
    for (let s = side; s >= 1; s--) {
      mark(r, c, s, true);
      dfs(count + 1);
      mark(r, c, s, false);
    }
  }

  dfs(0);
  return best;
}

class Solution {
    int n, m, best;
    int[] filled;   // bitmask of covered columns per row

    public int tilingRectangle(int n, int m) {
        this.n = n; this.m = m; this.best = n * m;
        this.filled = new int[n];
        dfs(0);
        return best;
    }
    boolean fits(int r, int c, int side) {
        if (r + side > n || c + side > m) return false;
        for (int i = r; i < r + side; i++)
            for (int j = c; j < c + side; j++)
                if ((filled[i] >> j & 1) != 0) return false;
        return true;
    }
    void mark(int r, int c, int side, boolean on) {
        for (int i = r; i < r + side; i++)
            for (int j = c; j < c + side; j++)
                filled[i] = on ? filled[i] | (1 << j) : filled[i] & ~(1 << j);
    }
    void dfs(int count) {
        if (count >= best) return;
        int r = -1, c = -1;
        for (int i = 0; i < n && r < 0; i++)
            for (int j = 0; j < m; j++)
                if ((filled[i] >> j & 1) == 0) { r = i; c = j; break; }
        if (r < 0) { best = count; return; }
        int side = 1;
        while (fits(r, c, side + 1)) side++;
        for (int s = side; s >= 1; s--) {
            mark(r, c, s, true);
            dfs(count + 1);
            mark(r, c, s, false);
        }
    }
}

class Solution {
    int n, m, best;
    vector<int> filled;   // bitmask of covered columns per row

    bool fits(int r, int c, int side) {
        if (r + side > n || c + side > m) return false;
        for (int i = r; i < r + side; i++)
            for (int j = c; j < c + side; j++)
                if (filled[i] >> j & 1) return false;
        return true;
    }
    void mark(int r, int c, int side, bool on) {
        for (int i = r; i < r + side; i++)
            for (int j = c; j < c + side; j++)
                filled[i] = on ? filled[i] | (1 << j) : filled[i] & ~(1 << j);
    }
    void dfs(int count) {
        if (count >= best) return;
        int r = -1, c = -1;
        for (int i = 0; i < n && r < 0; i++)
            for (int j = 0; j < m; j++)
                if (!(filled[i] >> j & 1)) { r = i; c = j; break; }
        if (r < 0) { best = count; return; }
        int side = 1;
        while (fits(r, c, side + 1)) side++;
        for (int s = side; s >= 1; s--) {
            mark(r, c, s, true);
            dfs(count + 1);
            mark(r, c, s, false);
        }
    }
public:
    int tilingRectangle(int n, int m) {
        this->n = n; this->m = m; best = n * m;
        filled.assign(n, 0);
        dfs(0);
        return best;
    }
};

Explanation

We want the fewest squares that exactly fill an n × m rectangle. There is no neat formula, so we try placing squares with backtracking and keep the smallest count we ever finish with in best.

To avoid wasted work, we always fill the first empty cell we find scanning top-to-bottom, left-to-right. Every valid tiling must cover that cell with some square, so we only have to decide the size of the square placed there — this keeps the search tidy and avoids duplicate arrangements.

The grid is stored compactly: filled[r] is a bitmask whose bits mark which columns of row r are already covered. The helper fits checks a square of a given side doesn't run off the edge or overlap, and mark flips those bits on or off.

At each step we compute the largest square that fits at the empty cell, then try sizes from big down to 1: place it, recurse, then remove it and try the next size. The crucial speedup is the line if count >= best: return — if we have already used as many squares as the best full solution, this branch can't win, so we prune it immediately.

Example: for 2 × 3, the first empty cell takes a 2×2 square, leaving a 2×1 strip that needs two 1×1 squares — total 3, which is the answer.

Time: exponential (heavily pruned) Space: O(m + n·m)