Tag: polyiamonds

Stripe Club

~ munizao ~ Leave a comment

I posted last year about a path puzzle using polyiamond tiles. Those tiles were marked with a complete set of paths between cell edges on the perimeters of diamonds and triamonds. Recently I’ve been exploring a variation on tiles with marked paths. In these tile sets, the paths are constrained to straight lines aligned with the grid and connecting the midpoints of opposite cell edges. By this scheme, there are 16 ways to stripe the tetrominoes. I wasn’t able to come up with any elegant tiling using just these pieces, but with a set of unstriped trominoes, they can make a rectangle with four stripes. We follow the typical rule of path puzzles: the stripes must connect between pieces.

There are nine distinct ways to stripe the three trihexes. There is an arrangement of parallel stripes on the figure below that looks like it could have a solution, but it proved to have none when I checked it with a solver. Luckily, non-parallel stripe lines are perfectly acceptable — as long as their intersections occur outside the tiling!

Striping polyiamonds brings a new complication: the line connecting cell edge midpoints is not perpendicular to the cell edge. That means we can change the direction of paths at piece boundaries. The solution below takes advantage of this feature:

Fortuitously, the striped 2-, 3-, and 4-iamonds together contain 49 triangular cells, allowing us to tile a triangle of side length 7. The striped 4-iamonds alone contain 36 cells, but they are not able to tile the triangle of side length 6.

Where else can we go with stripe problems? Todor Tchervenkov, Roel Huisman, and Edo Timmermans looked at tetrominoes with diagonal stripes on the Puzzle Fun Facebook group. (There are 17, which makes them awkward for tiling with the full set, but there are workarounds.) We could try other stripe orientations on polyiamonds and polyhexes as well. Polytans (or polyominoes with tans added or subtracted) could have line bends at diagonal boundaries similar to what happened with the polyiamonds. Another variation I’m looking at is what can be done with multiple stripes per piece. Stay tuned for more stripe content! (Does that count as a stripe tease?)

Border Marking

~ munizao ~ Leave a comment

This might, at first glance, appear to just be a random tiling of a bunch of dominoes and trominoes.

But what would be the point of such a thing? In fact, it’s a complete* set of dominoes and trominoes where edges may be marked, and the marked edges are exactly the ones that can occur on the border of this tiling. That thick rectangle around the tiling is part of the pieces!

*There is, in fact, one more tromino with markings that could fit in that rectangle. But if we included it, there would be a single cell in a corner that would be unfillable, since we’ve specified that the tiling has only dominoes and trominoes. Therefore, by the rule of exclusion of things that would be awkward to keep around, it has to go.

That this works at all, even with this minor fudge, feels like a pretty bit of luck. Not only do we have a perimeter and area that are compatible, we have exactly the usual number of corners for a rectangle.

With polyiamonds, I thought my luck ran out. No combination of sizes gave me compatible perimeter, area, and corners. But when I abandoned corners entirely, and focused on pieces with only one marked side, I found that a parallelogram with opposite sides marked could be made using the 2-, 3-, and 4-iamonds. Since it wouldn’t do to have any unmarked edges lying bare to the outside world, I wrapped that parallelogram into a cylinder:

And here are the pieces individually:

Sometimes when I have a novel polyform puzzle idea, I feel like I’m tapping into a rich vein of possibilities. Here, I’m not so sure. The problem is that when you move up to sets with larger sizes of polyforms, the area and border segment length are unlikely to scale in a way that gives you tilings with completely marked borders. But I would love to be surprised!

Three paths to pick from, part 1: A compact gem

~ munizao ~ Leave a comment

I’m going to be sharing a few different puzzles I’ve discovered that share the theme of path building. The first is a pretty polyiamond puzzle I recently prototyped; the other two have been split into a second post.

