Squares Part 2: This time it's Octominoes

(Part 1 is here, I'd recommend reading it first.)

After making the heptomino constructions in the above post, octominoes seemed like the logical next step. And we are spoiled for choice when it comes to which size squares we can make from them.

Firstly for solid squares with no centre hole, n² for when n is a multiple of 4, so we can construct 4x4, 8x8, 12x12 and so on. Great stuff. But it gets even better..! Through some happy coincidence of mathematics it turns out that for all odd n, n²-1 is divisible by 8. This means we can fill any odd edge-length square with octominoes as long as we give it a one-cell central hole. In fact, the only sizes we can't theoretically do are the squares with edge lengths even but not a multiple of 4: 2x2, 6x6, 10x10 etc. (Oh, and really tiny squares like 1x1 which are too small to do anything with. I guess in a strange way, the 1x1 square is just zero octominoes around a central hole so it sort of counts, but it's a weird edge case.)

Next step - pick a bunch of these squares whose total area is 2952. There are many ways of doing this; I picked one that included as many different sizes of square as possible. One of each possible size from 3x3 all the way up to 21x21, and then a second 12x12 and 13x13 in order to make the numbers work.

The 3x3 was easy enough to solve, but it was all downhill from there...

This took all afternoon and long into the evening to solve by hand. Early on the most challenging part was digging through the box of octominoes to find the specific bit I needed - my set are made of fluorescent acrylic so I can shine a UV torch into the box to make the edges stand out a bit better, but it's still infuriating digging through three-hundred-and-odd near identical pieces looking for a specific one. Especially when it turns out the piece I'm after has already been used up.

But by the time I was down to the last three squares (the three largest; I did them in ascending size order because doing one of the tiny ones last just sounded utterly horrifying) I was faced with a different problem. The thing with solving lots of separate squares is that there's lots of edges - way more than just solving one large rectangle. And the boundary between solution and empty space demands a higher proportion of straight-edged pieces. And pieces capable of filling 2, 3 and 4 cell deep indentations right at the edge of the construction.

Stuff like this.

Early on this wasn't much of a problem, but the further I progressed the less pieces I had remaining capable of plugging a hole like this. On the very last square I totally ran out and had to just build really carefully so as to not create a hole like this at the edge. And I managed - just.

The other tough bit was each time I finished off a square. Even with all the forward planning in the world, you don't seem to get a lot of say in what the space left for the last 2 or 3 pieces in a square looks like. And although sometimes you can partition it up without using an already-used piece or a nice piece with a 2x2 block in it, most times you've just got to take one for the team and sacrifice a potentially useful late game piece. It hurts, but there's no other way. And with octominoes, there's so many pieces with 2x2 blocks you can afford to use up one or two (or ten) prematurely along the way. Having to spend the big P-shaped piece in the top-right of the 19x19 square though... that wasn't fun.

So yeah, other related challenges. For the reader of course, because on completing this I swore off touching another octomino for at least a week.

• My construction is 17 squares total. Can anyone improve on that? (As in: more, smaller squares.)
• My construction has 15 distinct sizes of square. Is there a way to increase that, to take those duplicated 12x12 and 13x13 squares and somehow use that area to introduce another variety in there?
  

Squares

This has bound to have been done before, it seems too obvious a thing not to. But rediscovery or not I'm going to write about it at length anyway and nobody can stop me.

Imagine this: squares, right, but made out of polyominoes. Gripping stuff, eh?

Pentominoes

With tetrominoes and below you can't really do a lot, for all the usual reasons. Tetrominoes have got parity imbalance, triominoes and dominoes are just tiny sets you can't do a lot with, and while I suppose you can make a 1x1 square out of the set of monominoes (all one of them) it's not the most interesting thing in the world so we'll jump ahead to where it starts to get interesting.

One set of pentominoes can pack a 5x5 square and a 6x6 square simultaneously, if you don't mind an off-centre hole in the 6x6 to bring its total area down to 35. Shown above is one way of doing this, but there are at least 2 more, not counting rotations and reflections as distinct solution. Sadly there is no combination of squares without holes that the pentominoes can fill, just because 60 can't be partitioned into square numbers divisible by 5.

