Posts Tagged ‘polyiamonds’

Stop! In the name of Octagons!

March 29th, 2014

In the spirit of the flexible rhombic cell polyominoes that I posted about previously, here’s a hexiamond tiling of eight triangular segments squashed into an octagon:

hexiamonds in an octagon

Of course, octagons can also be used as base cells for polyforms. In fact, any regular polygon (and quite a lot of other things) can be used in this way, but octagons are special. They don’t tessellate the plane by themselves like equilateral triangles, squares, and hexagons, but they do form a semi-regular tessellation of the plane along with squares. This makes polyocts behave fairly well; you won’t be able to tile something convex and hole-free with them, but you can tile something that’s reasonably symmetrical at least. For example, here’s a tiling of the 1-, 2-, 3-, and 4-octs:

polyocts-2

That’s not the most symmetry that polyocts are capable of, (full octagonal symmetry is possible) but it’s the most we’re going to get with this set of pieces. See this page by George Sicherman for some figures with full symmetry that can be tiled with various individual polyocts.

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

Hexiamonds on an Octahedron

January 26th, 2010

Here’s an interesting problem that seems not to have gotten as much attention as I think it deserves. The twelve hexiamonds contain a total of 72 triangular units. A regular octahedron with edges 3 units long can fit 9 triangles on each of its 8 faces, exactly enough to tile with the hexiamonds. Some individual solutions to this problem have been found. A solution at Livio Zucca’s site bears the label “Adrian Struyk 1963?” so we may assume the problem has been around at least since then. Another solution by Michael Dowle is here.

Notice that you can unfold an octahedron to produce a net in the form of an octiamond. This provides another source for solutions. The octahedron has 11 different octiamond nets. Pieter Torbijn found that 24 enlarged octiamonds could be tiled with the hexiamonds; of these, 5 are nets of an octahedron.

As far as I know, nobody has made an exhaustive computerized search for solutions to this problem. You can be the first!

#4: How many distinct ways can the hexiamonds tile an octahedron?

The octahedron has a large amount of symmetry compared to any planar figure that these pieces can tile. It has 48 automorphisms, or ways to map the solid onto itself. This would indicate a relatively small number of different solutions, since many solutions will be mappings of each other over the various ways of rotating and reflecting the octahedron. On the other hand, the shape lacks external borders, which ought to greatly increase the number of possibilities.

Some solutions have a piece that wraps around and caps a vertex. This could be considered an aesthetic flaw, because it would be impossible to tell which hexiamond the capping piece is just from knowing what triangles it occupies; you must also know its edges.

There are 7 different pieces that can cap a vertex, one of which, the pistol, can cap it in two distinct ways. Notice that due to the symmetry of the shape it makes when it caps a vertex, only the orientation of the sphinx is a riddle; its identity is never in question.


#5: How many solutions have a capped vertex?

#6: What is the largest number of vertices that can be capped in a solution? The ideal would be for all six vertices to be capped with all of the above hexiamonds except the sphinx.

The octahedron has twelve edges, the same as the number of hexiamonds. This suggests another problem:

#7: Is it possible to tile the octahedron so that each of the twelve hexiamonds is folded across exactly one of the edges of the octahedron?