How do you represent a particular squared square uniquely? First, you present it in its canonical orientation, that is, with the biggest corner square at top left and the biggest of the two neighbouring squares on the top edge. That gets rid of rotations and reflections. Then for each horizontal edge in the squared square, starting at the top and running downwards, you list the sizes of the subsquares below that edge from left to right. Where more than one edge are at the same height, you list them from left to right. Finally you prepend the size of whole square. Thus a readable representation (called the Bouwkamp description) of the square used on the front page of this site is
192 (86,49,57)(41,8)(28,37)(19,9)(47,35,4)(31,14)(10,36)(17,26)(12,71)(62)(59)
Of course, the brackets and commas are just visual aids, and a computer will be perfectly happy with
192 86 49 57 41 8 28 37 19 9 47 35 4 31 14 10 36 17 26 12 71 62 59
Now we have a standard way to list1 the squared squares of a given order. Just list the Bouwkamp descriptions in ascending numeric order on the first field (the size), within the same value of the first field on the second, within the same value of the second field on the third and so on. The length of the list grows steadily as the order increases.
How many squared squares are there of a given order?
From the single one of order 21, the count grows somewhat jerkily to order 25, after which it grows in a neatly exponential fashion. There are 441 of order 26 and, as far as 37 at least, each further order has, rounded to one decimal place, 2.6 times as many solutions as its predecessor. So, there are roughty twenty thousand simple perfect squared squares of order 30, and more than seventeen million of order 37. The size of the biggest square in the order grows nothing like as fast. For order 30, it is only 2710, and for order 37, just 20242.
It will be immediately obvious from this that, not only are there a great many squared squares of an order like 37, but there are very many of some particular sizes within that order. Looking at the solutions for 37 in more detail, they begin (like all the other orders) in the low hundreds and advance, somewhat scrappily at first. Soon, most consecutive integers have a solution and from 359 onwards, every single integer up to 17970 is covered, a total of 17612 values. After that, they thin out again to the final value of 20242. Of the 18308 different solution sizes, the consecutive ones make up more than 96% of the total. And within this range, the number of different squared squares for a given size climbs rapidly towards the middle. Size 900 already has more than a thousand and the count reaches a peak at size 3240, which has 4281 different solutions!
How many squared squares are there of a given size?
For the smallest sizes, up to about 200, very few. Funnily enough, the smallest possible size (110) comes in three forms, whereas most of the other small ones have one or two. Once we get to middle-range squares around a thousand or so, it's a very different story; the count becomes enormous and with present techniques, effectively incalculable. Take size 1412, for example. The first four solutions of this size appear at order 29. Then, for increasing orders up to 37, there are 20, 52, 71, 139, 273, 512, 880 and 1659 respectively; that's 3610 so far. Presumably we will find that the counts for 38, 39 etc. rise when these orders have finally been tabulated. The thing is, at least one solution of this size of order 75 was found a long time ago. If, as seems likely, the counts rise for quite a lot of orders after 37, before (possibly) being on a falling trend by 75, the total count of squares of size 1412 might well be in the hundreds of thousands. But just try finding a single one by hand...
Naming and colouring squared squares
Simple perfect squared squares are given identifying names like this: <order>:<size><letter>. "size" is that of the whole construction, and "letter" starts from A to identify those which have the same order and size. Thus the square used for the front page is 22:192A. Where there are more than 26 squares of a given order and size, we continue with AA etc. and where there are more than 676, with AAA.
The four colours used to present the squared squares here are those known to modern browsers as "lightblue", "darkseagreen", "sandybrown" and "palegoldenrod" respectively. As a general rule, the top left-hand square gets colour 1, its immediate neighbour along the top edge gets colour 2, the (unique) square touching both of these, which is commonly not the third square in the Bouwkamp description, gets colour 3. The rest of the squares are assigned one of the four colours according to the particular pattern being tried. As colour 4 is subjectively the brightest one, its absence in the depiction of very rare 3-colourable solutions makes them stand out.
When colouring a squared square for display, it would be nice to have the most equitable colouring, that is, the colouring with the smallest ratio between the areas belonging to the colour with the most area and the colour with the least. That means checking a lot of different2 colourings... no solution has fewer than 1752 colourings, and already by order 31 some have millions. Unless otherwise stated, the squares shown below are coloured as equitably as possible.
The simplest one
The simplest possible squared square is 21:112A, the only one with just 21 squares. Its size of 112 is not the smallest possible, however; there three squared squares of size 110, but with more than 21 component squares.
There are 2483 different ways of colouring this "map" with four colours. The (unique) colouring shown has the most equitable distribution with the biggest colour (brown) having 12.4% more than the smallest (green).
The one with the biggest smallest square
There are a total of 1152 different squared squares of order 27 and five of them are of size 1032. 27:1032E is distinguished by having a freakishly big smallest component square (relative to its overall size). At 48, its side length is nearly 5% of that of the whole solution. This is the biggest such ratio for any squared square below order 38 at least.
This square could be of interest in physical constructions, whenever the technique used involves difficulties in rendering the smallest squares.
There are 28488 different ways of colouring this solution. The (unique) colouring above has the most equitable distribution of colour areas with the biggest colour, orange, having just 0.76% more than the other three, which in turn differ among themselves by barely one part in a thousand. Fewer than one percent of the squares below order 30 can be coloured as evenly as this.
While the downward pressure exerted on square sizes by increasing orders makes it seem plausible that no squared square will ever improve on 27:1032E, one of order 31 comes close: 31:1408A has a smallest square whose side is 4.54% of that of the whole solution, compared with 4.65% for the former.
The one with the smallest biggest square
What about turning the above condition around, and looking for the solution with the smallest biggest square relative to its overall size? This constraint makes for a lot of medium-sized squares, as can be seen in 33:1107A, where the biggest square has a side that is 27.100% of that of the whole solution. 25% represents a kind of barrier here, since below that figure the solution would have to be everywhere at least five squares deep horizontally and vertically, tough to achieve in an order as low as 33.
There are 585744 different ways of colouring this solution. The (unique) colouring shown has the most equitable distribution with the biggest colour (green) having just 1.47% more than the smallest (yellow).
Continuing the search up through the orders, we do get a few slightly better results. The best is S36:5967QQ which achieves 26.228%, but it does not present well, with some tiny squares lost among giants. The next best one is 37:1395BBD, pretty close at 26.237%.
The one with the biggest square
If we are looking for the biggest component square, it is always going to be in a corner, since there it constrains the other squares least. 33:2704EM holds the record below order 34; its humongous corner square takes up more than 45% of the whole area. The colouring is the most equitable possible, but that's not saying much in this case!
With all squared squares up to order 37 tabulated in 2020, we can do better. 37:9717A smashes the fifty per cent barrier, with its corner square taking up more than 51% of the whole area. Here, the colouring doesn't try to be equitable, but has the fewest other squares in light blue.
One needing only three colours
We know that we can colour any squared square with four colours, but what about three? A necessary condition for three-colourability is that all internal squares have an even number of neighbours. (It's also sufficient.) There is no need to run a special search for them; when the colour checker program finds a case without the fourth colour, it attempts a divide by zero when calculating the ratio of colour areas, and politely stores the special value "inf" in the printout instead of crashing. Well, such cases are remarkably rare. We have processed 145786 solutions when we finally find the first one, 32:1776A, and there is only one other to the end of order 33, a grand total of more than 610,000 solutions.
That is, of course, small beer when we are able to extend the search to cover all orders up to 37, for a grand total now of just under 28,000,000 solutions. As it happens, there are no three-colourable squares at all in order 34, but there are three of order 35, two of order 36 and just one in the seventeen million or so solutions of order 37. Most of them have some inconveniently small component squares and do not display well. The best of the bunch is 35:5704AFR, which certainly presents better than the order 32 one above.
Big brother and little brother
As a slightly different kind of problem, we can ask if there is a squared square of order N which is "little brother" to one of order N+1 in the sense that the bigger one consists of all of little brother's squares, plus its extra one. This is clearly a fairly difficult constraint to satisfy, given that the little brother's squares will have to be in quite a different pattern; maybe it is even impossible? We can run a search over all twenty-eight million or so fully tabulated squares up to the end of order 37 to see if we can find such pairs.
And when we do, the slightly surprising result is that, in all this huge number of squared squares, we find just one pair. Little brother is 36:800ES and big brother is 37:1000K. See them side-by-side here; a screen width of at least 1920 pixels is required to avoid scroll bars.
When we look at how little brother's squares were reassembled, we find that they didn't have to rearrange themselves that much at all. They group into five pieces, three single squares, one clump of eleven and one of twenty-two. The smaller clump is flipped across a diagonal, and the bigger one is rotated through ninety degrees, after which the pieces can be placed to form an L-shape around the (biggish) extra square. To make the rearrangement clear, the pieces are shown in their own individual colours here.
