ianhenderson.org / 2023 february 2

cutting squares into similar rectangles using a computer program

background

on december 14, @johncarlosbaez asked the question -- how many ways are there to cut a square into four similar rectangles? "similar" meaning, in its mathematical sense, having the same ratio between two perpendicular sides (for example, a 50" television screen and a 80" television screen are similar as long as they have the same 16:9 aspect ratio). and we only care about this ratio -- two different ways of cutting a square are still considered the same if their rectangular pieces have the same aspect ratio.

eventually eleven distinct ratios were found, as visualized by @Danpiker here:

the process of finding these eleven was somewhat ad-hoc, though, and could be hard to continue past four. i realized there was a way to generate them using a computer program, and worked through the details until i was able to generate dissections of a square into not just four, but five, six, and seven similar rectangles. since there seems to be some interest in this, i figured i'd do a writeup to explain how the program works. the source code is here, if you want to follow along.

there are five high-level steps in the program:

1. generating grid-aligned arrangements
2. writing the aspect-ratio constraint on each arrangement as a system of equations
3. solving the system of equations to produce a single polynomial representing the constraint
4. finding the roots of this polynomial and back-substituting to verify that the roots produce a valid dissection
5. rendering the dissection for each root

i'll discuss each step in the following sections.

generating grid-aligned arrangements

the first step is to find all the ways for rectangles to fit together in a square, ignoring their widths and heights.

let N be the number of rectangles we're cutting the square into. what i'll call a "grid-aligned arrangement" (or just an arrangement) is an NxN grid with each of its grid cells colored using one of N different colors.

every way of cutting a square into N rectangles can be grid-aligned like this. to see why, consider the horizontal lines touching the tops of each rectangle. there are M ≤ N distinct such lines, and one of those lines is the top line of the square itself.

each of the remaining M-1 lines can be moved to meet one of the N-1 horizontal lines separating the grid cells by adjusting the heights of the rectangles.

once the horizontal lines are in place, do the same thing with the vertical lines by adjusting the widths of the rectangles. in this way you can convert any dissection into a grid-aligned arrangement.

since distinct lines are moved to distinct lines, grid alignment is invertible -- you can go back from the grid to the dissection by moving the lines back to where they started.

problem 1: grids aren't canonical

note, however, that multiple grids can correspond to the same dissection. for example, figure 2 can be grid-aligned to produce figure 1, but grid-aligned in a different way to produce figure 4.

to fix this issue, we'll make a rule that all grid-aligned arrangements must follow.

rule one: if a row repeats, it must be the bottommost row; if a column repeats, it must be the rightmost column.

that is, figure 1 is a valid grid-aligned arrangement, but figure 4 isn't. there's only one way to grid-align a dissection while obeying this rule: align the first horizontal line with the first grid line, the second horizontal line with the second grid line, and so on (then do the same thing with the vertical lines). once you run out of horizontal (and vertical) lines in the dissection, the final row (and final column) will repeat.

problem 2: grids aren't always just rectangles

by changing the sizes of the N rectangles in different grid-aligned arrangements, we can obtain all the different ways of cutting a square into rectangles. but not every grid-aligned arrangement, as we've defined it so far, necessarily contains N rectangles to resize.

to guarantee that the grid contains exactly N rectangles, each with a distinct color, we'll add three more rules for grid-aligned arrangements.

rule two: each colored region must be contiguous.

that is, if there are two cells of the same color, there has to be a path, traveling horizontally and/or vertically between cells of that color, that connects them.

rule three: the 2x2 "L" subgrid is forbidden.

the following 2x2 subgrid (in all its rotated forms) can't appear anywhere in the grid:

to see why the lack of this subgrid guarantees only rectangles, look at the grid row by row. if you slice off a row from a grid containing only rectangles, you get another grid containing only rectangles. this means you can build up all such grids row-by-row, making sure that the grid still contains only rectangles after adding each row.

any grid with only a single row contains only rectangles. to extend a grid containing only rectangles by one row, the colors of each rectangle can either continue straight downward, filling the same horizontal extent in the next row as they did in the previous row, or stop, having no horizontal extent at all in the next row.

the only way to turn a rectangle into a non-rectangle is for a color to continue to the next row, but with a different extent than it had on the previous row. since each colored region is contiguous (rule two), if the color "a" continues to the next row, there must be at least one 1x2 "aa" subgrid:

but for the horizontal extent to have changed, there must be at least one 1x2 "ab" subgrid:

since the color "a" must be contiguous (and, in the previous row, contiguous on that row), all these subgrids must be contiguous as well; in particular, there's a place where an "aa" subgrid touches an "ab" subgrid, producing the 2x2 forbidden subgrid of figure 6.

rule four: all N colors must appear somewhere in the grid.

this rule guarantees there are actually N rectangles in the arrangement.

with these four rules, we can finally say that all grid-aligned arrangements contain exactly N rectangles, that each rectangle is colored using a different color, and that these arrangements correspond to all the ways for N rectangles to fit together in a square.

efficiently generating grid-aligned arrangements

a simple way to generate grid-aligned arrangements is to generate each N-coloring of an NxN grid, then reject colorings that fail to obey the rules. this quickly becomes slow as N gets larger. a more efficient way is to check the rules locally while generating each coloring. the details of the process for doing this are kind of tedious, so you can check the code if you're interested.

writing the aspect-ratio constraint on each arrangement as a system of equations

so, every dissection can be produced from a grid-aligned arrangement by resizing the rectangles. the question now is -- how can we resize the rectangles so they all have the same aspect ratio?

if x is the aspect ratio shared by all the rectangles in a dissection, that means each rectangle R_i has side lengths of a_i and a_ix, where a_i is its longer side length. i'll call this longer side length the "scale" of the rectangle.

