More Wiggly-edged Rectangles

There's not a technical term for shapes like this, is there?

Fig. 1: With heptominoes.

Those toothed edges are just as difficult as they look. They start out easy enough - the bottom edge was done first using pieces that it makes sense to put there, the 'H' shape and various other U-pentomino-derived pieces that fit perfectly. But alas there aren't enough of those shapes to go all the way around. And by the time I got to the middle of the top edge desperation had kicked in and I was using any piece I could to try and complete the perimeter. The straight line heptomino for example. And even one or two of the pieces with a 2x2 block which I generally try to hold onto until near the end.

Once the perimeter is done it doesn't get any easier. See, now I'm left with a very irregular cavity to fill, and if we want the central hole to be, well, central that forces the position of the harbour heptomino too. So you're left to squeeze an already awkward batch of pieces into a shape that really wasn't designed to accomodate them, just like last time.

- - -

As I was solving the above I wondered whether this sort of shape would be any easier with octominoes. On paper it felt like it should be - sure, an octomino rectangle would have a longer perimeter but the amount of pieces which would fit nicely into that perimeter would increase too. And the ratio of perimeter to area ought to mean that once the perimeter was completed we'd still have a large variety of pieces for the middle.

Fig. 2: The octominoes. Yeah, the corners are a slightly different style - I'd miscounted the number of teeth needed and offsetting them by one like this was a lucky save.

Turns out it isn't really that much easier after all. Maybe a tiiiny bit easier because of pieces like that 'E' shape in the top edge, but the perimeter got way longer and the number of nice pieces just hadn't increased enough to counterbalance it. Admittedly once I'd cleared that first hurdle, completing the rest of the solution was no worse than any other octomino solve I'd done in the past, so maybe I was partially right. Total time, maybe about 4 hours or so, spread out over one afternoon and evening. I don't know, I don't time these things. I just occasionally glance at the clock and realise I've wasted a whole afternoon and I should have had dinner an hour ago. But hey, there are worse ways to waste time.

Some Assorted Solutions

Polyform-related shenanigans have been on the back burner somewhat recently, mainly because I'm in the process of moving house and don't have table space right now to spread out even a full set of hexominoes, let alone a larger set. So this post is going to be a collection of solutions I found several weeks ago but didn't write about at the time for whatever reason.

First up, continuing with the last post's theme of long skinny rectangles we've got the heptominoes in a 9x85 rectangle with nine holes. I think I found this with the intention of including it in that post, but then I found the 5 high rectangle which was way more interesting and in the interest of not making that post a mile long I took this one out.

In February some time I put together another variant of the well-known side 20 diamond found originally by David Bird - same outer shape, different hole configuration. Nothing particularly groundbreaking to look at, but the solving process was interesting. The jagged outer edges use up pretty much every piece with any stairstep-type edges, leaving a glut of pieces with 2-cell protrusions for the middle. Which is less than ideal.

And finally, I found a few more fun things with the hexominoes, in what I call the 15x15-15 challenge because I'm terrible with names like that. The idea is, make a 15x15 square with 15 holes using the hexominoes. The challenge is to make the 15 holes look nice, given that they can't retain the symmetry of the outer square. There's some examples here (from back in 2019) and a few more just below, from back in March.

A silicon ship looking configuration.

Side note: For whatever reason the word 'quincunx' makes me giggle like an idiot.

Oh yeah. One last thing that I almost didn't include since it's a shameful chapter indeed in the history of polyominoes. I had attempted a heptomino construction with the crenelated edges similar to that top hexomino one. And I made the classic mistake of doing the math for it late one night when I was too tired to be trusted with simple tasks like adding a few numbers up. This was the result:

Yep. For whatever reason I'd thought that each edge had one more protrusion than it did which threw my area calculation off by 4. And because it was late and I was just itching to get my solve on, I didn't even think to double-check everything. I just never learn...

Polyominoes: How Thin Can We Go?

What is the narrowest rectangle (or vaguely rectangular shape) that can be constructed with each set of polyominoes?

Lets get the easy cases out of the way first. For pentominoes, there are 4 possible rectangles that can be made, the narrowest of which is 3x20:

Fig. 1: One of two ways of doing this (excluding rotations and reflections).
See if you can find the other way. Go on. I double dare you.

The tetrominoes don't do any rectangles due to parity issues, but if you add the triominoes (and optionally domino) into the mix you get a set that can fit nicely within a 2xn rectangle:

Fig. 2: Apparently there are 84 solutions to this excluding rotations and reflections.

 For hexominoes, each individual piece can fit within a 3xn space but we are able to rule 3xn rectangles out for the entire set together - see this older post for the grisly deets. 4xn however is totally possible as illustrated below:

That's all well and good, but what about heptominoes?

An obvious starting place is the well-known 7x107 rectangle which can be made in a variety of ways using the 107 non-holey heptominoes. There's one a little way down this really old post which I found, but I was hardly the first to do so. A few weeks ago I went one better, building the following 6x127 which ended up being the inspiration for this blog post:

(Click for full size)

