Enneominoes, revisited

First off some unusual news in the world of big tilings with big sets of polyominoes. It turns out that Sumio Baba of (presumably) Japan had been putting together shapes using sets of 10- 11 and 12-ominoes in the mid-2000's unknown to the rest of the world. Part of the reason for this is that he'd shared them with the world via a little Kindle eBook on Amazon, which is the last place you'd look really. Sadly, (and I think this is a fault of Amazon rather than the author; cheers Bezos ya berk) when you buy these there's no way of zooming in or doing anything with the pictures - the 11-omino and 12-omino squares are just big fuzzy unreadable grey lumps.

The smaller ones (if you can call heptomino and octomino sets smaller that is) are legit though, from what I can see snooping through the free preview samples so I'll take his word for it with the bigger ones. (Oh, and there's loads of big polyiamond and polyhex sets there too, the larger ones probably just as unreadable due to the file format too...)

So needless to say after this big tease and subsequent disappointment I was left fiending for some big tilings with unwieldy polyform sets. And with no other choice, my only option was to dig out the biggest set I had, the enneominoes, and have another crack at making something with them myself.

Phase 1: The Design

The main constraint I had on my choice of shape to fill was the size of the table in my room. Its dimensions are 68x120cm, which corresponds to a maximum rectangle size of 102x180 units, with my enneomino set being made at 6.666mm/edge. This sort of forced something rectangular, just because the bounding box of a diamond or parallelogram or something is way bigger than that of a rectangle of the same area. So I knocked together a python script that listed the various rectangles with an area slightly above 11565 square units (along with the corresponding hole count), and I picked one that

a.) I hadn't already done last time, and

b.) was odd x odd, which makes it slightly easier to achieve high symmetry placing the holes.

I settled on 93x125 with 60 holes - two domino holes and 56 monomino ones. Using MS Paint zoomed right in so you can see the grid and the individual pixels is a godsend for fleshing out things like this, finding a nice configuration, checking it's symmetrical and counting how far from the borders the holes all are for ease of construction. the end result was this:

and with that I could sweep everything off my table onto the floor and begin building.

Phase 2: The Construction

First off I tried something a little different. Something I don't really bother with with heptominoes or octominoes, but felt necessary this time. I painstakingly sorted all the enneominoes into a half dozen boxes by 'category'. First, all the holey pieces came out - fairly easy, they're white plastic so stand out a mile in the box. Then anything with a 2x2 sub-rectangle in the piece got put in a separate box (2x3 sub-rectangles got their own tiny box for the very end) and I also split out any 'snakes', i.e. pieces with no branches that are just a chain of squares.

Fig. 1: This kind of thing.

These pieces have no special significance when it comes to packing them, it just makes looking for an individual piece a little easier (and it was easy to pick them out by eye). You know which of the smaller boxes a piece is in so that's looking through ~400 pieces rather than a thousand. I kind of wish I'd filtered down further, maybe taking out all the pieces that fit in a 2xn or 3xn box. But I was running out of tupperware by this point so that categories I had would have to do.

Add caption

The grille I'd picked for the holey pieces was tougher than I'd anticipated - the pieces just needed to be too close together and that sort of forced specific pieces to go between them. And looking for those specific pieces was a tedious affair. I then realised that with like 56 holes and only 37 or whatever holey pieces, I didn't need to pack them so closely, but I'd already done like 20 by that point (it was late and I was tired, okay) so they were staying like that. Then a case of counting and checking like 5 times to make sure the number of units between the end of the domino-shaped hole and the edge of the rectangle was the same as that in the blueprint. I wasn't about to have a repeat of last time.

A Random Aside