each rectangle can be wide or tall

to find all the ways to resize the rectangles, we have to try both orientations for each rectangle.

for N rectangles, there are 2^N distinct orientations to try. (we can cut this number in half, to 2^N-1, by noticing that flipping all the rectangles is equivalent to flipping the entire arrangement -- and that the arrangement-generating procedure will also produce that flipped arrangement.)

generating systems of equations

after choosing an orientation for each rectangle, the next step is to produce a system of equations which the aspect ratio x must satisfy. there are different ways to do this -- i'll talk about two here, since i ended up implementing both (due to a potential issue with the first one i'll discuss). the published source code uses the first method, which runs faster, generates lower-degree polynomials during gaussian elimination, and is somewhat simpler overall.

the first way: solving for the scale of each rectangle directly

let the width and height of the square be 1. then the sum of the widths of the rectangles that appear in each row is equal to 1, and the sum of the heights of the rectangles that appear in each column is also equal to 1.

take the grid from figure 1, for example. if every rectangle is oriented in the "wide" direction, the equations for each row and column are as shown in figure 10.

once we have this system of equations, we can solve for the aspect ratio x and rectangle scales a_i directly.

the second way: solving for the locations of the grid lines

you can also look at the width and height of rectangles as relationships between the horizontal and vertical grid lines.

setting h₀ = v₀ = 0 and h_N = v_N = 1, we can solve for x to find the aspect ratio. then we can solve for the rest of the h_i and v_i to find the horizontal and vertical offsets of the grid lines.

solving the system of equations to produce a single polynomial representing the constraint

since these systems of equations are linear in the rectangle scales a_i (or in the grid line offsets h_i and v_i, though we'll set that approach aside for now), the coefficients can be written as a matrix.

the matrix in table 1 is somewhat unusual, since the entries are polynomials in x, but you can still use gaussian elimination on it. to avoid dealing with fractions, we cross-multiply instead of dividing by the leading coefficient. after cross-multiplying and subtracting, common integer factors are divided out, and any extra powers of x are removed (since we only care about solutions where x ≠ 0). for example, a row with entries

would be reduced to

by dividing by 2x. this could probably be improved by computing a polynomial gcd before cross-multiplying, but i didn't get around to doing that.

if everything works out, gaussian elimination should reduce the matrix until there's a row containing a single polynomial in the last column.

from table 2, we can already see that the aspect ratio that works for this particular orientation and arrangement is 3/5.

what if gaussian elimination doesn't produce a single polynomial in the last column?

this is the problem i mentioned earlier with the first way of producing a system of equations.

when four corners meet at a point, like in figure 13, gaussian elimination can result in a matrix that doesn't have a polynomial in the last column by itself.

this seems to suggest that any solution to a₃(1 − x⁴) = 1 − x + x² − x³ would work as a valid scale and aspect ratio. the issue is that there's nothing constraining the four corners to meet at the same point -- there actually are valid solutions that look like figure 14 (a whole continuum of them).

the code handles this by just skipping any oriented arrangement whose system of equations doesn't produce a single polynomial in the last column. this seems pretty dubious, but checking the number of aspect ratios against the second way of generating equations (solving for grid lines), which doesn't ever encounter this situation, you still get the same number in the end.

i suspect that for every arrangement with this problem, there's another arrangement that's able to produce the same dissections without the problematic solutions. but i don't have a proof or anything.

note that the same problem can happen even if the four corners don't actually meet in a point. the bad solutions for the arrangement in figure 16 don't even produce a consistent horizontal extent for rectangle 1 -- the top ends up at a different location than the bottom. yikes!

finding the roots of this polynomial and back-substituting to verify that the roots produce a valid dissection

anyway, at this point, we have applied gaussian elimination to the matrix for our system of equations, and we have a row containing only a polynomial p(x) in the last column. this means that, to satisfy the system of equations, x must be chosen such that p(x) = 0. in other words, the the roots of p are the potential aspect ratios x for the oriented arrangement.

to find the roots, we use @fredrikj's excellent calcium library. for each root, we verify that it's a real root in the interval (0, 1]. if so, we try substituting it back into the system of equations to obtain the values for the rectangle scales a_i.

if the root is valid, and if all of the a_i are greater than 0, then we add the root to a list with its associated arrangement and orientation. after gathering all the roots into this list, the list is sorted, and any duplicate roots are removed. the remaining roots are the distinct aspect ratios.

rendering the dissection for each root

the actual rendering is done using the html <canvas> element -- here's the page that does it. to get the data into the page, it's written to a json file. for each aspect ratio, the json file describes the orientation, scale, and position of the N rectangles.

conclusion and future directions

the natural next question is -- how far can you go with this? i've actually gotten to eight (images: 1 2 3 4 5 6), though i haven't double-checked with the grid line system-of-equations generating method to make sure the number (8506 8522) is correct. going further will probably require a better polynomial representation than what i'm using. tbh, you could probably get to nine just by using calcium's ca_poly_t type throughout. more ways to filter out arrangements to avoid generating so many duplicate polynomials and roots would also be helpful.

i'd also love to know if solving for the rectangle scales directly is actually valid. it does seem to generate the right numbers (or at least, the same numbers as solving for the grid line offsets), but the fact that some arrangements have to be skipped is a bit worrisome. it would be nice to have a convincing argument that skipping these arrangements isn't actually a problem.

anyway, let me know if you end up pursuing any of this, or if you have any corrections or comments whatsoever. i'm not terribly interested in pushing this any further myself, but i'm happy to add links here to your efforts if you do!

updated 2023 march 6: David Gerbet found an aspect ratio i missed -- the issue was with an assumption i made involving symmetry that turned out not to be true. i've updated the code to fix the bug, as well as the image for seven rectangles.