34x87 Octomino Rectangle

How to create a 34x87 rectangle with Octominoes (a handy guide)

Step 1: Solve 90% of a 37x84 rectangle, then wonder why there's so much space left over and not enough pieces to fill it (37x84 = 3108, which is slightly overshooting the octominoes' 2952+6 total area.)

Step 2: Despair for a little bit. Even with a physical set of pieces I find ways to screw things up.

Step 3: Salvage a nice big chunk from the starting corner of the failed solution (the corner where all the scariest, hardest to work with pieces live), and use this as the basis for a new rectangle with the correct dimensions this time...

Fig. 1: Success!

40x74 Rectangle with Octominoes

After the success of the new set of hexominoes I got made a while back, I decided to take the obvious next step and get a full set of octominoes cut too. They arrived about a week or so ago; three batches based on David Bird's three 29x34 rectangles construction*. Fluorescent green, fluorescent yellow, and a colour which is supposed to be fluorescent blue but doesn't really glow at all unless you turn a UV torch on it. Then it goes nuts. Again, all came with that sticky protective film on both sides of the acrylic so I spent the first few days just peeling it all off, a few pieces at a time. Fun times.

Fig. 1: The blue pieces look even worse here since the mat underneath them is dark green.

Once free of their protective sticky plastic stuff, I thought I'd break 'em in with a construction, choosing 40x74 simply because it was about the only thing that would fit nicely on the table. I like having the cutting mats there to make sure everything's all lined up and nice, and anything longer or wider than 40x74 wouldn't have fit on them properly.

Solving with physical pieces is a whole 'nother ball game to just solving the way I used to (or used to attempt to, I only ever got one complete solution that way.) For most of the solving process the hardest part by far is just finding the individual pieces you're after. Especially near the start when there are like 300 or more almost identical pieces to sift through.

Once I got to the last 10% of the construction the benefits of physical pieces really started to shine. The repeated backtracking that is just infeasible with drawing the pieces is now a lot more manageable. Which is just as well, because I must have spent close to two hours trying to get the last twenty or so pieces in. There were several times where I had 368 pieces down but the remaining hole was one cell out from the shape of the piece in my hand. That's the worst bit, those near-misses, but at least I suppose they mean I'm on the right track. If there was something terrifying like parity issues going on it would have at least alerted me.

Fig. 2: Getting there...

The entire solution took maybe about 4 or 5 hours total, a little last night and the rest this morning, which is a lot less than it usually took the old way. The little hole of unfinished pieces seemed to drift around as well during the endgame as I solved, eventually ending up right in the bottom-left corner of the photo above when all the pieces finally fell into place.

Fig. 3: Another side-effect of the colour scheme is that it photographs really badly. Especially when it's me holding the camera.

Here's the solution drawn out properly so you can actually make sense of it and tell where one piece ends and another begins:

Fig. 4: The finished rectangle.

Yeah, the spacing between the holes is imperfect. The gaps are 11-12-11 but it's about as good as you can get with an even-by-even rectangle.

---

* Side note: Is there any information anywhere about how he constructed this (and his other solutions)? I always assumed he did them with a set of pieces but it's just as likely he did them using just pen and paper. Especially the nonomino patterns, making and using the full set of 1296 pieces would be a tad unwieldy.

Attempting 4xn Constructions with Hexominoes

4xn is about as tight as you can squeeze hexominoes.

3xn looks like it's pretty much impossible. Consider the blue pieces in the following image:

All four of these need to be in the final construction (and will only fit horizontally) but between them they create six 3-cell deep wells at the edge of the construction. And there's only five hexominoes (the red ones) that could fill those gaps. The I-hexomino could theoretically fill two 3-cell deep wells, but I think in every possible case the space between the two blue hexominoes either end of it would be less than 6 and therefore unfillable. Unless we're going for constructions with holes permitted, in which case that would be fine after all. But exceedingly difficult.

Then, check out these green cases that create two adjacent 2-cell deep wells. In filling one of them, either you have to use one of the red pieces from above, or you use a piece that has a 2-cell extension, which would then cover the square marked by the red 'X' and create a new 3 (or more) cell deep well.

I know this isn't a rigorous, mathematically watertight proof but it's enough of a deterrent to stop me spending ages looking for 3xn solutions.


So, back to 4-cell high...
Similar to how it is with pentominoes (the narrower the rectangle, the fewer solutions there are), finding 4xn rectangles with hexominoes has proven to be surprisingly challenging. The few search programs I know how to use don't seem to like really narrow rectangles very much either, which left me doubtful I'd be able to do much better by hand. (Although in hindsight it's more likely I just don't know how to use the programs as well as I think I do, or how to set them up so that they search efficiently.)

A few months back I'd found the solution below using the combined set of hexominoes and pentominoes. It's not really what I'm aiming for though; the addition of the smaller pentominoes makes this about a hundred times easier, and I was able to place the holes symmetrically as a result.

