Q:

Split grid up into random sized rectangles

I have a 500 x 400px square with a 100px grid inside it. Now I want to fill that square with smaller random sized square that snap to the grid. This means that the smaller squares can be either 100, 200, 300 or 400 pixels in size. Their size and position needs to be random, so the output will look different every time it runs.
This image shows the large square, its grid, and a possible output with the smaller squares that I'm trying to create.

I'm generating this in Ruby / Sinatra with DIV's, but I guess the question is more general towards the actual algorithm to use.
Any suggestions on how to do this with the least amount of code?

A:

This method would take a lot of code, but I think what I would do is using Donald Knuth's Dancing Links algorithm (DLX) (or some other algorithm) to find all possible arrangements of squares.  You can compute the arrangements ahead of time, then you can quickly/randomly pick one later when you need them.
You can read his paper about the algorithm and its application to pentominoes (which is very similar to your problem) here:
http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
http://en.wikipedia.org/wiki/Dancing_Links

