How can I reduce a grid of equal sized squares to a minimum set of rectangles?

Question

If I have an arbitrary sized grid of equal sized squares (with no spacing between them), I need to know an efficient way to reduce these into a minimum number of rectangles, for example if each asterisk represents a square, then this could be reduced to one big rectangle:

*****
*****
*****

While this could be reduced to two rectangles:

  ***             ***
*****   =>  **(1) ***(2)
*****       **    ***
  ***             ***

An obvious solution is to collect adjacent squares in each row, then collect adjacent rows which are identical. For my second example this would find three rectangles, which is not optimal.

  *** (1)

***** (2)
*****

  *** (3)

I am wondering if there's a more successful and efficient algorithm to do this.

Answer 1

I've a gut feeling that this problem can be complex... for example consider

   *
   ***
****
   ***
   *

The optimal solution is 4

   B
   BCC
AAAB
   BDD
   B

but i don't find an easy way to foresee by local reasoning that A should stop before last square. In the optimal solution A, C, and D are non-maximal rectangles and only B is maximal. Things can get even more complex for example with:

   *
   ***
****
   ***
   *
 *****
  * *
  * *

where the optimal solution is

   B
   BCC
AAAB
   BDD
   B
 EEEEE
  F G
  F G

where only E is maximal. Also looks it's actually easy to build arbitrarily large problems where in the optimal solution all but one rectangles are non-maximal. Of course this doesn't mean IMO that no easy solution exists... like I said it's a gut feeling, but IMO any solver that reasons with maximal rectangles is going to have problems if the absolute minimum is needed.

For a somewhat similar but also different problem (I was searching a minimal covering with non-necessarily-disjoint discs) I used a slow greedy approach always adding to the solution the disc that was contained and covering most not-yet-covered squares. For your problem I'd probably see how it works adding the largest contained rectangle every time... that as the examples above show however this is not going to be in general an optimal solution.