Take the 2-minute tour ×

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.

Image Test

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?

share|improve this question
Given a square, there are a finite number of places to put it. If you're not worried about speed: generate random square size up to some max; get all possible places to put it; randomly choose one and put it. If there are no possible places, decrease the max size. –  Timbits Sep 4 '11 at 3:57

2 Answers 2

up vote 1 down vote accepted

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:



share|improve this answer

One simple recursive approach you could take that would produce a fairly good random distribution works like this: as a base case, any grid that is 100x100 must be filled with a 100x100 square. Otherwise, if the grid is n x n for some n that's small enough to hold a square, you may choose to tile it with a square of that size. Otherwise, pick some side of the rectangle that isn't of size 100, pick some random place that's a multiple of 100, then split it in half and recursively tile both halves.

The main advantage of this approach is that you never have to keep track of where you've put older rectangles to avoid hitting them. You always work with empty rectangles and keep recursively subdividing the problem in a way that ensures that the regions never overlap.

This may not always give good results, but it's very easy to code up (I'd assume maybe 15-25 lines of code total) and can easily be tweaked to change the output.

Hope this helps!

share|improve this answer

Your Answer


