# Packing rectangles in a grid

I have a problem that, discovered today, may be called "rectangle packing". I found extremely interesting references to papers in this question.

But the rectangles I want to pack have dimensions that are based on grid cells and must fit an evenly spaced grid. That means, rectangle widths and heights are multiples of an evenly spaced grid cell.

So, let's say that we have a 5x5 grid:

+----+----+----+----+----+
|    |    |    |    |    |
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
|    |    |    |    |    |
+----+----+----+----+----+


Packing it with the following rectangles:

• 3x3 (1)
• 2x2 (3)
• 1x1 (3)

...can possibly result in:

+----+----+----+----+----+
|           3x3|      2x2|
|              |         |
+              +         +
|              |         |
|              |         |
+              +----+----+
|              | 1x1| 1x1|
|              |    |    |
+----+----+----+----+----+
|      2x2|      2x2| 1x1|
|         |         |    |
+         +         +----+
|         |         |    |
|         |         |    |
+----+----+----+----+----+


...leaving one empty grid cell. Other solutions exist and some invalid ones too.

Which algorithm should I use to accomplish this? I am wondering if, given the rectangle dimensions and grid constraints, this would be much simpler than packing an arbitrarily-sized rectangle with others of equally arbitrary dimensions.

-
Even the one dimensional bin packing problem is known to be NP-hard. Two dimensions can't make it easier, and three is like packing a car with suitcases, which we all know to be very difficult. –  Ross Millikan Jul 16 '13 at 18:05
There are good heuristics for packing a car with suitcases. (I don't know what these are, but my father does. I've seen him do it.) –  Michael Lugo Jul 16 '13 at 18:08
Yep, I'm looking for a hint about heuristics. The grid and dimension constraints seem to make the problem just a bit easier than general 2D packing, though. –  moraes Jul 16 '13 at 18:19
I once wrote some programs for grid packing of polyominoes; your problem is a special case of this. It's not sophisticated, but it does work, and for small grids, like your example, it is fast enough to use. Even on an ancient, slow computer, it finds all 4608 solutions to your problem above in about 30 seconds. Feel free to email me for details. –  MJD Jul 16 '13 at 18:26
Source code and complete output for this problem. Note that the program distinguishes the three 2×2 tiles and the three 1×1 tiles, so each solution is repeated nine times; there are actually only 512 distinct solutions. –  MJD Jul 16 '13 at 18:39
show 3 more comments