Problem Description

You are given two positive integers, n and m, representing the dimensions of a rectangle (n rows and m columns). Your task is to tile the entire rectangle with the fewest number of integer-sided square tiles. Each tile must be a square (its sides must be of equal length), and you may use as many as you like, but you must use as few as possible. You may not overlap tiles, and you must cover the rectangle perfectly (no gaps or overlaps). Tiles cannot extend beyond the borders of the rectangle.

The output should be the minimum number of square tiles needed to cover the entire rectangle.

• Each tile can be of any integer size from 1 up to min(n, m).
• You cannot reuse a tile in more than one place.
• The solution must be exact; partial coverings are not allowed.
• Constraints: 1 <= n, m <= 13

Thought Process

At first glance, one might consider simply filling the rectangle with the smallest possible tiles (1x1 squares), but this would obviously use the maximum number of tiles. Alternatively, you might try to use the largest possible square at each step, but this greedy approach doesn't always yield the optimal solution.

The key insight is that, due to the small constraints, we can afford to try all possible ways to place squares recursively but must optimize to avoid redundant computations. This leads us toward backtracking with memoization (also known as DFS with pruning and DP).

The challenge is to represent the current "state" of the rectangle efficiently, to avoid recomputing subproblems. We also need to decide, at each step, where to place the next square and what size it should be, always trying to minimize the total tile count.

Solution Approach

We solve this problem using a recursive backtracking approach, enhanced with memoization to avoid redundant work. Here's the step-by-step approach:

1. State Representation:
   • We represent the current state of the rectangle by tracking which cells are already covered.
   • A common and efficient way is to use a tuple or bitmask for each row, where each bit represents whether a cell is covered.
