# Has anyone ever attempted to find all splits of a rectangle into smaller rectangles?

I'm enamored by the games Unproportional and Unproportional2. The only problem is that they have way too few levels. :)

But, I'm a computer programmer, so I could make my own! With blackjack and hookers the ability to upload custom pictures and randomly generate grids!

Most everything is straightforward there, except for the generation of the grids. How do I take a rectangle and partition it in smaller rectangles? And not only that, I want to be sure that my algorithm can produce ANY possible split within my limitations. (I'll need to add some limitations to make the grids playable. My first idea is to limit the minimum size of rectangle sides, but that will come from playtesting)

Searching for an answer to this I found the CS.SE question "Randomly partition an rectangle into N smaller rectangles". This suggests an algorithm:

1. Take a rectangle
2. Randomly do one of the following:
• Split the rectangle into two rectangles with a line parallel to its sides
• Split the rectangle into this pattern (with randomize sides and possibly mirrored):
3. Take each one of the new rectangles and go to point 1. (Recursion)

It's something. But I had doubts if it could produce ALL possible splits. So I took a look at the games, and sure enough, the first level I clicked already had a split which cannot be produced with the above algorithm:

This also gave me inspiration to produce this split, which I think is a minimal example of another split that cannot be produced by the above algorithm:

OK, so if that doesn't work, what does? It feels to me that a problem like this (partitioning a rectangle into smaller rectangles) is something that should have been explored mathematically, but I don't know where how and what to look for.

So, my question is - is there any mathematical research which, either as its primary focus or as a side effect, has developed an algorithm for enumerating all possible splits of a rectangle into smaller rectangles?

• You may be interested in the squaring the square problem. Instead of creating the arrangement by cutting up a rectangle, it is much easier to think about sweeping a horizontal line from top to bottom over such an arrangement, and about what kind of changes can occur when the sweep crosses the top or bottom edge of a rectangle. Aug 24, 2021 at 10:09
• Aug 24, 2021 at 12:11
• This question has more to do with geometry than topology, so I've edited the tags accordingly. Aug 24, 2021 at 16:46

• @JaapScherphuis In that pattern the top-right rectangle (unrotated) is adjacent to two rectangles on its bottom edge, but $1.5$ rectangles on its left edge. Only integers work for this algorithm so the choice would be forced, and at least one edge must have integer rectangles to avoid overlapping rectangles. It is possible to have both as integers involving a $+$ intersection inside the big rectangle, in which case there may be more than one way to construct the partition - imagine a big square made up of four small squares. Aug 25, 2021 at 17:55