Block layout algorithm

This (polyomino shape-packing) generally seems to be a nontrivial math problem, and I'll point you to the expertise of some others who have worked on it. This guy has a bunch of polyomino examples on his website where others can submit solutions. He also has solver software in Java:

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html.

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

There are also some algorithms written for this by Stephen Montgomery-Smith, which seem to be more comprehensive than the above (it solved some problems that weren't solvable with that) eventually made it into an xscreensaver (solves in real-time and cool to watch!). The following screenshot, from the screensaver, only shows shapes up to pentominoes, but it works on general shapes with general containers.

http://www.math.missouri.edu/~stephen/software/

I am unsure if either of these software approximates the best fit of polyominoes allowing for holes. But it's definitely 'decidable' this way, in the sense that you could certainly insert extra 1x1 polyominoes into your solution and see if it can find a particular result that fits, then remove the 1x1 pieces to get the result.

For your application, it might be more efficient to work backwards. All of these algorithms have complexity in the number of unit cells in each block. A good way to lay out your blocks would be to think of them as "subdivisions" in larger cells, so that a 3x3 square in your block corresponds to a 1x1 square in a rescaled version. Then, pad the blocks with empty space so they all consist of the larger blocks, run the algorithm, and strip away the extra space. Not only will this be much faster to execute, but it will also generate the space between blocks that you require.