Heptominoes Part Deux

At the end of Part One, I mentioned trying for a 11x69 rectangle construction. Sadly, the table in my room isn't quite long enough to accommodate a heptomino construction 69 squares wide without having to rearrange things, so I settled for the next best thing: a 20x38 rectangle with four holes. Symmetrically-placed holes, I might add.

After about 45 minutes (either this was a fluke or I'm getting better) I found the following solution - or at least I thought I had:

Notice anything unusual?

That's right, I somehow managed to centre the four holes incorrectly. They're all one square up from where they should be, giving the total rectangle only one axis of symmetry instead of two. And I only noticed this right at the very end when it came to drawing up a neat copy of the solution.

In my defence, the table's perspective made it looks completely fine as I was solving. That, and I clearly couldn't be bothered to count to 17.

Actually, just for the hell of it, here's a bonus heptomino construction from a few weeks back.

The 108 heptominoes (and 3 monominoes) in a 23x33 parallelogram. You've gotta call the holes 'monominoes', it makes it sound more like they're intentional.

Those wiggly edges are an absolute nightmare. You can see on the left hand side where I started, I use up all the shapes with zig-zag edges and by the time I got to the right-hand side I was just desperately trying any vaguely wiggly piece I could get my hands on.
There'll be a parallelogram with base 23 and height 33 out there, but that would mean having to build even more wiggly edges again, so I'll pass on that one for now.

The Most Useful Pentominoes - An Experiment

The first strategy that I worked out for myself when just playing around with a set of pentominoes is to try and get certain shapes used up first, so you don't have to desperately find a home for them near the end of the construction. Pieces like the X pentomino especially I grew to hate with a vengeance. And after a while of solving I sort of developed a feel for which pieces needed to be used up pronto and which ones I didn't mind saving until near the end. This was generally something like:

This was all just based on gut feelings, on how much my blood boiled on picking up or even looking at a certain piece, and there was never anything approaching a sensible, methodical look into which pieces are most or least cooperative. Until now.

Whilst trying to do something else with the program mops (scroll to the bottom of the page for the various solvers) I discovered that if the rectangle size is set to something that doesn't use all the pieces, and you've got 'Determine Frequencies' ticked, it keeps counts of each time a piece is used in a solution.

So I set it to randomly solve 200,000 5x5 rectangles (since that's going to feel fairly similar to the last half of a 5x12 or 6x10 solution) and the frequencies of each pentomino are as follows:


Piece Count
L    149575
P    143160
Y    108150
I    107900
V    106884
C     91992
S     66828
F     55200
W     55017
T     55003
Z     50006
X     10285

Or, in hideous OpenOffice default graph form:

So my intuitions and this match up fairly well, for the most part - the L, P and I pentominoes are all near the top, and the X pentomino is right down there in a class of its own below useless.
Of course, whether these values have any bearing on how useful the piece is is up for debate. It's a rough guideline at the very least, I suppose.

And of course I want to go and do the same thing with hexominoes now, don't I?

Here's the raw values after running 125,000 6x8 boards in mops, using the hexomino naming scheme from here.

Hexomino      Count
A             37420
C             23250
D             33164
E              9351
HIGH F        18540
LOW F         19888
G             26659
H             21624
I             44063
J             37513
K             19738
L             63206
M             22871
LONG N        35834
SHORT N       27537
O             41949
P             61310
Q             30998
R             43327
LONG S        20482
TALL T        17613
SHORT T       27457
U             37957
V             57020
Wa            26479
Wb            14223
Wc            19354
X              6688
ITALIC X       6912
HIGH Y        47517
LOW Y         27467
SHORT Z       20379
TALL Z        16586
HIGH 4        15534
LOW 4         20090

So there's a similar kind of trend here as there was for the pentominoes - L-shaped pieces and 'blocky' pieces with 2x2 blocks in them are most 'useful', spiky/wiggle/cross-shaped bits, not so much.

Heptominoes: A Tale of Frustration

A little while ago I managed to pack the 108 heptominoes into a 23x33 rectangle. Sadly, the three holes in the construction were just scattered wherever allowed me to solve the thing. So, not the most aesthetically pleasing. A few days ago I set about remedying that - I figured a nice fairly-symmetrical construction would be to leave the three holes in a little diagonal line centred on the middle of the rectangle, and I dug out my little heptomino set and had a crack at it.

The first two thirds of the construction were fairly easy. There are so many heptominoes at this point that for pretty much any weird hole or gnarly boundary you could possibly create, there'll be an unused 'omino waiting that fits perfectly. And just by this strategy of sticking polyominoes down however I felt like it, I got about the first 75% of the rectangle done in one sitting, half and hour tops.

...that was, until I realised that in all the excitement I hadn't put the three holes perfectly in the centre. They were misaligned by one. And so began the first of many soul-crushing backtracking steps - tearing up a good 30 or so pieces so I could put the harbour heptomino and the two monomino holes next to it into the right place and continue on my way.

There's a point, approximately when there's about 15 heptominoes left, when the previous technique of just doing whatever stops working. There'll be gaps that could be filled by a piece but that piece has already been used earlier. There's gaps that could only be filled by two copies of the same heptomino, and gaps that just can't be filled at all, so it's a slower, 'two steps forward, one step back' process from here on in. Until you get down to the very end of the endgame...

I hope you've saved those blocky, co-operative pieces for last, you're gonna need 'em.

You know what's the absolute worst? This nonsense here:

Let's have a closer look at the damage:

Yeah, that. 1 like == 1 prayer.

Actually, I've thought about it a bit more and I think this is the second worst thing. The worst is what comes next: the heart-wrenching feeling of backtracking after reaching a near-miss point like this, tearing up big swathes of carefully-placed shapes in the desperate hope that this time they'll go back together nicely.
In fact, I spent a couple of hours doing this (spread over a few evenings) and wasn't getting much further than this. 107 heptominoes placed, and then there's a little heptomino-shaped gap left... that just happens to be the wrong shape. Tear a few out, rearrange them and try again.

At this point I was itching to just give up, pile all the pieces into the little tub I keep them in, reclaim that all-important desk space for more important things, but I didn't. Because it was tantalizingly close each time. A few times I reached a point where the hole left was one square different from the last heptomino I was holding.

After a few evenings of this I decided to do the unthinkable. I backtracked 12 pieces out, then cracked open FlatPoly2 and drew in the shapes and the outline of the remaining hole. Don't worry, not to straight-out find a solution, just to enumerate the solutions. If it said there was 200 ways of getting these last twelve shapes in there, then I'd just have to try a little harder. And if there were no solutions, well, I'd decide on a course of action if and when that happened (this would either amount to backtracking a little further, or just rage-quitting and scrunching the rest of the tiling into a heap, depending on how tired I was at the time.)

As it stood, there was 7 solutions to my last little section of rectangle. Reassuring, but not as reassuring as I'd have hoped. At least I was armed with this new knowledge - not only is it possible to complete this damn thing, but it's possible without having to backtrack any further and tear up any more of my precious handiwork from earlier.
And additionally, manually keying in the shape of the gap left had forced me to pay a bit more attention to it, and those two little holes right next to each other were just crying out to be plugged with the following heptomino (that was otherwise proving infuriatingly hard to fit anywhere):

It took maybe another quarter of an hour to go from here to the complete solution, still tentatively placing and backtracking, but spurred on with the knowledge that the solution had to be around here somewhere...

And it was! It's a hell of a feeling, looking down and seeing it finally complete. Here's the solution in all its glory, drawn up all pretty:

And as much as I'd like to say it was celebrations all round on finishing this, my first thought upon slotting that last piece in was "I bet that same hole pattern is possible at the centre of an 11x69 rectangle..."

So stay tuned, I guess.

Solving Strategy (or a lack of it)

I wish there was more out there on technique when it comes to constructions with polyforms. (Don't get me wrong, I wish there was just more out there in general to do with polyforms, but this topic especially.) It's like, "such-and-such created an x-by-y rectangle using the set of z-ominoes" but there's never anything written about the process of creating it, how they did it.

The only bit of wisdom I've picked up (I have no idea where I originally got it from, but looking at all the well-known big constructions out there I'd imagine it's pretty common knowledge) is the idea of saving the big blocky rectangular 'more co-operative' shapes until the end. And using up the awkward wiggly pieces as soon as possible.
But aside from that, I have no idea. I'm pretty much chucking pieces down and crossing my fingers at this point. And of course, all bets are off when it comes to pentominoes. Since there's so few of them and none are particularly pleasant to work with (apart from the P maybe?) With hexominoes or heptominoes you can generally get the first 4/5ths of the shape done without too much pain, it's only in the end-game where the going gets tough. With pentominoes though, it's all endgame. Or at least that's how I justify it to myself when it takes me ages to do a 6x10 rectangle.

This 23x33 heptomino construction from November last year is as good as I'm able to do so far (aside from running computer searches, but where's the fun in that?)

Fig. 1 - 23x33 heptomino construction (in a fab rhubarb-and-custard colour scheme)

Yeah, the holes aren't arranged symmetrically, and it's riddled with crossroads (4 'ominoes meeting at a point) and other such un-aesthetically-pleasing things, but hey. It's a start!

'Sup.

So this is going to be a blog. About polyominoes and stuff, like. And sort of a sad attempt to drum up interest in polyominoes and related tiling puzzles etc. What I'd really like there to be is a sort of message board, a big central hub (like what the ConwayLife forums is for Conway's Game of Life, and the surge in breakthroughs and discoveries there in the past couple years), but I don't have the resources or know-how to get something like that up and running sadly. Or I would.

The focus of this blog is mainly going to be on constructions/rectangle-packing/making pretty shapes with the bog-standard polyominoes and other related polyforms. Most of which will be reinventing the wheel, but since existing information on this kind of stuff is scattered haphazardly around the internet or on sites and newsletters that are impossible to get a hold of anymore, it's tricky to say.

Figure 1 - The end product of an exciting, action-packed, well-spent evening

Here's the hexominoes in a 10x21 parallelogram. It's not really the kind of thing anyone's going to get excited about in any way (or even give half a toss about really, let's be honest here) but you can't just go straight in at the deep end knocking out sprawling enneomino constructions without getting a bit of technique down first. And this was a way of getting the technique down. The sacred art of "saving the bigger blockier more co-operative bits for last". Which I can't do because I'm impatient. I see a rectangle-shaped gap emerging, I stuff the rectangle there - who cares how much of a ball-ache it's going to be at the end, when I'm stuck with a handful of chronic wigglers and no way of making them behave.