Archive for February, 2011

Polyiamond Minimal Succinct Covers

February 2nd, 2011

My first particularly interesting and novel discovery in the field of polyforms was what I call the minimal succinct cover problem. The basic minimal cover problem, which I introduced in a previous post, is to find the smallest shape into which a each of the polyforms in a set (e. g. the 12 pentominoes) could fit. A succinct cover is a shape or set of shapes into which each of the polyforms in a set can fit in exactly one way. Several years ago I wrote a program in Python to find minimal succinct polyomino covers, and shortly thereafter I extended it to handle polyhexes. But at the time I left off handling polyiamonds, because of the three regular planar tessellations, (square, hexagonal, and triangular) the triangular one is the trickiest to program.

Still, it was about the lowest hanging fruit around as far as results of mine to extend go, and since I recently blogged the minimal hexiamond cover problem, it seemed only natural to look at minimal succinct polyiamond covers now, so I hacked on my code to add them.

Here’s a minimal succinct cover of the hexiamonds:

Notice that the hexagon must appear as a separate piece in a succinct cover. As a result of its symmetry, whenever you add a cell to it, the resulting heptiamond will fit a couple of hexiamonds in two different ways. (The X pentomino has an analogous position in a succinct pentomino cover.)

And here’s an MSC of the heptiamonds:

(No animation here; my process for making them has a couple of manual steps, which would get tedious for larger sets.)

Notice that there are three hexiamonds in the minimal hexiamond cover, and two heptiamonds in the minimal heptiamond cover, and that all of these have some kind of symmetry. This should not be terribly unexpected; symmetrical polyforms are, in a sense, less flexible to work with because the number of distinct ways you can append a neighboring cell is reduced.

Here’s my updated Python code for solving minimal succinct polyform cover problems.

See also my extended writeup on polyform covers. (This was written before I started the blog, and I haven’t yet integrated some of my newer material.)