# Covering grid with constrained rectangles

I need to place N rects on a 2-dimensional grid with constraints.

For the each rect height/width and placing limitations($x_{min}$-$x_{max}$) are known.

The problem is to place all rects on a grid with no intersections that every rect's bottom left $x$ is in rect's $x_{min}$-$x_{max}$.

I've implemented the naive solution where I just iterating over rects and incrementing $x$ by some fixed step while checking for intersections. If no place found then I increment $y$ and iterate again.

The question: I'm sure that there are algorithms/data structures that will help me to solve this task faster, but I do not know where to start.

I suggest you use a constraint solver, like Minion. The following paper shows that they are effective for a related problem:

My thanks to András Salamon for pointing to this information.

You could also try using a SAT solver.

• Thanks a lot for your answer. Constraint solver really seems like the best option here – somebody32 Jun 7 '14 at 11:30