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}