# How to slice an area in rectangles optimally? [duplicate]

Given a contiguous subset of a chessboard (or, more general, a 2d rectangular grid), how can I algorithmically determine a minimal set of rectangles covering the area?

In this example, the "contiguous subset" is the black area, and I am interested in the three red rectangles. There should be no overlap between the rectangles. The relative sizes of the rectangles is not too important; it would be a bonus if the sizes weren't too different.

-

## marked as duplicate by Rahul, Bookend, William, amWhy, Adam HughesSep 3 '14 at 22:28

This question was marked as an exact duplicate of an existing question.

That is a cool picture. – Stefan Smith May 25 '13 at 20:13
So you could extend the single square horizontally to give rectangles of areas 3, 4 and 6 - which would be a "better" solution according to your criteria - and illustrates an issue about obtaining an algorithm - it isn't necessarily best to lop off the bits which protrude. – Mark Bennet May 25 '13 at 21:38
Incidentally, the converse of this question has been explored a fair bit. Googling about 'tiling rectangles with polyominoes' should provide plenty of information about this latter question. – Benjamin Dickman May 26 '13 at 0:47
@StefanSmith Thanks :) I put the SVG source of the pic here, in case you're interested: gist.github.com/andreas-h/5970117 – andreas-h Jul 10 '13 at 20:40
@andreas-h Thanks. It looks like you put a lot of work into it, though I would guess there was some cut-and-pasting involved. – Stefan Smith Jul 20 '13 at 18:35

If an approximate solution is acceptable, you can start with a partition into rectangles (say, all $1\times1$ rectangles), grow those rectangles as much as possible (in random directions), remove or cut them (at random) to have a partition. Iterate many times and keep the best solution. I think a similar algorithm is used to simplify boolean expressions (but overlaps are allowed).