Posts Tagged ‘hexiamonds’

Complete combination colorings on the torus

January 9th, 2017

I posted previously about my talk at Gathering for Gardner 12 on colorings of pentomino tilings. One unexpected consequence of that is that my work has now been cited in a very prestigious… um… coloring book. Alex Bellos and Edmund Harriss previously collaborated on Patterns of the Universe, a mathematical coloring book for adults, and were looking for material for the sequel. They were attending G4G12, and saw my talk, and thought that they had found some. They wanted to use something like the strict complete combination 3,4-coloring of the pentomino tiling that I showed, but for the purpose of a coloring book page, they needed something with more shapes to color. Could I come up with such?

It seemed to me that the problem called for a pentomino tiling of a torus, which they could use as a wallpaper-like pattern, repeated as many times as they needed. The choice of the particular torus to use is a matter of taste, but I thought it would be nice to maximize the minimum distance between two images of the same point. (I haven’t proven that I succeeded, but it’s close.) In coding the solver for this, I used a shortcut: instead of directly checking whether a given tiling had a coloring of the correct type, I checked whether each pentomino bordered exactly six others. This turns out to be a necessary condition, but not a sufficient one, so I manually checked a few such tilings until I found one that worked. This is the pattern that appears, in user-colorable form, in Visions of The Universe by Bellos and Harriss.

The hexiamonds were the other obvious set of 12 polyforms to try to tile with this coloring scheme. Here, there is one torus with maximal symmetry. Amazingly, my solver found just two tilings where every piece bordered 6 others, of which exactly one had the right coloring properties. Recall that the solution for the pentominoes on the 6×10 rectangle was also unique. It seems incredible to me that this problem type has yielded two instances that were so finely balanced as to be solvable, but only by the barest of margins.

Maximal Irreducible Contiguous Covers

April 28th, 2011

A cover of a set of polyforms is a shape (or set of shapes) into which each member of the set could fit. Mostly I’ve looked at problems involving minimizing the size of a cover. This problem goes the other direction.

A reducible cover is one where a cell can be removed and the remaining figure is still a cover. An interesting problem then is to find an irreducible cover in a single piece that is as large as possible. (Why a single piece? Well, without specifying that, the largest irreducible cover will simply be all of the shapes in the set in separate pieces.) Here’s a (conjectured) maximal irreducible contiguous cover (MICC) of the pentominoes:

The above solution has been on my polyomino cover page for a while. Here are a couple of new results, (still just conjectured since I found them by hand rather than exhaustive computer search, and I am not able as yet to prove they are maximal.)


An MICC (?) of the hexiamonds


An MICC (?) of the pentaedges (shown in two copies for clarity)

Between these solutions, we see some patterns emerging. Certain polyforms are in some sense distinctive: they have features that do not occur in other polyforms in the set. This makes it easy to make a large cover that includes exactly one copy of them. Other polyforms end up serving a connective function. For example, there are quite a few occurrences of the L pentomino in the first figure, so removing a cell will never make the cover cease to include an L. By using a few pentominoes as many times as possible in this connective function, more pentominoes are left over to occur singularly.  In some cases multiple polyforms that occur only once are forced to overlap, so we don’t get their full number of cells to add to the cover, but we do get a few. This is shown with the outlined hexiamonds above. In the case of the pentominoes, we have one cell where two T pentominoes overlap; since these are the only two T pentominoes in the figure, the cell can’t be removed from the cover.

Problem #25: Find maximal irriducible contiguous covers of anything and everything! This problem ought to yield interesting results for any kind of polyform you can throw at it.

One final note: It was slightly unfortunate that I chose the word “cover” to represent a concept in polyforms when it already had an unrelated meaning in graph theory; it’s even more problematic now that I’m using graphs themselves as polyforms. It appears that in graph theory, the appropriate term is “common supergraph”. I could use “common superform”, although one problem is that polyforms, unlike graphs, are generally not allowed to be disconnected, and for some problems (though not this one) we want sets of polyforms that aren’t connected to each other. Perhaps “common superformsets” in that case, as ugly as it sounds.

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.)

Hexiamond Minimal Covers

December 16th, 2010

I define a cover of a set of polyforms as a shape or shapes into which each polyform in the set can fit. I’ve written up an exploration of related problems on my recreational mathematics non-blog. Most of these problems use pentominoes or other polyominoes; it lately occurred to me that I had done a disservice to the hexiamonds, which are just as worthy of attention. So here’s a minimal (ten cell) cover of the twelve hexiamonds:

A proof of its minimality is simple. There are two ways that the bar and hexagon hexiamonds can be superimposed with maximal overlap:

Each of these contains nine cells, and neither is a cover of all of the hexiamonds. (The one on the left is missing the butterfly and chevron hexiamonds, the one on the right, just the butterfly. ) Therefore any cover must contain at least ten cells, so the one given above is minimal. (The nomenclature I’m using for individual hexiamonds is given on this MathWorld page.)

In fact, there are five ways to complete a cover by adding a single triangle (marked in blue below) to one of the figures above:

And these are the minimal covers produced:

The animation at the top of this post displays a cycle where a single cell is moved at each step. (I posted about this previously with the pentominoes in a minimal cover.) The hexiamonds have the handy property that their number is exactly twice their size, which leads naturally to the following problem:

Problem #16: Starting with a hexiamond with all cells labeled, find a sequence of single cell moves that cycles through all twelve hexiamonds, returning to the first hexiamond, and that moves each labeled cell exactly twice. Bonus points if the set of cells used is either a minimal cover or a 2×3 parallelogram. Bonus points as well for satisfying conditions like those of problems #10 and #11 in the post linked above. (All cells return to their starting positions, or all cells end up in a cyclic permutation of their starting positions.)