Tag: common superforms

Cell colorings

~ munizao ~ Leave a comment

Most of my previous polyform coloring explorations involve map colorings of complete polyforms, i.e. colorings that adhere to the rule that no two adjacent shapes have the same color. We can color the cells of a grid instead; for example, a checkerboard is a two-coloring of the regular square tessellation, and checkered polyomino tiling problems have a long history. But for this post I want to look at problems where finding a coloring is part of the solution, rather than the coloring being given in advance.

Quite a while back, I used cell colorings for a couple of minimal common superform problems. Below, the cells of the figure on the left have been colored so that each of the 12 pentominoes occurs exactly once containing cells of all five colors. (For the common superform problems in this post, I am copying out the individual pentominoes on the right, to make it easier to see that they have a valid coloring for the problem.)

In the following figure, three colors are used. If a pentomino contains cells of two of those colors, there are 12 different color proportions possible. The figure contains each pentomino exactly once containing two cell colors, and each color proportion occurs once.

Both of these are solutions I found manually, so you may be able to find smaller figures with the desired properties.

With four colors, there are 12 ways to combine them in a 2:2:1 proportion. We could try to find a 4-colored pentomino tiling where we could overlay a second pentomino tiling so that each color combination occurs in one pentomino. The graphic below is the result of a little exploratory noodling. I just picked a tiling at random, and then tried to see how far I could get with overlaying a second tiling without repeating a color combination or using one that is not 2:2:1. Getting 8 on my first try makes me optimistic about a solution existing.

There’s nothing special about 2:2:1, either. Any proportions of the form a:a:b:c will give 12 combinations. (Zeros being implied.) So 3:1:1, or even 3:2 or 4:1 might be possible.

Problem 55: Find a pair of overlapping pentomino tilings of a rectangle where the first is 4-colored, and the second is cell-colored so that all color combinations with given color proportions are present in a single pentomino. And if that’s too easy, is it ever possible to take a solution to this problem, and then 4-color the second tiling so that the first has all of the color combinations?

We can also apply the complete set of color combinations concept to a cell-colored minimal common superform problem. Here’s a 23 cell superform of the pentominoes where each pentomino appears with a unique 2:2:1 color combination. Can you find a smaller one?

And that’s all I have for cell colorings for now. Coloring problems more generally are something I have come back to a number of times, and I expect to have another post or two to say on the subject as I plow through my as yet unblogged polyform material from the last year.

Maximal Irreducible Contiguous Covers

~ munizao ~ Leave a comment

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.