Path puzzles are a natural extension of edge matching. Instead of just marking edges in some way so that we can match like markings, we can choose and connect any pair of edges. Then we can make challenges involving the paths spanning multiple tiles that are formed. I’ve examined cell markings on polyforms a fair amount here, but I’ve left edge markings understudied. One reason is that the combinatorial explosion of possibilities can become overwhelming. The L-tetromino (to pick a simple asymmetric example) has 16 different cell markings if each cell can either be marked or not. Kadon sells this set in an 8×8 square frame as L-Sixteen. Since the L-tetromino has 10 edge segments, there are 2^10 = 1024 different markings if we do the same with the edges. If someone made this, it’d need a 64×64 square frame!

Cell markings also work for path puzzles! (Adapted from here.) Not shown: 4096 square unit monstrosity.

It’s probably little surprise then that most puzzles involving edge markings use simple squares or hexagons. But recently, when I was looking for something to do with diamonds and triamonds, I found a nice set for a path puzzle.

But first, an aside on why I was looking at diamonds and triamonds. My recent puzzles with row and column pip sum challenges used multiple copies of small polyominoes with different markings. The ability to exchange copies of the same shape usefully inflates the size of the search spaces for those puzzles. But tile placement remains an important aspect, even if the finding a tiling is easy, so it still has the feel of a polyform puzzle. In a sense, these puzzles “punch above their weight” in terms of the amount of puzzle you get for the size. I wanted to find other puzzles like this, and started to look at polyiamonds. For small polyiamonds, a hexagon of side length 2 seemed like the ideal frame.

There are a number of ways to divide up the 24 cells of that hexagon, but 3 diamonds and 6 triamonds was a top candidate. I tried magic pip sum puzzles first with mixed results, but then I checked the ways to connect edge segments and found that I got exactly 3 diamonds and 6 triamonds. And making paths with them is indeed a nice manual puzzle.

After I came up with this I was curious about which exits from the hexagon it is possible to get to from a given starting point. The darker triangles overlaid on that diagram give a clue: the number of transitions between dark and light squares must always be the same, however the pieces are placed. This means that the path must always enter and leave the hexagon at triangles of the same color, so only the positions marked 1, 4, 5, and 8 are possible exits if you start at the ★. Solutions do exist for each. (Positions marked with the same number give equivalent paths by symmetry.)

I later produced a lasercut acrylic prototype of the puzzle. Here it is:

One change I’d like to make for a production version would be to cut a circle in the frame around the hexagon so that the whole puzzle can be easily rotated, allowing the ends to match the symbols. As it is, you might find a solution that connects “wrong” edges, and it’s a pain to take the pieces out and put them back in the right orientation.

In future posts, I can promise not only more path puzzles, but also another “compact gem” of small polyform sets with big puzzling possibilities.

Component Colorings II: Diamonds and Triamonds

~ munizao ~ 2 Comments

Here’s a nice coincidence: the numbers of tri-diamonds and di-triamonds are both 9, which is the right amount to tile a regular hexagon of side length 3. And both sets can! Behold the di-triamonds:

3-coloring the triamonds here isn’t hard. The tiling seems to want to have a bunch of points where four triamonds meet, which disrupts chains of forced colors. The challenge is adding more challenges on top of 3-coloring. I suspect that there is no strict 3-coloring of the triamonds. One possibility is a sort of meta-coloring of the di-triamonds where no two di-triamonds with the same color pair may be adjacent. The above diagram doesn’t qualify because there are blue-red di-triamonds touching each other. Problem #60: Find such a meta-coloring.

