minimum number of rectangular regions to fill a grid

Question

Suppose we have a grid and we want to paint rectangular regions on it using the smallest number of colors possible, one for each region.

There are some cells that are already painted black and cannot be painted over:

Is there a polynomial algorithm to solve this problem?

After testing, I found out that the solution for this case is 9 (because we need 9 different colors to paint the minimum number of regions to fill the whole grid):

---

The greedy approach seems to work well: just search for the rectangle with biggest (white) area and paint it, repeating this until there's nothing else to be painted, but I didn't measure the complexity or the correctness.

Answer 1

Here are a few observations that can simplify this problem in specific cases. First of all, adjacent identical rows and columns can be reduced to one row or column without changing the required number of regions, to form a simplified grid:

A simplified grid where no row or column is divided into more than two uncoloured parts (i.e. has two or more seperate black cells), has an optimal solution which can be found by using the rows or columns as regions (depending on whether the width or height of the grid is greater):

The number of regions is then minimum(width, height) + number of black cells.

If a border row or column in a simplified grid contains no black cells, then using it as a region is always the optimal solution; adding some parts of it to other regions would require at least one additional region to be made in the border row or column (depending on the number of black cells in the adjacent row or column):

This means that the grid can be further simplified by removing border rows and columns with no black cells, and adding the number of removed regions to the region count:

Similarly, if one or more border cells are isolated by a black cell in the adjacent row or column, all the connected uncoloured neighbouring cells can be regarded as one region:

At each point you can go back to previous rules; e.g. after the right- and left-most columns have been turned into regions in the example above, we are left with the grid below, which can be simplified with the first rule, because the bottom two rows are identical:

Collapsing identical adjacent rows or columns can also be applied locally to isolated parts of the grid. The example below has no identical adjacent rows, but the center part is isolated, so there rows 3 to 6 can be collapsed:

And on the left row 3 and 4 can be collapsed locally, and on the right rows 5 and 6, so we end up with the situation in the third image above. These collapsed cells then act as one.

---

Once you can't find any further simplifications using the rules above, and you want to check every possible division of (part of) a grid, a first step could be to list the maximum rectangle sizes that can be made with the corresponding cell as their top left corner; for the simplified 6x7 grid in the first example above that would be:

        COL.1            COL.2       COL.3       COL.4       COL.5  COL.6

ROW 1   [6x1, 3x3, 1x7]  [5x1, 2x3]  [4x1, 1x7]  [3x1]       [2x5]  [1x7]
ROW 2   [3x2, 1x6]       [2x2]       [1x6]       []          [2x4]  [1x6]
ROW 3   [6x1, 1x5]       [5x1]       [4x3, 2x5]  [3x3, 1x5]  [2x3]  [1x5]
ROW 4   [1x4]            []          [4x2, 2x4]  [3x2, 1x4]  [2x2]  [1x4]
ROW 5   [6x1, 4x3]       [5x1, 3x3]  [4x1, 2x3]  [3x1, 1x3]  [2x1]  [1x3]
ROW 6   [4x2]            [3x2]       [2x2]       [1x2]       []     [1x2]
ROW 7   [6x1]            [5x1]       [4x1]       [3x1]       [2x1]  [1x1]

You can then use these maximum sizes to generate every option for each cell; e.g. for cell (1,1) they would be:

6x1, 5x1, 4x1, 3x3, 3x2, 3x1, 2x3, 2x2, 2x1, 1x7, 1x6, 1x5, 1x4, 1x3, 1x2, 1x1

(Some rectangle sizes in the list can be skipped; e.g. it never makes sense to use the 3x1-sized region without adding the fourth isolated cell to get 4x1.)

After choosing an option, you would skip the cells which are covered by the rectangle you've chosen and try each option for the next cell, and so on...

Running this on large grids will lead to huge numbers op options. However, at each point you can go back to checking whether the simplification rules can help.

---

To see that a greedy algorithm, which selects the largest rectangles first, cannot guarantee an optimal solution, consider the example below. Selecting the 2x2 square in the middle would lead to a solution with 5 regions, while several solutions with only 4 regions exist.