Thin rectangles are a fair bit harder to solve (manually at least) than wider, more squarish rectangles of the same area. I'm guessing it's just to do with the higher perimeter-to-area ratio. Every extra square bordered by perimeter is a further restriction on the heptominoes within the shape (as are things like holes). And once you get thin enough it begins to restrict weird things, like the orientation of polyominoes within the shape. A heptomino that spans 6 cells in one direction will touch both the top and the bottom side of the 6x127 rectangle for example, and if placing that shape partitions the rectangle into two areas whose areas aren't a multiple of 7 then you've just rendered the lot unsolvable.

A 5 square high rectangle with a mixture of the 1- through 7-ominoes is possible, as demonstrated in the picture below, solver unknown.

I don't know where I got this image from or who to credit for the solution. If anyone knows anything about its mysterious origins please stick it in a comment below.

Here's a neater version with the polyominoes coloured by size:

(Click to embiggen)

 

I also found the following 5x152 pure heptominoes solution using Aad van de Wetering's FlatPoly2 software.

Click for larger. It was either this or insert it vertically and make this post a mile-long scrolling marathon.

The first three quarters or so were placed by hand, and then the final 26 were input into the solver. For whatever reason (I think it's just my computer) the software takes aaages to find anything if you just give it the full shape and all the heptominoes - in fact I've never actually been patient enough to let it finish - so the only way I can find solutions is to solve manually until there's about 20 (or fewer) pieces then let it solve from there.

And height 5 might be the best we can do.

In a similar way to what we did for hexominoes, we can rule out shapes of width 3 and lower - there's a V-shaped heptomino that reaches out 4 squares in two directions, which isn't going to fit no matter how you place it. And for 4xn we run into issues too. According to the analysis that Peter Esser's 'mops' solver does, the set of heptominoes can cover a total of 373 border squares. And a 4 unit high rectangle has to be at least 190 units long for the area to be >756 (allowing for holes for the harbour heptomino.) This means we have 380 border squares for the two long edges alone (and a few more for the little short edges) which the heptominoes just can't manage. So 5 might just be as thin as we can go.

"Fun" with Polyiamonds

Introduction

In branching out the blog to include not just polyominoes but other polyforms too, I couldn't help but notice one thing: my polyiamond solving game is atrocious. I had rationalised this in all sorts of ways in the past - the paucity of chunky yet asymmetrical pieces to hold onto until the endgame was my go-to excuse - and just treated them as a harder bunch of shapes to work with in general.

But realistically it's far more likely that the reason I can't manually solve even a heptiamond construction half the time is down to the fact that, compared to polyominoes, I just haven't put the hours of practice in building up a sort of intuition for the solving process. So I made it a sort of unofficial New Years' Resolution* to try and remedy this.

Bootcamp - Heptiamonds

This is where I discovered my apparent inability to solve polyiamonds. I have a nice little set of wooden heptiamonds I got laser cut a while back, and a little tray that holds them, a 7x12 parallelogram. Except the pieces spend most of their time in a little zip-lock bag because I struggle to get them all into the tray consistently.

Heptiamonds are pretty flexible with the shapes they can do; there's no real parity constraints or anything holding them back so you can go ham - triangles, parallelograms, hexagons, you name it they'll have a go. You can do a triangle with side length 13 and a central hole. I say 'you can' because I can't, and believe me I've tried.

One of the few things I could manage was the two identical parallelograms below, found more by sheer luck and perseverance than by any kind of breakthrough in solving technique:

Fig. 1: Two 6x7 parallelograms.

In general it seems that the trial and error aspect involved in solving heptiamond things overshadows any possible impact from being careful with piece ordering. So I moved on to octiamonds instead.

Octiamonds - a tale of woe

You get a little more choice for pieces with these lot. There's 66 of them so you'd better hope there'd be at least a few which aren't a complete pain in the arse. (See the ones I singled out in the octiamonds section of this older post.)

My first success of the year with these was the 6x44 parallelogram below. I solved this one right to left (well, left to right really, but the final image got flip turned upside down at some point while I was sobbing into my keyboard trying to get InkScape to behave itself.) About two thirds of the way through the solution I realised it might be wise to start solving from both ends and meet in the middle - the thin little 60° points are notoriously tricky, especially when you're down to a very limited set of pieces. And the endgame for this one - the little trial and error period where you just place and backtrack and hope for the best - was agonisingly long, as is always the case with polyiamonds. The last 9 or 10 pieces probably took longer than the 55 or 56 that preceded them. I guess it's the Pareto Principle in action - 20% of the pieces take 80% of the time.

Fig. 2: A 6x44 parallelogram with the 66 octiamonds.

Octiamonds have parity. It works pretty much the same way as hexominoes but this time it's up- and down-pointing triangles you have to keep an eye on. Twenty-two pieces have three of one and five of the other, the rest have 4 up and 4 down, as illustrated in the diagram below. (This seems like it should be too obvious to warrant a diagram but I have doubts about my ability to express things in plain text so I'll draw one anyway.)

From this, we can discover that the total numbers of up and down triangles for the whole construction need to be either equal or differ by 4n where 0 ≤ n ≤ 11. And can you guess when I figured this out?

