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

Crinkly wrinkly shapes with Heptominoes

Seeing as I have an excess of spare time on my hands recently I've been attacking some constructions that I had previously written off as 'too hard' or at the very least on the boundary of what I could do without 'cheating' and using a computer solver. One of these is the following 29x29 rectangle with wrinkly crenelated edges around the outside, and a little 5x5 hole in the centre. And a couple of other little holes too because the harbour heptomino needs something to chow down on.

This wasn't the easiest thing in the world to put together. The first challenge was the outside corners. There are a very limited number of pieces that can occupy those corners, and I only discovered this a little way into the solution - too far in to just backtrack and start again, corners-first. Miraculously I hadn't used up too many of those precious corner pieces when I realised, so I was able to keep on trucking.
The whole perimeter of this was a completer pain in the arse to do. I started out with the left-hand edge, using pieces derived from the C- (or U- if you're weird) pentomino but they ran out fast and by the time I got to the final edge (the right-hand side) I was stuffing whatever pieces I could in, in the desperate hope they'd fit.

And they did. But they didn't leave a nice set of pieces remaining. And they didn't leave a nice shaped internal hole either. Still, I pressed on.

Fig. 2: Approximately what I had left to contend with after completing the perimeter.

From here I filled in the remainder of the space going around clockwise starting from about the 4 o' clock position. In fact, here's a needlessly detailed step-by-step of what I did. I usually refrain from this on the grounds that it's not very interesting, but really, is any of this very interesting?

Firstly, that question mark-shaped piece was just crying out to be put in that question mark-shaped hole, so I did that. Then there were a bunch of really hideous pieces (the other orange ones) that I just felt needed to be used up as early as possible, just so I didn't have to look at them again. Those two sort-of cross shaped bits especially. Winding up with one of those near the end of a solution when you're down to a handful of pieces is the stuff of nightmares.

Then, using up all those long S and L-shaped pieces because they're no fun either. Sadly, in order to do this we had to sacrifice that nice 2x4-with-a-notch-taken-out-of-it piece, but it was for the greater good. And now the edges of the hole in that top-right section are all relatively smooth and straight - ideal for for the very end game when you're solving with relatively squarish blocky pieces.

This is where the going started to get even tougher. Those two red pieces especially, I have a personal vendetta against now. I managed to get them all packed in there - but at what cost? So many potentially useful end-game bits used up in their prime.

Got that top-left corner squared off. And at this point we're left with not the worst hole in the world (that award would have to go to... I don't know, the ozone hole? Or the holes in the end of trombones that allows them to make their noise), but not the easiest to solve either. That two-cell-deep well at the far left was to haunt me for the next hour or so.
And the pieces I was left with to try and plug this hole? Check out this ragtag bunch of misfits:

Admittedly not the worst selection imaginable, but still... especially that one that kind of looks like a number 4 or a heavily-damaged tuning fork (kindly marked in orange for your identifying pleasure), that can suck a fat one. You'd think that piece and the 2-cell well would be a match made in heaven, but try as I might, it just was not to be...

At this stage in the game, there really is no more technique to speak of, no prioritisation of pieces or synergies between two pieces that are painful to deal with on their own but make a well-behaved 14-omino when coupled together. It's just a case of try something then if it fails tear it out and try something else. And that makes solution times vary wildly. Sometimes just through blind luck you'll stumble upon a valid solution after five minutes; other days it's hour after grueling hour trying various configurations in vain.  I guess the factor that determines how long this takes will be how many solutions to this particular endgame there are lurking in the search space as you wander randomly through it.

I got all but one piece in several times as I was doing this one. That's always the worst, that feeling of so near yet so far... And there's another weird thing that happens occasionally when finding a correct solution. It's when you get that 'eureka' moment, that "Yes! I've done it!" spark of excitement a fraction of a second before you've actually understood how the last two or three pieces are going to fit in there. I'd write it off as premature celebration if not for the fact it only ever seems to happen when I've got an actual solution on my hands - maybe I'm subconsciously spotting the solution and the rest of my mind takes that split-second to catch up? 'Tis a mystery.

Here's the eventual configuration I found. A quick consultation of some solving software tells me that there are 9 solutions to this, and that 5 of them do fit that '4'-shaped piece into the two-cell well, so goodness knows how I managed to miss 'em all.

In fact, here's all nine, since I'm being so generous with the pictures today. Mine is number 7.

And while we're on the subject of wicked tough constructions, here's another recent one that might be a contender for 'hardest construction so far', or at the very least most time-consuming:

As I've probably mentioned at some point before, octiamonds are just not a pleasant bunch of shapes to work with.
Sorry, no step-by-step account for this one. Partly because I solved this about two weeks ago so I can't remember the solution process clearly (other than that it was all over the place), and partly because I'd rather not re-live the experience. All I know is I solved the bottom edge first, and the rest followed, four hours later...

Octiamonds

Polyiamonds are tricky. Even the smaller sets seem harder than their similarly-sized polyomino counterparts. Hexiamonds, for example. There's 12 of them, same as the pentominoes, and in a geometric sense they don't seem any more jagged or otherwise unruly, but for whatever reason solving anything with them seems a lot harder.
I mean, it could just be that I'm more used to polyominoes and that a sort of intuition for other polyforms would build naturally with time. And with polyominoes I know all the handy tips and tricks, which pieces (or types of pieces) are most useful in which situations, whereas with polyiamonds I don't have that (yet).
With larger sets of polyominoes, (i.e. hexominoes and above) a technique emerges of saving the more cooperative shapes for the end game, and as the sets get larger this pool of 'nice' pieces increases rapidly in size. But with (say) octiamonds it's not so obvious which shapes are the most useful. They're all pretty hideous, actually, at least to the untrained eye. The little hexagon made of six triangles is the closest analogue I can think of to the 2x2 square block that makes for nicely-behaved polyominoes. But there are only 4 out of 66 octiamonds which contain it and even these 4 pieces don't play especially nicely together with each other.

So the solution below was the result of about an hour and a half of stumbling about cluelessly followed by a flash of pure luck.

Fig. 1: The 66 octiamonds in a 12x22 parallelogram.

 Another fun fact: Drawing these out neatly is really hard too. Pixel art and triangles don't mix too well.