The Problem of Polyominoes

Have you ever started a project and found it take over your life, and have you ever started working on something only to have it lose sight of its goal and take off in unexpected directions?

A couple of weeks ago, I was sitting in a meeting feeling bored, so I started entertaining myself by trying to find the 12 pentominoes (distinct arrangements of five rook wise connected squares that are unique with respect to reflections and rotations). I knew how many there were before I started, but I wasn’t able to come up with all 12 in my head. I quickly did it on paper, but then I wondered how many hexominoes there are. This problem I tackled on paper.

The next chance I got, I started writing a program in Matlab to find all of the polyominoes of a given order. After some fiddling, I got it working for N from 1 to 6. It would drop 18 of the heptominoes.

I decided that the Matlab code was too slow, and reworked it in C++. My initial efforts were thwarted by efforts to be clever and to organize the memory in useful ways. This ended up just confusing me, and since I had found a work-around to my initial indexing and allocation problem (which may have led to the program running faster), I went back to an algorithm that was fundamentally similar to the one I used in Matlab. Sure enough, it told me that there were 90 heptominoes, rather than the correct number of 108.

A quick comparison with a published list of heptominoes indicated that I had a parameter that was too restrictive (a looser parameter would have been more robust, but would have increased run time approximately 128 fold). Upon correcting it, both C++ and Matlab correctly identified 108 heptominoes.

I then turned to optimizing my algorithm for speed. This rose out of a number of issues, primarily that I wanted to find the number of 16-ominoes and also out of a desire to be “hackish” because of my recent discovery of the Jargon File. After a day or so of intermittent tweaking, I got the 10-omino runtime down from about 2 hours to 36 seconds (it obstinately refuses to go below that). It still takes about 20 minutes for the 11-omino level to run (compared with about 14 or more hours originally), and I have yet to generate a collection of 12-ominoes (although that may change soon). My goal is to generate the 16-ominoes, but that may be beyond anything I can do.

In the meantime, I’ve been obsessed.

Also, I want to wish a happy birthday to my cousin Tami (it’s today), and a belated birthday to Gary, Pet, Karinka, Melodie, and Charlie Brown, all of whom celebrated anniversaries on the 2nd, but I was too busy and self-absorbed to remember it at the time.