Camera phones in low light conditions: Not even once.

If you said 'right in the middle of a construction where the numbers of up and down triangles differ by 6' then give yourself a hearty round of applause.

The rough working out that I should have done before I placed 60 pieces...

The next time I could bring myself to attempt an octiamond construction I was a little bit more diligent with my parity checks before I set out, and it paid off. Being a bit sick of parallelograms but not wanting to do anything too adventurous I settled on an eight row high trapezium (or trapezoid as they're known in the US/Canada) which passed all the criteria - it has 8 more 'up' triangles than 'down' ones.

Fig. 6 or something: A height 8 trapezium.

Again, the solution took a while to find, but at least this time there was one.

Enneiamonds - the Final Boss of Polyiamonds**

I'm not sure what possessed me to tackle this one when I was clearly struggling with octiamonds, but I did anyway. Enneiamonds (blogger spell check has a vendetta against that word) have all the frustration of octiamonds and then some, and by far the biggest ball-ache is the introduction of holes. You need a hole for the holey enneiamond (the harbour enneiamond?) and then you need more holes to bring the total area up to something that divides nicely. Adding a further three makes the total coverage 1444 triangles which divides up nicely and allows two rhombi with two holes each to be made (Also 4 triangles with one hole each but let's not try to run before we can walk just yet.)

But knowing a solution should exist and finding that solution are two very different things.

It looks real pretty. And it looks very human-solved, the pieces getting chunkier and easier towards the top corner of the right hand rhombus. But don't be fooled. the last 15 pieces were done with a little electronic assistance.

I don't like doing this. And in fact when I started keying in the pieces which just wouldn't go, my intention was never to just find a solution - that makes for something of a hollow victory feeling when you put that last piece in and know deep down you didn't properly complete it. I initially just ran a search to check for the existence of a solution, but not the solution itself. If the program came back with '0 solutions found' I'd know to backtrack one more piece and try the search again until I reached a position where one or more solutions existed.

I used to do this back in the early days of heptomino solutions, before I got good enough at them to not need any assistance. And usually I'd need to backtrack 5 or 6 pieces and there'd be a couple of solutions lurking in that piece of search space. Not in this case, though - I had to remove fifteen pieces before it could find even one solution. If that's not irrefutable proof that polyiamonds are just a more obstinate breed than polyominoes I don't know what is. Anyway, I'd found a position where a solution was definitely possible, at least in theory. In reality, I fought on, trying configuration after configuration trying desperately to get the rest of the pieces in. The big triangle belonged in the very corner, that felt like a given; it just fit there so well and didn't seem to sit comfortably anywhere else. But beyond that I was just pushing pieces around pretty much at random, sometimes finding I could get all but one in, other times creating awkward little bays and peninsulas in the edge of the construction that seemed to exclude every other shape.

I spent way too long on this - several days' worth of mornings, lunch breaks and evenings - so I eventually decided I would do the unthinkable. I'd peek at a computer solution for those last 15 pieces. Not the entire thing; just the next few pieces, to point me in the right direction.

Key: Purple pieces were already placed, red bits I looked at the solution to find, yellow bits I did myself after the red bits were placed.

Armed with these handiest of hints, I managed (after another 20 minutes or so) to fit the last of the pieces in and gaze upon the finished construction. It still felt like a bit of a cop-out though. I suppose it's just part of the learning process - I did similar with heptominoes a year and a half ago and it wasn't long after that I was knocking out octomino rectangles in single afternoon sittings. Hopefully the next time I dig out the enneiamonds I'll be able to get a little bit further than this time, and before I know it I'll be able to just solve whatever with them without breaking a sweat.

~

* I don't know why I feel the need to prefix that with 'unofficial', it's not like there's anywhere I can go to make a New Years' Resolution official or legally binding or whatever.

** Until I make myself a set of dekiamonds, that is.

2021! (a.k.a. A Fun Little Challenge with Heptominoes and Hexominoes)

Happy new year! Going to kick off 2021 with a lazy low effort post.

In an older post I found two hexomino rectangles which had twelve holes, each in the shape of a different pentomino. Or it could be thought of as a combined pentomino/hexomino rectangle with the added condition that none of the pentominoes touch each other or the edge of the rectangle.

The topic was brought up on the 'Puzzle Fun' Facebook group, and the gauntlet was thrown down - was the same thing possible for heptominoes with hexomino-shaped holes? I had a go and found the following:

Fig. 1: 22x44. Separating the hexominoes and heptominoes out when dismantling the finished construction was not a fun job.

There's two monomino holes in there, one has to be there to placate the harbour heptomino, the second is there because otherwise the combined area (7*108 + 6*35 + 1 = 967) would be a prime number. And the hexominoes are at a higher concentration in the bottom half of the rectangle. I wasn't sure how much space I had when I started off constructing this so I packed them in really tightly at first, then when I got about three-quarters of the way through I realised I had like 4 hexominoes left so they're a tad sparser up there.

the inevitable next step will be the octomino/heptomino equivalent of this. I'm putting off starting it but I'd give it a month tops before I cave and begin trying to solve it.

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'.