Thursday, February 11, 2021

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

3 comments:

  1. I am looking for ways to pack the 66 octiamonds in 6 congruent figures of 11 pieces each. Do you know of any collection or compilations? I have seen six semiregular hexagons with side lengths 6 and 2 alternating. Also seen 6 trapezia that can join to make a big hollow hexagon. These are computationally difficult though. Making 11 shapes with 6 pieces each is computationally easier.

    ReplyDelete
    Replies
    1. The page at https://www.mathpuzzle.com/octiamond.html has at least one other, about 2/3 of the way down the page there are six jagged-edged approximations of rectangles. Directly below that there's also the diagram for those six wedge-shapes but it doesn't give a solution, just states that one is possible. I don't know of any others but if I find any I'll link to them here.

      Delete
    2. Actually, now you've got me tempted to look for some of these myself. By computer search most likely, I imagine solving these by hand is a little beyond my capability.

      Delete