Randomly partition an rectangle into N smaller rectangles

Question

I'm looking for an algorithm that can partition a rectangle into N smaller rectangles, at random. N will be small (on the order of 5-10 in most cases). It need not be uniformly at random, but at the very least, I'd like to avoid algorithms which completely exclude interesting classes of partitions.

One algorithm I've come across a few times (including a question on Math.SE about the number of ways to do n partitions), is to randomly divide the rectangle in two by drawing an horizontal or vertical line across it, then do the same thing recursively to the resulting smaller rectangles until you get what you want.

The trick here is that although you can get a number of different partitions using this scheme:

There are some ways of dividing a rectangle into smaller rectangles that this method will never produce:

You can easily see that the divide-and-conquer partitioning will never generate the above, because there's no line that could possibly be the first cut, since no single straight line divides the entire square into two smaller rectangles.

So basically I'm looking for an algorithm to randomly divide a rectangle up into N smaller rectangles, where the results meet the following criteria:

• Partitioned into exactly N smaller rectangles
• Everything must actually be a rectangle (no L shapes, etc)
• No empty space left over

The algorithm as a whole should meet the following criteria:

• There is no valid partitioning that the algorithm is incapable of producing
• Can be biased towards certain types of configurations, though the less bias the better.
• Preferably works with integer indices.
• Does not operate by generating all possible partitions and then picking one at random.

I don't care about asymptotic complexity much, because I'll be working with small numbers.