Fitting a square grid with non-overlapping rectangles

81 Views Asked by At

Let R be a list of rectangles Ri with integer height h and width w.

What are all the possible positions of these rectangles and their 90 degree rotations on a NxN square grid (N <= 64) without overlaps? Every rectangle Ri can and must be placed only once, but there can be duplicates in the list R. (You could also say each rectangle has to be placed mi times, where mi is a natural number bigger than 0, so no duplicates in set R)

For example

Let R = {{1, 2}, {1, 1}}.

And a 2x2 square grid:

0 0
0 0

We can fit the rectangles in the following way, where 'a' represents the first rectangle and 'b' the second rectangle:

b a    0 b     a 0    a a    
0 a    a a     a b    0 b    

0 a    b 0     a b    a a    
b a    a a     a 0    b 0    

The bigger picture is finding the best tiling in respect to a metric. I'm still thinking about the exact metric, its about the distance between some of the edges of the rectangles. I thought spanning the solution space would be a good start for some algorithm, greedy search or neural net etc.

0

There are 0 best solutions below