# Tiling a Rectangle with the Fewest Squares
**Difficulty:** HARD
[External](https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares)
Canonical: https://scaleengineer.com/dsa/problems/tiling-a-rectangle-with-the-fewest-squares
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
---
## Problem
Given a rectangle of size `n` x `m`, return _the minimum number of integer-sided squares that tile the rectangle_.

**Example 1:**

![](https://assets.glich.co/dsa/tiling-a-rectangle-with-the-fewest-squares/image0.png)

**Input:** n = 2, m = 3
**Output:** 3
**Explanation:** `3` squares are necessary to cover the rectangle.
`2` (squares of `1x1`)
`1` (square of `2x2`)

**Example 2:**

![](https://assets.glich.co/dsa/tiling-a-rectangle-with-the-fewest-squares/image1.png)

**Input:** n = 5, m = 8
**Output:** 5

**Example 3:**

![](https://assets.glich.co/dsa/tiling-a-rectangle-with-the-fewest-squares/image2.png)

**Input:** n = 11, m = 13
**Output:** 6

**Constraints:**

* `1 <= n, m <= 13`

# Approaches
## Naive Backtracking
This approach uses a straightforward backtracking algorithm to explore all possible ways of tiling the rectangle. It uses a 2D grid to keep track of covered cells and recursively tries to place squares in the first available empty spot. While simple to understand, its brute-force nature makes it highly inefficient.
**Time:** Exponential. The search space is vast, related to the number of ways to tile a grid. Without effective pruning, the complexity is prohibitive. This approach is too slow for the given constraints. · **Space:** O(n * m) to store the `covered` grid. The recursion stack depth also adds to the space, but it's dominated by the grid.
**Pros:** Guarantees finding the optimal solution.; Relatively easy to conceptualize and implement.
**Cons:** Extremely inefficient due to the large state representation (`n*m` grid).; The process of finding the next available cell and checking for valid placement is slow.; Very likely to cause a 'Time Limit Exceeded' error for most inputs within the given constraints.
### Explanation
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.

```java
class Solution {
    int ans;

    public int tilingRectangle(int n, int m) {
        if (n == m) return 1;
        ans = n * m;
        boolean[][] covered = new boolean[n][m];
        dfs(n, m, 0, 0, covered, 0);
        return ans;
    }

    private void dfs(int n, int m, int r, int c, boolean[][] covered, int count) {
        if (count >= ans) {
            return;
        }

        // Find the first uncovered cell, starting from (r, c)
        while (r < n && covered[r][c]) {
            c++;
            if (c == m) {
                r++;
                c = 0;
            }
        }

        // If all cells are covered, we found a solution
        if (r == n) {
            ans = Math.min(ans, count);
            return;
        }

        // Try to place squares of different sizes, largest first for better pruning
        for (int size = Math.min(n - r, m - c); size >= 1; size--) {
            if (canPlace(covered, r, c, size)) {
                place(covered, r, c, size, true);
                dfs(n, m, r, c + size, covered, count + 1);
                place(covered, r, c, size, false); // backtrack
            }
        }
    }

    private boolean canPlace(boolean[][] covered, int r, int c, int size) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (covered[r + i][c + j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private void place(boolean[][] covered, int r, int c, int size, boolean val) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                covered[r + i][c + j] = val;
            }
        }
    }
}
```
### Algorithm
- 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`.

## Backtracking with Skyline Pruning
This is a more optimized backtracking approach that uses a 'skyline' heuristic to represent the state of the tiling. Instead of a full 2D grid, we only keep track of the height of the tiled area in each column. This significantly reduces the state space and makes finding the next placement location much more efficient. Combined with aggressive pruning, this method is capable of solving the problem within the given constraints.
**Time:** Exponential, but significantly pruned. The number of reachable states is much smaller than the theoretical maximum of `O((n+1)^m)`. The exact complexity is hard to analyze but is efficient enough to pass the given constraints. · **Space:** O(k * m), where `k` is the maximum recursion depth (number of squares) and `m` is the smaller dimension of the rectangle. A new `height` array of size `m` is created at each recursion level.
**Pros:** Guaranteed to find the optimal solution.; Significantly more efficient than naive backtracking due to a compact state representation and targeted search.; Feasible for the given constraints (`n, m <= 13`).
**Cons:** The time complexity is still exponential, though much better than the naive approach.; The logic is more complex to implement correctly compared to the naive grid-based backtracking.
### Explanation
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.

```java
class Solution {
    int ans;

    public int tilingRectangle(int n, int m) {
        if (n == m) {
            return 1;
        }
        // Ensure n is the larger dimension to keep the skyline array smaller.
        if (n < m) {
            int temp = n;
            n = m;
            m = temp;
        }
        ans = n * m; // Upper bound: tiling with 1x1 squares
        int[] height = new int[m];
        dfs(n, m, height, 0);
        return ans;
    }

    private void dfs(int n, int m, int[] height, int count) {
        if (count >= ans) {
            return;
        }

        // Find the first column that is not full (lowest point on the skyline)
        int minHeight = n;
        int startCol = -1;
        for (int i = 0; i < m; i++) {
            if (height[i] < minHeight) {
                minHeight = height[i];
                startCol = i;
            }
        }

        // If all columns are full, we have a complete tiling
        if (startCol == -1) {
            ans = Math.min(ans, count);
            return;
        }

        // Find the width of the flat area at minHeight
        int endCol = startCol;
        while (endCol + 1 < m && height[endCol + 1] == minHeight && (endCol - startCol + 1) < (n - minHeight)) {
            endCol++;
        }
        int width = endCol - startCol + 1;

        // Try placing squares of different sizes, largest first
        for (int size = Math.min(width, n - minHeight); size >= 1; size--) {
            int[] nextHeight = height.clone();
            for (int i = 0; i < size; i++) {
                nextHeight[startCol + i] += size;
            }
            dfs(n, m, nextHeight, count + 1);
        }
    }
}
```
### Algorithm
- 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)`.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int m;
private
  int[] filled;
private
  int ans;
public
  int tilingRectangle(int n, int m) {
    this.n = n;
    this.m = m;
    ans = n * m;
    filled = new int[n];
    dfs(0, 0, 0);
    return ans;
  }
private
  void dfs(int i, int j, int t) {
    if (j == m) {
      ++i;
      j = 0;
    }
    if (i == n) {
      ans = t;
      return;
    }
    if ((filled[i] >> j & 1) == 1) {
      dfs(i, j + 1, t);
    } else if (t + 1 < ans) {
      int r = 0, c = 0;
      for (int k = i; k < n; ++k) {
        if ((filled[k] >> j & 1) == 1) {
          break;
        }
        ++r;
      }
      for (int k = j; k < m; ++k) {
        if ((filled[i] >> k & 1) == 1) {
          break;
        }
        ++c;
      }
      int mx = Math.min(r, c);
      for (int w = 1; w <= mx; ++w) {
        for (int k = 0; k < w; ++k) {
          filled[i + w - 1] |= 1 << (j + k);
          filled[i + k] |= 1 << (j + w - 1);
        }
        dfs(i, j + w, t + 1);
      }
      for (int x = i; x < i + mx; ++x) {
        for (int y = j; y < j + mx; ++y) {
          filled[x] ^= 1 << y;
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int tilingRectangle(int n, int m) {
    memset(filled, 0, sizeof(filled));
    this->n = n;
    this->m = m;
    ans = n * m;
    dfs(0, 0, 0);
    return ans;
  }

private:
  int filled[13];
  int n, m;
  int ans;
  void dfs(int i, int j, int t) {
    if (j == m) {
      ++i;
      j = 0;
    }
    if (i == n) {
      ans = t;
      return;
    }
    if (filled[i] >> j & 1) {
      dfs(i, j + 1, t);
    } else if (t + 1 < ans) {
      int r = 0, c = 0;
      for (int k = i; k < n; ++k) {
        if (filled[k] >> j & 1) {
          break;
        }
        ++r;
      }
      for (int k = j; k < m; ++k) {
        if (filled[i] >> k & 1) {
          break;
        }
        ++c;
      }
      int mx = min(r, c);
      for (int w = 1; w <= mx; ++w) {
        for (int k = 0; k < w; ++k) {
          filled[i + w - 1] |= 1 << (j + k);
          filled[i + k] |= 1 << (j + w - 1);
        }
        dfs(i, j + w, t + 1);
      }
      for (int x = i; x < i + mx; ++x) {
        for (int y = j; y < j + mx; ++y) {
          filled[x] ^= 1 << y;
        }
      }
    }
  }
};

```

### Python

```python
class Solution:
    def tilingRectangle(self, n: int, m: int) -> int: def dfs(i: int, j: int, t: int): nonlocal ans if j == m: i += 1 j = 0 if i == n: ans = t return if filled[i] >> j & 1: dfs(i, j + 1, t) elif t + 1 < ans: r = c = 0 for k in range(i, n): if filled[k] >> j & 1: break r += 1 for k in range(j, m): if filled[i] >> k & 1: break c += 1 mx = r if r < c else c for w in range(1, mx + 1): for k in range(w): filled[i + w - 1] |= 1 << (j + k) filled[i + k] |= 1 << (j + w - 1) dfs(i, j + w, t + 1) for x in range(i, i + mx): for y in range(j, j + mx): filled[x] ^= 1 << y ans = n * m filled = [0] * n dfs(0, 0, 0) return ans

```