Tiling a Rectangle with the Fewest Squares

• The state of the tiling is represented by a 2D boolean grid covered[n][m], where true indicates a cell is covered.
• A global variable ans stores the minimum number of squares found, initialized to a large value (e.g., n * m).
• A recursive function, dfs(covered, count), explores tiling possibilities.
• Pruning: If the current count of squares count is already greater than or equal to ans, the function returns immediately.
• Base Case: The function scans the grid to find the first uncovered cell (r, c). If no such cell is found, the rectangle is fully tiled. ans is updated with min(ans, count).
• Recursive Step:
  • For the uncovered cell (r, c), the algorithm tries to place squares of every possible size s (from largest to smallest) that can fit.
  • To place a square, it must fit within the rectangle's boundaries and not overlap with any already covered cells.
  • For each valid placement:
    1. Mark the corresponding cells in the covered grid as true.
    2. Make a recursive call: dfs(covered, count + 1).
    3. Backtrack: Revert the changes to the covered grid by marking the cells back to false.

The core idea is to perform a depth-first search (DFS) on the state of the rectangle. The state is defined by which cells are covered. We start with a completely empty rectangle and recursively add one square at a time.

We begin by finding the top-most, left-most empty cell. Then, we try to place the largest possible square that covers this cell. After placing the square, we make a recursive call to solve for the rest of the rectangle. Once the recursive call returns, we backtrack by removing the square and trying the next smaller size. This process continues until all possibilities are exhausted.

To avoid exploring fruitless paths, we use pruning. A global variable ans holds the minimum number of squares found so far. If the current number of squares used in a path (count) meets or exceeds ans, we abandon that path.

1class Solution {2    int ans;3 4    public int tilingRectangle(int n, int m) {5        if (n == m) return 1;6        ans = n * m;7        boolean[][] covered = new boolean[n][m];8        dfs(n, m, 0, 0, covered, 0);9        return ans;10    }11 12    private void dfs(int n, int m, int r, int c, boolean[][] covered, int count) {13        if (count >= ans) {14            return;15        }16 17        // Find the first uncovered cell, starting from (r, c)18        while (r < n && covered[r][c]) {19            c++;20            if (c == m) {21                r++;22                c = 0;23            }24        }25 26        // If all cells are covered, we found a solution27        if (r == n) {28            ans = Math.min(ans, count);29            return;30        }31 32        // Try to place squares of different sizes, largest first for better pruning33        for (int size = Math.min(n - r, m - c); size >= 1; size--) {34            if (canPlace(covered, r, c, size)) {35                place(covered, r, c, size, true);36                dfs(n, m, r, c + size, covered, count + 1);37                place(covered, r, c, size, false); // backtrack38            }39        }40    }41 42    private boolean canPlace(boolean[][] covered, int r, int c, int size) {43        for (int i = 0; i < size; i++) {44            for (int j = 0; j < size; j++) {45                if (covered[r + i][c + j]) {46                    return false;47                }48            }49        }50        return true;51    }52 53    private void place(boolean[][] covered, int r, int c, int size, boolean val) {54        for (int i = 0; i < size; i++) {55            for (int j = 0; j < size; j++) {56                covered[r + i][c + j] = val;57            }58        }59    }60}

• To optimize, we can ensure n >= m by swapping them if necessary. This reduces the width of our state representation.
• The state is represented by a height array of size m, where height[j] is the filled height of column j.
• A global variable ans stores the minimum squares, initialized to n * m.
• A recursive function dfs(height, count) drives the search.
• Pruning: If count >= ans, the function returns.
• Base Case: Find the column c with the minimum height h. If h == n, all columns are full, the rectangle is tiled. Update ans = min(ans, count) and return.
• Recursive Step:
  1. The point (h, c) is the top-left corner of the next available area.
  2. Determine the width w of the continuous flat region at height h starting from column c.
  3. The largest square we can place here is s_max = min(n - h, w).
  4. Iterate through possible square sizes s from s_max down to 1 (trying larger squares first is a good heuristic).
  5. For each s, create a new height profile by updating the heights of columns c to c + s - 1 to h + s.
  6. Make a recursive call: dfs(new_height, count + 1).

The key improvement over the naive approach is the state representation. An array height of size m (the smaller dimension) is used, where height[j] stores the y-coordinate of the highest filled cell in column j. This is often called a 'skyline' representation.

The algorithm works as follows:

1. Find the lowest point in the skyline. This corresponds to the first available empty space. Let's say this is at column c with height h = height[c].
2. From this point, determine how wide of a square we can place. This is limited by the rectangle's boundary and by any adjacent columns that are taller than h.
3. We iterate through all possible square sizes that can be placed at this location, from largest to smallest. Trying larger squares first is a heuristic that helps find a good solution early, which in turn makes the pruning (count >= ans) more effective.
4. For each potential square placement, we update the skyline and recurse. We pass a copy of the height array to the recursive call to avoid manual backtracking.

This approach is powerful because it directly targets the next area to be filled and prunes the search space effectively, making it feasible for the given constraints.

1class Solution {2    int ans;3 4    public int tilingRectangle(int n, int m) {5        if (n == m) {6            return 1;7        }8        // Ensure n is the larger dimension to keep the skyline array smaller.9        if (n < m) {10            int temp = n;11            n = m;12            m = temp;13        }14        ans = n * m; // Upper bound: tiling with 1x1 squares15        int[] height = new int[m];16        dfs(n, m, height, 0);17        return ans;18    }19 20    private void dfs(int n, int m, int[] height, int count) {21        if (count >= ans) {22            return;23        }24 25        // Find the first column that is not full (lowest point on the skyline)26        int minHeight = n;27        int startCol = -1;28        for (int i = 0; i < m; i++) {29            if (height[i] < minHeight) {30                minHeight = height[i];31                startCol = i;32            }33        }34 35        // If all columns are full, we have a complete tiling36        if (startCol == -1) {37            ans = Math.min(ans, count);38            return;39        }40 41        // Find the width of the flat area at minHeight42        int endCol = startCol;43        while (endCol + 1 < m && height[endCol + 1] == minHeight && (endCol - startCol + 1) < (n - minHeight)) {44            endCol++;45        }46        int width = endCol - startCol + 1;47 48        // Try placing squares of different sizes, largest first49        for (int size = Math.min(width, n - minHeight); size >= 1; size--) {50            int[] nextHeight = height.clone();51            for (int i = 0; i < size; i++) {52                nextHeight[startCol + i] += size;53            }54            dfs(n, m, nextHeight, count + 1);55        }56    }57}