All this time I was wondering another thing - how exactly Sumio Baba was constructiong his creations. As in, by hand or by computer search. There certainly seems to be a look of hand-solved-ness to them, the David Bird-esque clumping together of the big chunky pieces in one corner. And some mention in the accompanying text about the difficulty of solving (I think - but my command of the Japanese language is pretty dire considering how long I've been studying it).

Which then begs the question, what kind of technique was used for keeping track of which pieces were already in the construction vs. were still free to use? That is essentially what all my physical sets of pieces are, a way of ensuring I don't re-use a piece or miss one out. For smaller sets like hexominoes where you quickly commit to memory all the pieces they're not needed - I've sketched out solutions freehand or solved via drawing using the table border tools in Excel on particularly slow days at work. But for a set like the 12-ominoes...

Actually I can sort of think of something that could be manageable - I'd need to throw together something that could convert between a graphical representation of a polyomino and a simple textual form, something like APGcode for storing objects in Conway's Game of Life. Then it'd be possible to have a searchable list of the pieces and a flag for each as to whether it'd been used or not. (Provided you had a nice means of generating all the pieces, that's another headache in itself!) And as for creating the actual solution, honestly I'd probably do it in Microsoft Paint, the old classic. Worked last time...

The Construction (again)

The remainder of the solve was knocked out in practically one go - a single day (07/02/25) from about half 9 in the morning to just before 4, with breaks here and there to have lunch and learn the keys to '5 Minutes' by The Stranglers for a rehearsal that evening. But whenever there was a gap I was drawn back to the table with the 'ominoes on it, intending to do 'just one more' or to fill one little tantalising gap. And each time it would turn into another 30 minute sesh where I'd put like a hundred pieces in and have to tear myself away to do normal person things.

These are markedly trickier than octominoes. I probably mentioned it last time but that one extra square in each piece, you really feel it. Everything's a bit wigglier and weirder, and I notice I have to take much more care finding a piece that not only fits the hole I want to plug but that doesn't also wriggle around and interfere with another area somewhere else. The first 75% of a heptomino construction I can generally sleep through pretty much, unless it's something with weird diagonal edges or a really thin rectangle, or multiple congruent shapes. But these it's tougher. Not something I can do so well while tired either.

Another issue I ran into was due to sorting the pieces into boxes before hand. I prioritised the 'normal regular pieces' box, only to near the end find I had an abundance of snakes. And snakes don't tend to tile well with other snakes, unless you've got a lucky situation where two of them bend in perfect unison and can just be stacked together. The top-left of the solution has a bit of a gathering of these pieces, as I furiously used them up before getting to the 2x2-sub-square pieces. Which are (marginally...) nicer to tile.

Again I got really lucky with the very endgame - I could I suppose say I made my own luck by being careful with the order I used the pieces, but there was still a big degree of trial and error involved too. I only had to spend about half an hour or 45 minutes max on the repeated backtracking phase getting the last 15 or 20 pieces to play nicely.

I wondered a little bit if it's not any particular property of the 2x2 or 2x3 sub-boxes that make those end game pieces fit together nicely as much as it's due to the lower perimeter that results from a more compact shape. Less units of edge that need to be matched perfectly?

Fig. 2: The completed 93x125 rectangle. I'm scared there might be mistakes in this drawing, because I caught one of them while finishing it and now I'm thinking could there be any more in there?

Total solve time, somewhere between 10 and 12 hours, probably closer to the 12 side but once you hit that flow state it's really hard to keep track of how long you've been sat there for. And bonus points for not building to the wrong dimensions, or with off-centered holes and having to tear out and redo any huge chunks. That's a first for enneominoes, and a rarity in general for me.

Enneominoes!

It had to happen sooner or later.

Ever since not long after I got my octominoes made, I'd wondered occasionally whether the next set up would even be feasible. For the longest time I dismissed the idea outright; octominoes was as high as I'd be able to go, for three reasons:-

Firstly, the total area of 1285 pieces as 10mm per unit edge was just far too much to handle. The octominoes already pushed the limit of what the table in my room could hold, and even if I resorted to building enneomino constructions on the floor I would struggle with particularly long and skinny rectangles. (That and the fact it's all carpet so not really a suitable surface.)

Secondly, the amount of pieces would just be too much to work with - I knew well the pain of searching through the box of 300+ octominoes for that one specific piece (usually only to find that I'd already used it in the construction...) and even making the enneominoes in 10 colours, that'd still be 128 or so pieces of each colour, so even if I knew the colour of the piece I was after it'd still be a tedious hunt every time. And more often than not I wouldn't even know the colour of the piece I was searching for.

And finally, making this set wasn't going to be cheap. And I'm averse to spending money at the best of times, so was very reluctant to look too hard into this if I was laser cutting something that was going to spend most of its life in a box in my room for the above two reasons.

But even then these reasons felt more like excuses than actual set-in-stone barriers; to paraphrase a certain Ms. Satou, "I knew the possibility of it happening was there."

Making the Set

Gradually I realised a few things that sort of tipped the scales. Firstly, I let go of the idea that the pieces had to be 10mm/edge. This was the case for the smaller sets because it allowed me to line pieces up to the grid printed on the cutting mats, a handy help given my track record for misaligning holes and building things to the slight wrong dimensions. I realised that by making each unit edge 6 and two-thirds millimetres I'd still be able to line some of the pieces up with the grid, and the tradeoff for this slightly awkward compromise was that I'd be able to actually fit more pieces on the table. Potentially even all of them if I'd done my maths right.

I then found a construction by Patrick Hamlyn which had the entire set of unholey enneominoes in 48 congruent rectangles, which I could use as a basis for the CAD files when I got the pieces cut. The number of rectangles meant I had a bit of flexibility with how many batches I got them cut in, and as a result the number of different colours. Eventually I settled on eight (plus a ninth for the holey pieces), which was more influenced by the number of colours of perspex the laser cutting place offered than anything else. It gives 156 pieces of each colour, which is not ideal but it's marginally better than 1248 of each colour I suppose.

I drew up the .SVG files of the pieces while on holiday in Arran, on the evenings where the midges were out in full force and I couldn't do a great deal else. This wasn't the most fun task, just manually copying out the pieces from the reference image. Almost as tedious as digitising octomino solutions from a photo after finding them. And then when I'd finally uploaded all the files to the laser cutting people and parted with an eye-watering amount of money, I set about devising something to actually solve with the pieces once they got here. Something easy to start with, or at least as easy as enneominoes can be. A 79x147 rectangle with the holes all in the centre in a 4-fold symmetrical configuration, for instance.

The Solve

By this point I naively assumed that the enneominoes wouldn't be that much harder to solve than the octominoes - they were wigglier, sure, but there was more of them and therefore more possible pieces to fill a particular niche whenever one should arise in the boundary of the solved area. Right? And lots of pieces with inner 2x2 squares too. 436 of them in fact - a whole 34% of the pieces, up from 23% of the heptominoes and 30.6% of the octominoes.

I misunderestimated these bastards.

Fig. 1: The start of the peeling process. To call it gruelling would be an insult to gruel.

I started the solving and the peeling of the protective sticky plastic pretty much simultaneously.  It was less that the solve was too exciting to wait for, and more that the peeling process was too boring to do on its own. And at this point I made my first mistake.

In planning the boundaries and hole placements of the rectangle, I worked in units and units squared, and then had to convert back to mm in order to place markers on the table. But somewhere here clearly I cocked up, because I built the ring of holey pieces, filled it with 100+ pieces and built a good chunk of solution connecting the centre to the bottom edge before realising it was two thirds of a millimetre higher than it needed to be. So I had to rip out a strip of enneominoes, move a huge patch down carefully without disrupting everything, and then re-solve the little strip I'd taken out with a completely different set of pieces and some new ridiculous constraints on the pieces. Fun stuff. An afternoon well spent.

By this point it had dawned on me these were an entirely different beast to the octominoes - the difficulty plateau I'd envisioned after comparing the octominoes to the heptominoes just wasn't there, and this wasn't going to be as fast and easy a 'warm-up solution' as I'd initially hoped. Additionally, it was taking absolutely ages; by this point I must have sunk 6 or 7 hours into the solution and only placed about 350 pieces or so. And a lot of this time was spent digging around looking for specific pieces, just like I'd feared. Additionally, this being the first time with the pieces meant I wasn't familiar enough with them to know which colour I was looking for half the time either. So I began trying to organise things a little bit. A separate dish where I'd put all the 'really nice' bits - those containing a 2x3 rectangle as sub-polyomino, a dish for the pieces with 2x2 subsections, and a dish for pieces that would work to fill 1xn cavities at the edge of the board - which I internally refer to as edge pieces despite the fact you can use them anywhere really. And this made things a tiny bit easier.

Fig. 2: How the solution looked at about this point. The various trays were my method of sorting the pieces - pieces with 2x3 sections in the smallest tub, ones with 2x2 sections on that big tray on the floor, etc. This was also the last time I could use my desk for normal desk things like writing and eating for a while.

The going got tougher still when it came to filling those two narrow parts between the centre and the long edges. They're not even particularly narrow by most standards - like 20 squares or something, would have been a walk in the cake with heptominoes - but it was enough to make me sneakily reach into the pile of pieces marked 'save for later' multiple times. By the time I had extended the top edge along to the top-left corner I had pretty much no 'normal' pieces left, just 2x2-box ones. Plain sailing from here onwards, I thought.

A Cock-up Most Spectacular

The remainder of the solve was, just as I'd hoped, fairly simple - no worse than putting the last third of the octominoes in. Until I got down to about 19 or so pieces and slowly realised with a creeping sense of dread that the space I had left was concerningly smaller than it should be. I had checked and double-checked all the measurements as I went to prevent exactly this type of thing; I didn't want a repeat of the off-centre centre a few days back. But obviously I hadn't checked hard enough, and sure enough after another tedious bout of counting rows I discovered I had in fact built a 79x146 rectangle - one row shorter than it should be.

I'm still to this day unsure of how I managed to screw this up, I had left little post-it notes tucked under the top edge of the solution as I went denoting the number of columns to each edge in each direction. I must have just been exceptionally tired that day or something.

And so I ripped out a huge wedge of solved pieces right back up to the top left corner, probably 150 or so in total, and began again to the correct dimensions this time. Which was a lot harder than the first time around, given that I was working in a long, narrow space.

The Endgame

The final bit of the solution wasn't too bad all things considered. Once I've whittled the set down to a dozen or so squarish blocky shapes, and the space they need to go into doesn't have any tricky bits, it's just a matter of trial and error. And in this case it maybe took only an hour or so to find something that worked.

Fig. 3: Complete!

The total time to solve was probably 12-14 hours, spread out over several days. Many little solve sessions crowbarred in between work, sleep, gym and whatever else I had to do. And some of that was peeling the plastic backing off pieces too. In fact there's a few of the pink pieces where I don't know quite what was going on, but the stuff just wouldn't come off (or would come off in tiny bits) so I just left it.

Here's a nice clear image of the solution where you can actually see the individual pieces. Which took another couple of hours to draw up, that wasn't a fun task... Normally I find the digitising of solutions kind of therapeutic, but this one just took the piss.

Fig. 4: The completed rectangle in all its glory.

So I suppose the question now is, what next? Dekominoes are definitely out of the question, but I reckon it's only a matter of time before I try something else with the enneominoes, something a little more interesting. Sets of five congruent shapes are definitely possible. For next time I don't feel like using my desk for a week or so.

And there's another fun side effect of solving these I noticed. When you go back to hexominoes (or even heptominoes) afterwards, they seem like baby toys in comparison. There's barely any of them, and they're all such simple shapes... This holds for a little while, until you're about half way into a solution, and then they kindly remind you that they can still be fiendishly tricky.

Picking this back up after a long break

Man, I've missed this so much. Only one post so far this year and it was ages ago. Basically, stuff just got kind of busy, a surprise change of job in February/March took up a big chunk of my time, and with my attention divided between the blog and the shiny new website I ended up not contributing a great deal to either. But~! Enough excuses. A few nights ago - just for the hell of it, just for old times' sake - I dug out the heptominoes and just had a crack at solving something with them. Just a 29x29 rectangle with a central 9x9 hole (and some other unit holes). Knowing full well it wouldn't be something interesting enough to write to the blog or the site about.

And I remembered why I started doing this in the first place.

Spring 2019 - when this blog started) - was, for me, not exactly the most fun of times. And I think in those evenings of stumbling into the world of polyforms, retreading the steps people like David Bird and Michael Keller had made way before me, it became a sort of meditative thing. When I was knee deep in a hexomino or heptomino thing all I was able to focus on were the pieces at hand (and occasionally the Andrew W.K. I had blasting on the iPod) and it was a welcome break from everything else going on. Kept me sane (or at least, kept me from getting any less sane than I already was...)

And I think that's what I need now.

Fig. 1: I finally made good on that promise to buy a proper camera instead of just using the one on my phone. Problem now is, I don't know how to use it (and I scale down the photos for the site anyway to save space) so they still look just as bad.

It's not like I've got a lack of things to write about on the blog, anyway. In the past 6 months or so I've been getting things made (generally laser cut) like no-one's business, though these generally lie in the more 'out there' realms of polyforms - sets where the base shape is something weird like a domino sliced in half diagonally, or assembly puzzles of mathematically incomplete polycube sets. Think Soma cube, and its many variations and relatives. Enough to keep churning posts out on here anyhow.

Here's a picture of some actual polyominoes, as way of apology for turning this place into LiveJournal up there before:

Fig. 2: Four-colouring these adds an interesting challenge.

Oh, and I made this too.

Add caption

It's the nine enneominoes that have either the 2x4 octomino or the 3x3 with a missing corner as a subset. There's one solution (excluding rotations and reflections) for getting them into that 9x9 box, and I'll leave it as a puzzle for the reader (if indeed there are any).

I made this stupidly small - the pieces are at a scale of 5mm/edge meaning the entire thing including tray is a mere 65mm wide. I was trialling how small I could feasibly make pieces and have them still be nice to play with. Because I have plans for a certain large set of pieces. And evidently 5mm/edge is just a tad too small. Might have to do 8mm.

More Octominoes

Here's a few more (okay, two) octomino constructions from over the past few weeks. Mainly boring shapes like rectangles, just because I'm limited by the size of the desk in my room. A big diamond with diagonal edges would be awesome but it's just not going to fit on the available working space, in fact this one with height 57 really pushes the limit of what I can do, it was practically overhanging the edge of the desk:

Fig. 1: A 57x63 frame that fits the 23x33 heptomino rectangle perfectly inside it.

An odd thing with n-ominoes is this - as n increases, not only does the number of n-ominoes with a particular feature increase, but the proportion of all n-ominoes with that feature increases too. Take polyominoes with holes for instance. With heptominoes there's one, giving a proportion of 1/108 = 0.93%. With octominoes it jumps to 6/369 = 1.63%. And this trend seems to keep going, as shown below.

Counts for the really big polyominoes taken from here. Sorry it's an image and not a copy and paste-able format, blogger hates tables for some reason.

My gut feeling is that this keeps going, approaching 100% but never quite getting there, instead tapering off in a big s-shaped curve.

Here's a graph that has everything wrong with it. Default OpenOffice design, tidied up in MSPaint, uses percentages which I assume isn't good form for actual scientific purposes... I may as well have gone the whole hog and done the captions using WordArt.

The same trend seems to hold true for other features too, such as polyominoes containing a 2x2 block inside them somewhere as a subset of their squares, or pieces with a two unit deep well (like the pi heptomino.) I guess it could be in part down to the fact that as n increases there's more scope for a given piece to exhibit several of these features at the same time, e.g. have an internal hole as well as a 2x2 sub-section. Maybe? This feels like the kind of territory that would need approaching from a rigorous mathematical angle, but I have no idea how to do that so the best you're going to get is me guessing wildly based on a hunch I got from spending too long playing with glorified jigsaw puzzles.

Here's a 29x102 rectangle with the octominoes. David Bird beat me to the punch by several decades but I'm still going to share it here anyway, dammit.

Ooh, and we get a final bonus guest solution this time too... I had shared an older polyomino solution (the one with concentric layers of 5- through 8-ominoes) to the Puzzle Fun facebook group, mentioning that there was a possibility for a 121x129 layer of enneominoes to surround the entire construction. Sadly, there was no arrangement of holes that would preserve the symmetry of the hole distributions in the inner layers, but I settled on something close enough and Patrick Hamlyn found the following solution for it:

(Click for full-size.)

Interesting to note are the pieces his search program saved for last - the ones just below the bottom-left corner of the octominoes section. There's a lot of the kind of pieces I'd expect, blocky, rectangular pieces, but also a lot of long thin bits with a completely smooth edge on one side. I'd never considered holding onto these pieces that late in a solution, but clearly it gets results so it's maybe something worth me experimenting with while solving by hand.

And yeah, if anyone fancies wrapping a set of dekominoes around that, that would be grand.