Hexominoes

This lot are frustrating due to the usual parity constraints but nevertheless we'll give it a go. Square sizes permitted are 6² = 36 and 12² = 144 for solid squares, and 5² = 24+1, 7² = 48+1, 11² = 120+1, 13² = 168+1 if you want to allow a square with one solitary central hole. Which feels like bending the rules but alleviates parity issues somewhat, and will be needed for heptominoes and above where we've got pieces with holes whether we like it or not.

Making 210 with a combination of the above squares is our next problem. Each of the above squares would contain an even number of hexominoes, meaning that no combination of them would ever contain exactly 35 hexominoes. Damn.

One avenue to explore is to allow duplication of one of the hexominoes, bringing the set size up to 36 and total area to 216. This can be broken into squares, the most obvious partition being six 6x6 squares. This is... difficult. I've tried it by hand, I've tried running various software to find a solution, no luck so far. All I know is that for this to work the duplicated hexomino must be one of the ones with 2-4 parity imbalance. And that it's possible to solve six 6x6s for the set of hexominoes plus triominoes. So if solutions do exist, they look to be pretty few and far between.

But there are other ways of making 216 from the above numbers. 6² + 6² + 12² works, as does 7² + 13² with a central hole in each. The duplicated hexomino in each case is shown in a different colour (again, the duplicate must be one of the 11 pieces with unbalanced parity.)

6² + 6² + 12² = 216

 

7² + 13² = 216 + 2

As a general rule, the more squares and the smaller the squares are, the harder it is to find a solution.

5² + 5² + 7² + 11² = 216 + 4

Another fun challenge would be to place the two duplicate pieces in a symmetrical or otherwise aesthetically pleasing way. I've just been letting pure chance dictate which piece is duplicated and where it ends up, i.e. solving the 35 unique pieces and hoping the 6 remaining squares are all joined together. It works but the solutions aren't always the prettiest.

Heptominoes

This is where it starts getting fun. For the first time we've got a real choice of how many squares we can do and what size they are. For unholey squares the sizes possible are 7², 14² and 21² (28² > 757 so we don't need to worry about that) and for squares with a centre hole (which we're gonna need for the harbour heptomino) the available sizes are 13² and 15². Actually, a 6² or 8² would be possible but the hole would be off-centre so I didn't consider these. We can afford to be picky here.)

I didn't do an exhaustive list of what was possible, I just found a bunch of squares whose area added up to 756 and jumped right in. The first solution I found was the picture below.

Three 7x7s, a 13x13 and 21x21 with heptominoes.

I did the little squares first because they're the most restrictive in terms of which pieces can be used then did the great big square at the very end. I then realised that instead of having a 21x21 square, I could create four 7x7s, two 14x14s and a 13x13 which would yield a little more challenging of a solve.

 

'A little more challenging' is putting it lightly.

For a start, it took me two attempts. Admittedly this was down to my own stupidity - on the first attempt I'd done the four small squares first then moved onto the larger three, only to discover near the end that one of my 7x7 squares was actually a 6x7 and I had one leftover piece too many. The second attempt (the one pictured above) just took ages to do. Same solve order, but when I got to the last square (the bottom right 14x14) I was left with some really difficult uncooperative pieces and completing it took probably about six hours spread out over the space of the weekend.

The obvious next step here is this: One 14x14 is equivalent to four 7x7s. So It should be possible to solve a full set of heptominoes into the following:

• Eight 7x7s, a 13x13 and a 14x14.
• Twelve 7x7s and a 13x13.
  

Whether either of these is possible (or feasible solving by hand) is another matter entirely. I noticed with the construction with four 7x7s I was running out of pieces that would fit comfortably in corners or along edges by the end of the last square, and introducing even more edge is only going to make that worse. I might tackle those other possibilities at some point soon. But that's a pretty big 'might'.