On 31/12/19 I had another crack at this, aiming for a 4x53 grid using just the hexominoes, but with no constraints on where the two holes would be. Just proving that a 4xn solution exists would be enough for the first step; making it all pretty could come later.

After far too long (about an hour, maybe? It's hard to say because I tend to lose track of time when doing things like this) I found a solution. This one:

It's butt ugly though; not only are the two holes not placed in any kind of order but one is on the edge of the rectangle too, which just doesn't look right to me. It's not really a hole now, is it? It's just some weird notch out of the side of the puzzle. Oh well, it's a start.

Side note, that 'T' piece near the right-hand end was the absolute worst piece to place. Had I used it up right near the start it might not have been such a pain in the arse, but somehow it escaped my attention until there wasn't a lot of long skinny pieces left that worked well with it. In order to place it vertically rather than horizontally, it needed to have one of the holes either side of it too, since it partitions the rectangle into two parts, both of odd size.

But, it's a proof of concept at least. A symmetrical 4x53 rectangle seems way more possible now than it did before. (Edit 06/09/2020: I found one!)

Where to next?

At this point I've written pretty much everything there is to write regarding stuff like my solving process. And a lot of times when I solve something with hexominoes or heptominoes now, it isn't anything particularly interesting or challenging or worth telling the internet about - just more of the same.
So the plan for 2020 might be to sort of vary thing a little bit, still keeping it firmly to do with polyforms but not just a monthly 'Here's a bunch of pictures of heptomino constructions with not much in the way of descriptions to go with them' type posts. Which is what this place has a very real risk of becoming.

Fig. 1: Three 16x16 squares with the heptominoes.

See?

That one was actually solved with laser cutting in mind, if I ever wanted a nice new set of heptominoes, cutting this design from 3 small (180x180mm) pieces would be way more cost-effective than trying to cut them any other way. Probably.

Then a few weeks ago I solved (mostly) the one below. Instead of doing what I usually do and spreading out the set of heptominoes out all over the desk before solving manually, I did this by drawing it directly in MS Paint and crossing off the pieces from a list as I went. This has a few advantages - since I'm drawing the complete outer shape first I can guarantee I've put the centre hole in the right place. And it saves me having to redraw the solution once I've found it. And that's a fair enough trade off for not being able to backtrack nicely. And there being a risk of drawing pieces in wrong as well. For all the shortcomings of using a big ol' set of physical pieces, there's never the possibility that you'll place an n-omino with the wrong n while you're solving.

Fig. 2: Three 11x23 parallelograms. First two by hand, last one partially completed with computer search.

It's putting the last 15 or so pieces in that are the worst when you're doing this without a physical set. Backtracking and keeping track of which pieces have and haven't been used is just too much for my little mind. Especially when I'm tired and it's an evening and I've been at work all day. Which is most of the times I do things like this.

So yeah. Expect a more varied polyominoes blog in the new year hopefully.

Oh. And another thing. The future may involve octominoes a bit more...

Octominoes: The Hall of Shame

Hoo boy, where do I start with this one?

Fig. 1:  ;~;

This is what happens when you solve without a physical set of pieces. Pieces that don't belong in the set (in this case, the two blue nonominoes) creep in undetected, and only when you're down to the last little corner do you realise that the remaining space is the wrong size. I do a quick manual check to see if the number of free squares are divisible by 8 at about this point, and in this case it wasn't so I engaged panic mode (i.e. looked for the offending pieces, found that they were nowhere near the edge of the solution, and gave up.)

This was my second crack at the same solution, a month or so later:

Fig. 2: Another 4 hours I'll never get back.

This time, the area of the final space was divisible by 8, but it wasn't the multiple of 8 I was expecting. I had 15 octominoes left to place, and an area of 14*8 = 112 unit squares. So I reckon I've used a piece twice somehow. I've looked over the solution but can't see it, so if anyone actually reads this and has a better eye than me, see if you can spot what I did wrong here.

A while after all this, I read somewhere that octominoes have parity constraints of sorts. Or at least the 363 unholey ones do. (See here, click through to 'Other octomino constructions' and it's about 2/3 the way down.) I'm still trying to get my head around this; I'm still not sure if and how it will impact constructions like this. Maybe this shape wasn't even solvable to begin with, since I put down the holey octominoes first, reducing the construction to a solution with the set of 363 unholey ones?

Hardware Upgrade

Exciting times! Well, depending on your definition of excitement anyway. This blog sets the bar for exciting pretty damn low.

To cut a short story even shorter, I found a laser cutting place a little while ago and got a set of pentominoes and hexominoes cut from acrylic. It's one of those times it really hits me we're living in the future, the fact that I can just draw up a .svg file of whatever polyominoes I want, click a few buttons then a week or so later those exact polyominoes rock up at the house in physical form.
(Actually I was out when they attempted delivery so I had to trail right out the the sorting office, but it's still pretty impressive. That or I'm just easily impressed.) Anyways, here they are:

Just look at all that sticky protective stuff on the perspex - that's on both sides of the pieces, which took an absolute age to manually peel off each individual piece. Worth it though, they're all lovely and pretty and shiny.

Not that you can tell, mind you, thanks to the amazing fuzzy blurriness of my phone camera. I've been meaning to get a proper camera for ages now. But then again I'd been meaning to get polyominoes laser cut since about June so that might be a way off yet. I just have a habit of putting off doing things for no real reason, which isn't good.
What is good however is the way these hexominoes are when you use them. My original set were cut on a CNC routing machine, and as a result have these weird beveled edges thanks to the width of the drill. Which means that when you turn pieces over they look weird, and sometimes pieces just don't comfortably fit together, mainly interlocking pieces with C-pentomino-like indents in them. But these are all nice and precise and fit together flawlessly, it's just so satisfying to sit there building stuff with them. Oh yeah, and they're scaled to 1cm squares too, so I can use that cutting mat to assist with construction. (Not that it helps much clearly, given the amount of patterns I've cocked up due to misaligning things in the past...)

Here's the full set. Hexominoes, pentominoes, and a bunch of little monominoes and dominoes which are useful for marking out pattern boundaries and hole locations and other such things.

Of course the real goal here wasn't just to have a nice spanking new set of hexominoes. Lord no! These were just a test run really, to see what kind of quality the pieces would be and how much everything would cost, stuff like that. But now that I know this works, the plan is to get myself some octominoes made. Never mind that there's not a big enough flat surface in the house to use them on, that's besides the point. Octominoes! Picture it, all done in fluorescent clear plastic so you can see the boundaries between pieces nicely - that's the one flaw with these hexominoes, but I chose a solid colour on purpose so when I eventually make the octominoes they're visually distinct.

And try not to think about how long it'll take to manually remove the scratch-protection sticky business from all 369 octominoes. On both sides.

Oh yeah, almost forgot, here's a couple of little hexomino things, just since I've been playing with the new set quite a bit recently. Here's a better illustration of the 11-hole rectangle from the photo above, because due to a combination of lighting and piece colour you couldn't really see what's going on:

And here's a 5-cell high parallelogram that was a ball-ache to complete. In fact I used a program to place the last 8 pieces in a fit of laziness. It was getting late and I had other stuff to do.

And then I found a bunch of different pattern variations based on a 15x15 square with 15 holes. There's some quite nice challenges here, analogous to the pentominoes in an 8x8 square with 4 holes that you can place wherever. It's hexominoes though so parity constraints mean you can't just stick the holes anywhere, but it still leaves enough room for creativity. Hell, now that I can laser cut stuff I'm thinking about the possibility of making a little tray to hold a 15x15 solution, and 15 monominoes in a very different colour that can be used as a little self-contained puzzle.
Here's three example solutions for you to feast your eyes on, arranged from left to right in increasing order of fiendishness.

More heptomino things

Recently I've been way busier than usual with non-polyform-related things. There haven't been as many evenings where I could just whip out the ol' heptominoes set, so constructions have been a little thin on the ground. Additionally, I can't help but feel I'm beginning to exhaust all the possibilities with just heptominoes (well, all the interesting possibilities anyway, I'm sure there's plenty more rectangles with holes in them possible but after the first five or so they don't make for particularly gripping blog posts.)
Anyway, to kick things off here's a squarish shape with minimal holes and maximal possible symmetry, that I'm surprised I hadn't thought of sooner:

Here's two parallelograms, using the full set of 108 split between them. Getting the holes centered here was hard, it's impossible to eyeball it and it's a bit of a pain to work out where they should be by counting. And it never looks quite right either, just due to the sloping nature of the diagonal sides. Still, far as I can tell this is correct:

For reference, the first one took about 10-15 minutes, and the second one took a bloody age because I'd foolishly forgot to use the [ shaped piece up earlier. And it doesn't play nicely with other pieces.
Things like three 11x23 or 4 10x19 parallelograms are probably possible too. Next time I've got a free evening I'll have a crack at one of them maybe.

A while ago I found a nice hexomino solution (about half-way down that page) that had a 7x9 rectangular hole in it, which could fit a set of pentominoes inside it with 3 cells to spare. Well, I went one better and found a heptomino frame that could accommodate that inside it, creating the following three-layer pattern. With the holes spaced nicely around the edge too. Forget 45° zig-zag edges - five-cell-high tubes with heptominoes are my new least favourite thing to solve.

To me right now, this just screams 'find a fourth layer with the octominoes!' I haven't checked yet if it's mathematically possible to, or at least if it's possible without introducing more holes than the 6 required for the six holey octominoes. I'll have to have a check.