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


Almost Square Packing, Helmut Simonis and Barry O’Sullivan.


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

You could also try using a SAT solver.