2. Recursive Search:
   • We search for the first uncovered cell (let's call it (i, j)).
   • We try to place the largest possible square at position (i, j) that does not overlap any already-covered cells or extend beyond the rectangle.
   • For each possible size (from largest to smallest), we:
     • Mark the cells covered by the square as filled.
     • Recursively solve for the rest of the rectangle.
     • Backtrack (unmark the cells) to try other possibilities.
   • We keep track of the minimum number of tiles used across all possibilities.
3. Memoization:
   • We cache results for each unique state (e.g., the current coverage of the rectangle) to avoid recomputation.
4. Base Case:
   • If all cells are covered, return 0 (no more tiles needed).
5. Optimization:
   • Always try the largest possible square first, as this often leads to fewer tiles.

This approach works well because the rectangle is small (maximum 13x13), so the number of states is manageable.

Example Walkthrough

Let's consider n = 2, m = 3 (a 2x3 rectangle).

1. The rectangle is initially empty. The first uncovered cell is (0, 0).
2. The largest square we can place at (0, 0) is 2x2 (since both n and m are at least 2). Place a 2x2 square at the top-left.
3. Now, cells (0,0), (0,1), (1,0), (1,1) are covered. The only uncovered cells are (0,2) and (1,2).
4. For each of these, place a 1x1 square (since a 2x2 square would go out of bounds).
5. Total tiles used: 1 (2x2) + 2 (1x1) = 3.
6. Try other possibilities (e.g., only use 1x1 squares): would need 6 tiles. Try two 1x2 rectangles (not allowed - must be squares). Try three 2x1 squares (not allowed - must be squares).
7. So, the optimal solution is 3 tiles.

Time and Space Complexity

Brute-force approach:

• Would try every possible way to tile the rectangle, leading to exponential time complexity: O(2^(n*m)) or worse.

• There are at most 2^(n*m) unique states (each cell covered or not), but in practice, far fewer are visited due to pruning and memoization.
• Time complexity is O(2^(n*m)), but with heavy pruning and memoization, it is much faster for n, m ≤ 13.
• Space complexity is O(2^(n*m)) for the memoization table.

The reason for the exponential complexity is that each cell can be covered in many different ways, and we have to consider all combinations.

Summary

The problem of tiling a rectangle with the fewest squares is a classic example of recursive search with memoization. The main insight is to represent the problem's state efficiently and prune unnecessary branches by always trying the largest possible square first. Despite the exponential number of possible tilings, the small constraints and clever use of memoization make the problem tractable. This solution demonstrates the power of combining recursion, backtracking, and dynamic programming to solve complex combinatorial problems efficiently.

Code Implementation

from functools import lru_cache

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        if n == m:
            return 1

        @lru_cache(None)
        def dfs(heights):
            if all(h == m for h in heights):
                return 0
            min_height = min(heights)
            idx = heights.index(min_height)
            max_size = 1
            while (idx + max_size <= n and
                   all(heights[i] == min_height for i in range(idx, idx + max_size)) and
                   min_height + max_size <= m):
                max_size += 1
            res = float('inf')
            for size in range(max_size - 1, 0, -1):
                new_heights = list(heights)
                for i in range(idx, idx + size):
                    new_heights[i] += size
                res = min(res, 1 + dfs(tuple(new_heights)))
            return res

        return dfs(tuple([0] * n))
      

#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int tilingRectangle(int n, int m) {
        if (n == m) return 1;
        unordered_map<string, int> memo;
        return dfs(vector<int>(n, 0), n, m, memo);
    }
    
    int dfs(vector<int>& heights, int n, int m, unordered_map<string, int>& memo) {
        string key = vecToString(heights);
        if (memo.count(key)) return memo[key];
        bool done = true;
        for (int h : heights) if (h != m) done = false;
        if (done) return 0;
        int min_h = INT_MAX, idx = -1;
        for (int i = 0; i < n; ++i) {
            if (heights[i] < min_h) {
                min_h = heights[i];
                idx = i;
            }
        }
        int max_size = 1;
        while (idx + max_size <= n) {
            bool can = true;
            for (int i = idx; i < idx + max_size; ++i)
                if (heights[i] != min_h) can = false;
            if (!can || min_h + max_size > m) break;
            ++max_size;
        }
        int res = INT_MAX;
        for (int size = max_size - 1; size > 0; --size) {
            for (int i = idx; i < idx + size; ++i)
                heights[i] += size;
            res = min(res, 1 + dfs(heights, n, m, memo));
            for (int i = idx; i < idx + size; ++i)
                heights[i] -= size;
        }
        memo[key] = res;
        return res;
    }
    
    string vecToString(const vector<int>& v) {
        string res;
        for (int x : v) res += to_string(x) + ",";
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int tilingRectangle(int n, int m) {
        if (n == m) return 1;
        Map<String, Integer> memo = new HashMap<>();
        return dfs(new int[n], n, m, memo);
    }
    
    private int dfs(int[] heights, int n, int m, Map<String, Integer> memo) {
        String key = Arrays.toString(heights);
        if (memo.containsKey(key)) return memo.get(key);
        boolean done = true;
        for (int h : heights) if (h != m) done = false;
        if (done) return 0;
        int minH = Integer.MAX_VALUE, idx = -1;
        for (int i = 0; i < n; ++i) {
            if (heights[i] < minH) {
                minH = heights[i];
                idx = i;
            }
        }
        int maxSize = 1;
        while (idx + maxSize <= n) {
            boolean can = true;
            for (int i = idx; i < idx + maxSize; ++i)
                if (heights[i] != minH) can = false;
            if (!can || minH + maxSize > m) break;
            ++maxSize;
        }
        int res = Integer.MAX_VALUE;
        for (int size = maxSize - 1; size > 0; --size) {
            for (int i = idx; i < idx + size; ++i)
                heights[i] += size;
            res = Math.min(res, 1 + dfs(heights, n, m, memo));
            for (int i = idx; i < idx + size; ++i)
                heights[i] -= size;
        }
        memo.put(key, res);
        return res;
    }
}
      

var tilingRectangle = function(n, m) {
    if (n === m) return 1;
    const memo = new Map();
    function dfs(heights) {
        const key = heights.join(',');
        if (memo.has(key)) return memo.get(key);
        if (heights.every(h => h === m)) return 0;
        let minH = Math.min(...heights);
        let idx = heights.indexOf(minH);
        let maxSize = 1;
        while (
            idx + maxSize <= n &&
            heights.slice(idx, idx + maxSize).every(h => h === minH) &&
            minH + maxSize <= m
        ) {
            maxSize++;
        }
        let res = Infinity;
        for (let size = maxSize - 1; size > 0; size--) {
            for (let i = idx; i < idx + size; i++) heights[i] += size;
            res = Math.min(res, 1 + dfs(heights));
            for (let i = idx; i < idx + size; i++) heights[i] -= size;
        }
        memo.set(key, res);
        return res;
    }
    return dfs(Array(n).fill(0));
};