I'm looking for an algorithm to divide a space into the minimal number of rectangular blocks (for example, on the attached picture, dividing the white space into the red rectangles). Doesn't have to be the optimal solution, a good heuristic would suffice. I don't know what problems like this are usually classified or referred to as, so I havn't had much luck searching for it.

Okay here's how you can solve it. Picture the grid as a graph where each cell is a node. Insert all the empty nodes into an array. Now grab the first node and generate all the possible rectangles with it then for each rectangle recursively call the operation again and pass in the remaining nodes. Track the number of rectangles. Could use a branch and bound algorithm.

If you need help generating the rectangles from a single node just ask.

Your function will look like:
FindMinimumNumberOfRectangles(nodes, numberOfRectangles)
{
// Generate rectangles from first node in nodes using the nodes in nodes
for each generated rectangle
{
FindMinimumNumberOfRectangles(nodes-rectangle nodes, numberOfRectangles + 1)
}
}
You start by doing:
FindMinimumNumberOfRectangles(empty nodes, 0)

Looks like a fun project...

Ohh ya, I think the above poster has over-estimated things.