The diamonds in the tri-diamonds are even easier to 3-color. Enough so that 3-coloring them so each tri-diamond has all three colors (the equivalent of the poorly thought out problem #58 with the tri-dominoes) was no challenge at all. Perhaps there is something to be done with symmetry. Notice that, ignoring color and the tri-diamond outlines, the diamonds in the figure below have an an axis of reflection symmetry. I wonder if, for some tiling, some form of symmetry on the diamonds is possible where colors are included.

The meta-coloring idea above suggests a way to salvage Problem #58. Instead of a three coloring of the dominoes in a tri-domino tiling, we could look for a 4-coloring of the dominoes where every tri-domino contains 3 of the 4 colors, and there is simultaneously a meta-4-coloring of the tri-dominoes where no two adjacent tri-dominoes are missing the same color.

Rescued by Flexible Polyominoes

~ munizao ~ 2 Comments

See the previous Flexible Polyomino post here.

One unfortunate lesson that you quickly learn about tiling problems involving a full set of (free) n-ominoes is that the pentominoes are the only really nice set. Monominoes through trominoes are trivial. And tetrominoes and hexominoes have checkerboard parity problems. Here’s an example. Suppose we wanted to tile a figure containing five copies of a 6×7 rectangle with the hexominoes. (It might be a 30×7 rectangle, or a 35×6 rectangle, or something more fanciful.)

These rectangles (suitably checkered) have an odd number of both black and white squares, and since an odd times an odd is odd, so do five of them. But 11 hexominoes are “even” (they will always cover an even number of both black and white squares) while 24 are odd (they cover an odd number of squares of each color.) Since an even number times an odd number must be even, there must be an even number of squares of both colors in both the even and odd hexomino subsets, and thus also in the full set. So our figure is impossible to tile.

But flexible polyominoes come to our rescue. This figure, formed from five of the above rectangles with a little distortion, can be tiled with hexominoes!

Why does it work? Well, consider what it would mean to checker the underlying cells. There is a cycle of five cells around the center. If you color one of the cells white, then as you go around the center, the next cells would be black, then white, then black, then white again. But the following cell would be the one where we started, and it would have to be black! So you can see that whenever we have an odd cycle of cells, we can’t have a consistent 2-coloring, and the checkerboard parity argument above no longer applies.

Note that there’s no magical property of flexible polyominoes involved here, just the presence of an odd cycle. The following figure has no odd cycle, so checkerboard parity applies, and it turns out to be untileable with the hexominoes.

Checkerboard parity problems can only occur with sets of even-sized polyforms. Our next odd size is the heptominoes, but here a new problem emerges. One of the heptominoes has a hole:

Thus every heptomino tiling must either incorporate a hole or omit the holey heptomino. Either solution is inelegant. Flexible polyominoes rescue us once again!

Solution by Edo Timmermans

The holey heptomino is there, but the hole is not. Can you find it?

Once you move to the octominoes and beyond, “opening” a holey polyomino can require breaking a connection between cells, so we’ll stop here. But the 9-iamonds, like the heptominoes, have a single holey piece where the hole is pinched together with disconnected “fingers”.

Problem 54: Tile this figure with the flexible 9-iamonds. There are 160 9-iamonds, which brings us into the zone where we’d want a pretty efficient solver in order to make headway.

This gets us through most of the 2022 Flexible Polyform Renaissance material that I wanted to post, but there is still enough for a brief coda, which I hope to complete soon.

Isolating small pieces: submitted solutions

~ munizao ~ 1 Comment

A couple of submitted solutions on the theme of isolating small pieces in tilings of polyominoes of mixed sizes:

George Sicherman solved problem #44. (Tile a certain torus with the 1–5-ominoes such that the 1–4-ominoes do not touch each other. Finding a solution where none of the smaller pieces even meet at corners was optional, but well appreciated!) This solution contains four “crossroads”, or points where four polyominoes meet. These are sometimes considered an aesthetic flaw in a polyomino tiling, and whether or not you agree with that, finding solutions without them tends to be good for an extra challenge.

Problem #44a: find a solution for problem #44 without crossroads.

Jaap Scherphuis analyzed this challenge that was included with my Agincourt puzzle: find a tiling of an 8×8 square where none of the dominoes and trominoes touch each other or the outer edge. He found that there were 32 solutions. In just one of these, none of the smaller pieces meet at a corner:

I don’t feel that I acknowledge other puzzle creators enough in this space, so I want to give a shout out to Kadon for their Mini-Iamond Ring puzzle, which contains all of the 2–5-iamonds, and includes as a challenge isolating all of the different sizes of pieces:

Stop! In the name of Octagons!

~ munizao ~ Leave a comment

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

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

Polyiamond Minimal Succinct Covers

~ munizao ~ Leave a comment

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

~ munizao ~ Leave a comment

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

~ munizao ~ 5 Comments

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?