Moves in Tilings

January 25, 2025 ~ munizao ~ Leave a comment

Early last year I became aware of a paper by Jamie Tucker-Foltz on Locked Polyomino Tilings. It defines a recombination move on a tiling of n-ominoes as creating a new tiling by removing an adjacent pair of tiles and replacing them with a pair of tiles in different positions. Locked tilings are those that admit no recombination moves. Remarkably, for both 4- and 5-ominoes, there is a unique smallest square locked tiling:

The concept of moves between tilings seemed like a promising source of puzzles. Given a tiling, we could try to find a recombination path to a different tiling with specified properties. For example, starting with a tiling of 12 P pentominoes in a 6×10 rectangle, our goal might be to make recombination moves until we arrive at a tiling with all 12 pentominoes.

But from the perspective of designing a physical puzzle, removing and replacing pieces two at a time seems unnecessarily complicated. A better puzzling experience ought to result from removing and replacing pieces one at a time. This doesn’t create a move between tilings, but works just fine as a move between packings. (In fact, sliding block puzzles can be seen as using just such a move.)

After some experimentation with various sets of polyforms, I came up with one that was very promising. There are 10 one-sided tetrahexes. We can pack 9 copies of one of them in a hexagonal figure, leaving a one-hex hole. Now our goal is to form a packing of the other nine pieces in the same frame. These pieces begin in our unused supply, and at every move, we return one piece from the tiling to the supply, and then take one piece from the supply and put it in the frame. The removed and replaced piece can be the same; there are some positions where we might want to change the orientation of a piece, moving the hole. Notice that we can never have more than one of the pieces in yellow below. This was not a restriction in the original problem from the Tucker-Foltz paper, but it seems like a reasonable one for a physical puzzle where we want to limit the production cost of the pieces.

Here are a couple of representative packings of each set. Can a chain of moves be made from a packing of the first type to one of the second? (Not necessarily the packings shown.) This is Problem #63. I got very close while trying to solve it manually, but I couldn’t get all the way there.

Finally, there was another direction I went in exploring this type of problem which was very fruitful indeed. At one point, before I tried the tetrahexes, I was having difficulty finding any polyform that might work. I decided to try the simplest set of polyforms I could come up with: one-dimensional polyominoes. Of course, 1D polyominoes can be represented as integers, and a tiling is simply an ordered list of integers.

Then I needed moves that could be made on this such a list, and a goal to be achieved by a chain of moves. The simplest moves I could think of were splitting a number into two smaller positive integers that sum to it, and merging two adjacent numbers to produce their sum. Since these moves are inverses of each other, we can backtrack through the space of lists if we need to, which is a nice feature in a puzzle. For a goal, I decided to use reversing the list, at least until I could think of something better.

Now, it’s clear that there are a couple of trivial strategies that prevent this from being any kind of puzzle at all. One is to decompose all of our integers into 1’s, and then recombine them to make our desired list. A simple rule to prevent that is to disallow making a list that contains more than one of the same integer. Another is to combine all of the list into one big number, and then split it down from there. The simple rule I found to prevent that strategy was to disallow any number greater than the greatest number in the original list. As an example, with the list [7, 2], the following chain would be a valid solution: [7, 2] → [6, 1, 2] → [6, 3] → [2, 4, 3] → [2, 7].

After playing with a few lists using these rules, I was surprised to discover that some of them made decidedly non-trivial puzzles. (And I stuck with reversing the list as a goal, as I never did come up with something better.) I wrote up the puzzle as a post on my Mastodon account. And then some funny things happened.

My Mastodon post was picked up by Hacker News, a popular bulletin board site for programmers, where it briefly was ranked high enough to make the front page. Some commenters wrote code to explore different lists, looking for ones with long minimal length solution paths. Others wrote interactive playable versions. Arthur O’Dwyer wrote a blog post about the puzzle. (Read that one for a deeper look at the puzzle and the behavior of different lists. I’m not writing that post here, because it already exists.) Tomas Rokicki submitted an integer sequence related to the behavior of the puzzle to the OEIS. I gave an informal talk about the puzzle at a Gathering 4 Gardner Zoom Social, and I started writing my own snazzy interactive version of the game. With Skona Brittain, who used the puzzle as an activity for young math learners, I presented the puzzle to a group of folks who study mathematical puzzles and pedagogy. This little puzzle that I dashed off a quick Mastodon post about has gotten as much engagement as all of my other explorations in recreational math put together.

And now I must segue to a real world concern. I am very underemployed, and I am looking for work. Part of my motivation for writing that snazzy interactive version was to have a portfolio piece to show off my skills in Javascript, React, and CSS. I am generally looking for web development positions, but I’m also interested in other software development positions. I live in the Portland, Oregon area, but I’m willing to consider remote positions.

Piling Polyominoes

May 2, 2023May 3, 2023 ~ munizao ~ Leave a comment

In my previous post I offhandedly tossed off a taxonomy of polyform positioning problems:

	No Overlap	Overlap
No holes	Tiling	Piling
Holes	Packing	Tacking

The vast majority of the problems you will find in the wild are tiling problems, with an occasional sprinkling of packings. The other side of the matrix is rare enough that it didn’t already have established terms. Piling in particular is a topic that I haven’t focused on since before the blog, so it was overdue for another look.

The earliest appearance of pentomino piling that I’m aware of is a set of problems that appeared in Puzzle Fun #7. Ariel Arbiser filled a 6×9 rectangle with 6 pairs of pentominoes that overlap in one cell, and asked if the positions of overlaps could be made symmetric. Pieter Torbijn’s solution was printed in Puzzle Fun #9:

If pentominoes overlap two different other pentominoes, you get a chain. I explored this type of problem before the blog, and wrote up some results. One problem that I set at that time was making such a chain in a 7×7 square such that every overlap cell was a knight’s move from the next. (The X and I pentominoes are the only ones that do not contain two cells a knight’s move apart, so they must be at the ends of the chain.) Recently, Bryce Herdt solved it:

Remarkably, Herdt reports that the only other solution is the one made by flipping the F so that it overlaps with the I in a different cell.

There are 12 different tetrominoes with a single marked cell. It was these that inspired me to look at overlap problems again, since, (with three T’s) they have a parity problem that makes it impossible for them to tile a rectangle. It seemed natural to ask if they could pile a rectangle with the overlaps occurring at the marked cells. Herdt found a symmetrical solution:

Herdt noted that this is the only type of symmetry that a solution can have. If a piling had vertical reflection symmetry or rotation symmetry, it would have unworkable parity.

There are 20 tetrominoes with two marked cells. These are the tetrominoes in Kate Jones’s Fill-Agree puzzle. They could make chains, ~~and should not have any parity issues.~~ (Edit: There is, in fact a parity issue. There is an odd number of pieces where the marks have opposite parity. Since the chain must end on the same checkerboard color it begins on, we can’t close the loop. Thanks to Bryce for pointing this out.)

Problem 56: Pile a ~~6×10 rectangle~~ 5×12 torus with the tetrominoes with 2 marked cells, such that overlaps only occur on the marked cells, and the overlaps form a single circuit containing all of the pieces.

Is there more that we can do with polyomino piling? Will tacking be useful for future puzzles? Will I stop trying to make “piling” and “tacking” happen? Stay tuned for the answers to these questions and more! (Well, more silly questions, at any rate.)

The Pentominoes My Destination

February 25, 2023 ~ munizao ~ Leave a comment

Usually, the pentominoes are the raw material of a problem, not its end point. Here are a couple of puzzles that turn the usual order on its head.

I.

With Gathering for Gardner 12 approaching in 2016, I was looking for things to do with the pentomino theme. (I’ve posted previously about my pentomino coloring talk and what led from it.) I had come up with a puzzle with 12 separate frames, each with space for a pentomino, and two sets of 12 puzzle pieces. Each set was in a different color, and the object of the puzzle was to fill all of the frames with two pieces of the same color. I made a copy out of lasercut wood, and brought it to the Gathering.

At the Gathering’s offsite “garden party” I commandeered a table a little bit away from the main crowd. (I have auditory sensitivity issues that become a problem in loud, crowded spaces.) I set out the pieces and frames, and hoped I would get some takers. I was incredibly lucky that one of them was none other than Richard K. Guy! I tended to be shy at these conferences about approaching the “old guard” who knew Martin Gardner as a peer. We have lost many of them, including Guy, John Horton Conway, Raymond Smullyan, and Solomon Golomb, in the years since this picture was taken. This was my only substantial interaction with Guy, and I’m very thankful to have the memory.

I discovered that a puzzle with multiple frames had very interesting effects on the collaborative dynamics of group solving. Everyone could pick a frame to work on separately, so there was no confusion as to which parts were “owned” by whom. Unused frames and pieces could be picked up by anyone without fear of stepping on anyone’s toes. Sometimes a player would require a piece that was already used in a different frame, and they would ask its owner for it. Everyone was working toward the same final goal, so they would always be willing to share. I saw the same patterns when three different groups worked on the puzzle that day, and I believe that the delineation of responsibilities that emerged from the multiple frames helped all of the players feel ownership of an important role in solving the puzzle.

Here is the set of pieces. The size of each piece is 2½ unit squares. I wanted to have two copies of six different pieces, but that didn’t work, so there are two singletons per set.

Although the puzzle as designed requires two pieces from the same set in each frame, an obvious alternate puzzle would be to have each frame use one piece of each set. I haven’t tried it though, so I don’t know if that challenge is a good puzzle, or even solvable.

II.

I’ve recently been looking for light puzzles with small piece sets that might make good exchange gifts for Gathering for Gardner. Taking the 1½- and 2½-ominoes and giving them every possible choice for marking any of the (full) cells with a square yields 6 pieces, with 5 squares, and an area of 13. Well, 5 squares means I’m going to have to do something with pentominoes. And an area of 13… well, that’s just awkward. But I was inspired by Tick Wang’s Tans Dance, along with other puzzles I saw on the Nothing Yet Designs site where the goal is not to make a particular shape, but to make any symmetrical shape.

And that’s the puzzle. Take these pieces and make a symmetrical shape (either rotation or reflection symmetry is fine) where the blue squares form a pentomino. Now do it again for the other 11 pentominoes. All of them are solvable! Most of them, individually, are not too hard, but with 12 challenges, it should keep someone busy for a few minutes.

What I like about this puzzle is that the symmetry goal makes the squareless pieces relevant, and including the squareless pieces makes the pieces a more complete and elegant set. Will it be my exchange gift for the next G4G? I think it’s too early to say yet. I try to pick an idea at about six months prior to the conference. This tends to give me a timeline where I have plenty of time for design, prototyping, ordering materials, and assembly, with some cushion if my first idea doesn’t pan out. I’ll still be on the lookout for more good light puzzles. After all, having lots of ideas to choose from for one’s exchange gift is the best way to ensure you find a really good one!

(A final aside: you might notice that there are two ways to make a half-omino. You can cut parallel to the grid, as I did for both of these puzzles, or you can cut a square diagonally. For the first puzzle, diagonal cuts were out, because the T pentomino cannot then be split into two 2½-ominoes. For the second puzzle, I considered diagonal cuts first. That version of the puzzle does actually also work, but often, you get to a point where you have the puzzle basically solved, but you have to do some fiddly piece flipping so that the right triangle ends give a symmetric figure.)

Cell colorings

February 4, 2023February 25, 2023 ~ 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.

Rebels of Flexible Polyforms

January 9, 2023 ~ munizao ~ 3 Comments

After the last two flexible polyform posts, I had a couple of misfit tilings left over, rebels that didn’t want to fit into a larger theme. But they reminded me that creativity is itself a rebellion; to create something novel, we must set ourselves apart from the paths followed by others.

A lot of creativity is mixing existing ideas in ways nobody else has yet thought to mix them. That’s much of what I try to do in recreational mathematics in general, but in polyform tilings there is a more literal sense of mixing: combining different types of shapes within the same tiling. Previously I tried mixing different symmetry variants of polyominoes. With flexible polyforms, we can mix polyforms with entirely different base cells, since distorting angles can allow them to become compatible. Here is a tiling of flexible pentominoes together with the hexiamonds:

Another creative tool is tweaking magnitudes of qualities. We can turn one negative, and ask what it’s opposite might mean, or what happens if we reverse a process. Or we can tweak a knob the other way toward an extreme. We already do that with flexible polyforms when we ask, “Can we get more symmetry by squeezing more repeated segments around the center?” We can also ask, “What would it mean to make flexible polyominoes even more flexible?” Here’s one answer:

As it happens, my motivation for finding this was seeking a different extreme. I wanted to find the “best” possible shape to tile with flexible polyominoes. There is no clear definition for “best” here. More symmetry is nice, but so is convexity and a smooth border. Regular polygons seem good if you can pull them off. (Previously, we managed to squeeze the hexiamonds into an octagon.) So I started with a regular pentagon, and looked for a good way to subdivide it into 60 cells, and ended up with the scheme used above.

And with that coda, I conclude my series on flexible polyominoes. I’m sure there is much more out there to be found, but for now I’ll be searching elsewhere for new and fun ideas.

Revenge of Flexible Polyominoes

September 28, 2022 ~ munizao ~ Leave a comment

Several months ago, I felt myself at a bit of a creative ebb. I wasn’t coming up with any bold new polyform ideas, so the best I could do would be to tinker around in a space that was already well-trodden. In this state of mind, I asked myself: did Abaroth miss anything good?

When I came up with the idea of letting the cells in polyominoes be flexible rhombi, Abaroth ran with it, and made an entire gallery of tilable shapes with solutions. Some of Abaroth’s discoveries used rows of squares as seams between the “leaves” of a target shape, but he missed this nice pentomino star:

An obvious thing to want after seeing a tiling like this with five-fold dihedral symmetry is one with sixfold dihedral symmetry. So far, the attempts have run into some problems.

The tiling on the left is Abaroth’s. It contains a couple of ambiguous pentominoes in the upper right. Where the green one wraps around a degree-3 vertex, it could be “unglued” to form either an X or an F pentomino. The red one could be an L, an N, or a Y.

The tiling on the right is mine, and has a different problem. The P pentomino in the upper left is not ambiguous, but it is split. This type of flaw can only occur in a polyomino that contains a square tetromino; P is the only pentomino that does.

Problem #53: Find a flexible pentomino tiling with sixfold dihedral symmetry without ambiguous or split pentominoes.

One-sided flexible polyominoes were another area that had been missed. It turns out that there are some nice tilings here:

George Sicherman, Abaroth, and Edo Timmermans all found one-sided pentomino tilings for the above double star. This double balanced three-coloring found by Edo Timmermans is particularly nice. Remarkably, the one-sided hexominoes also admit a double star:

It might not be clear at first that other symmetry variations on polyominoes will survive in this weird flexible world, but in fact some can. If squares can flex into rhombi, then rectangles can flex into parallelograms, and we can get tilings like the following, using the 3-, 4-, and 5-rects:

For the second post in a row, I’m going to stop with at least another post’s worth of material left to share. If I leave you in suspense, you’ll have to keep coming back, right?

The Rune Where It Happens

February 7, 2022April 7, 2023 ~ munizao ~ 4 Comments

A while back, I was finalizing my drawing files for laser-cut frames for my Cross Products puzzles, which I was intending to sell at Gathering for Gardner 13. I wasn’t happy with just wasting the material in the center of the frames, so I looked for a simple idea that would make use of it. The shape that was being cut out was a rectangle with a 3:4 aspect ratio. I could cut that into 12 squares, and then engrave something on each of them. Now what might there be 12 of?

It will probably not surprise anyone here that my mind went straight to the pentominoes. Tiles with pentominoes could be useful for choosing one at random. (Sure, I already owned a 12-sided die with the pentominoes on it, which I bought from Eric Harshbarger, but with tiles one could select without replacement, or even effectively shuffle an ordering of the entire set.)

The tiles I made for my G4G13 exchange gift didn’t have these fancy swirled colors.

The tiles reminded me of rune stones, with the pentominoes forming a cryptic alphabet. I thought it would be amusing to make sets of them my exchange gift for G4G13, along with a slip that instructed the user on how to use the arcane power of the pentominoes to divine the future. It would be the kind of playful deadpan jab at ungrounded mysticism that Gardner’s alter ego, Dr. Matrix, might have enjoyed making. But to really justify the effort, it couldn’t be just that. I’d need to include some activity using the pieces that would have genuine recreational math interest. Perhaps a puzzle.

What I found was a variation on the common superform framework that incorporated squares with pentomino runes. The basic common superform problem is to find a figure into which any of the polyforms in a set can be placed. Usually, the object is to minimize the area of such a figure, but in this case, the area will be set by each particular challenge using the pieces. We add a couple of restrictions:

Each set of five tiles that forms a pentomino must contain the corresponding rune.
Each rune must be contained in at least one set of tiles that forms that pentomino.

The above figure was included as an example on the instruction sheet. The challenges provided were to find a valid tile arrangement using nine of the tiles, to do so with all of the tiles but one, and to do so with the complete set. Remarkably, this is possible!

Show Solution

I’ve since looked for other sets of polyforms that are able to make valid rune configurations with a complete set. Here are the tri-diamonds:

And here are the tetrahexes:

Can you find others?

Incidentally, at G4G13, I gave a few pentomino readings to fellow conference goers, one of whom reacted with cheerful amusement, and another with stony skepticism. Honestly, I could not have hoped for anything better.

Flexible pentominoes on rhombic polyhedra

February 26, 2018 ~ munizao ~ Leave a comment

If you subdivide the faces of a rhombic triacontahedron into 2×2 grids, you can tile the polyhedron with two copies of each pentomino.

One way of looking at this figure is as a tiling of the projective hemi-rhombic triacontahedron. The projective (also known as abstract) polyhedra can be formed by identifying the opposite faces of certain polyhedra with each other. So the projective hemi-cube has three square faces, and the projective hemi-rhombic triacontahedron has 15 rhombic faces. Stitching together the opposite sides of the unshaded area in the figure is a way to form this 15 face “polyhedron”.

I came up with that one a couple of years ago, but I neglected to put up a blog post because I didn’t like the graphic enough. I suspect that it’d look really cool if the lines of the rhombic triacontahedron were properly projected onto a flat disk, but I don’t have the expertise to make that happen. I finally decided that it was worth sharing even if it doesn’t look as cool as it could.

Below is another tiling of subdivided rhombi. The significance of this figure is that four copies could be used to cover a rhombic hexecontahedron.

Vexed by Convexity, part one

February 2, 2018 ~ munizao ~ Leave a comment

Last September I came across a conversation on Twitter about how convex the 12 pentominoes are. At first glance, this might seem like an uninteresting problem. Clearly, the I pentomino is convex, and the rest aren’t. (Recall that a shape is convex if, for any pair of points inside the shape, the segment connecting them is entirely within the shape. Otherwise, we call it concave.)

But the problem wasn’t whether the pentominoes are convex, but how convex they are. In order to answer that, we’d like a measure that gives 1 for a shape that is convex, and ranges between 0 and 1 for concave shapes, getting higher as they more closely resemble some convex shape.

There are several measures that work. (For a discussion of convexity measures, see this paper by J. Zunic and P. Rosen.) One strategy for measuring convexity is to consider a shape in relation to its convex hull. A shape’s convex hull is the smallest convex shape it is contained in. Naturally, a convex shape is its own convex hull. The ratio of the area of a shape to that of its convex hull makes a reasonable measure of convexity. Or instead of areas, we could instead look at perimeters. The perimeter of a shape can never be less than that of its convex hull. So the ratio of a shape’s convex hull’s perimeter to that of the shape itself can also be used as a convexity measure.

Another method of measuring convexity is the probability that the segment between two points in a shape chosen at random lies entirely within the shape. Finding exact values for this measure can involve some tricky math, which Dan Piponi worked through for the P pentomino. However, calculating an estimate by randomly picking a large number of pairs of points is also an option. And, as it happens, Rod Bogart did exactly that.

The following table shows the convexities of the pentominoes according to each of these three measures.

Pentomino, shown with convex hull	Area / Convex Hull Area	Convex Hull Perimeter / Perimeter	Probabilistic method
	.7143	.8387	.786
	1	1	1
	.7692	.9302	.822
	.7692	.8875	.778
	.9091	.9414	.946
	.7143	.8726	.788
	.8333	.8333	.708
	.7143	.9024	.748
	.7692	.8536	.772
	.7143	.8047	.840
	.7692	.8875	.854
	.7143	.8726	.720

Convex hull area method data by Vincent Pantaloni. Convex hull perimeter method data mine. Probabilistic method data by Ron Bogart.

Even though these shapes are pretty simple, the data above shows that the different convexity measures treat them differently in interesting ways. Notice that the X pentomino, for example, is tied for the least convex pentomino by the convex hull area method, but is the fourth most convex by the probabilistic method.

I hope I’ve shown that convexity, as applied to polyominoes, is more interesting than it might have seemed! In part two, I’ll look at how we can use these convexity measures to make some new puzzles.

Pentominoes on paths and trees

February 3, 2017 ~ munizao ~ 1 Comment

Here’s a path that could be taken by a chess king. All subpaths of length four describe a different pentomino:

A pentomino train

This led from the grid of pentomino painting instructions that I posted previously. Consider a string of arrows for which the subsequences of length 4 include instructions for producing all 12 pentominoes. (This is somewhat analogous to a de Bruijn sequence.) For the case shown, the string is ←↑↖→→→→↓↓←↓←↘↗↓, although the graphic seems more illuminating than the arrow string here.

Instead of a path, we could have a tree of pentominoes:

Along with the constraints that each pentomino occurs exactly once, and no square is used more than once, I wanted to limit the number of branches per node. The root node having three branches might be considered a flaw, but this was the best I could do.

Pentomino Painting Robots

February 1, 2017February 1, 2017 ~ munizao ~ Leave a comment

In the diagram below, each row (reading from left to right) and column (reading from top to bottom) gives instructions for painting one of the 12 pentominoes:

Sometimes an idea languishes in one of my notebooks for a few years before I can come up with the right iteration of it. My original idea here was to use a 4×4 grid. That would give me 8 pentominoes, (perhaps 10 using diagonals) but elegance surely requires all 12 to be present.

A combination of circumstances led me back to this problem. Some friends of mine have a tradition of playing RoboRally on New Year’s Day every year. This is a board game where you use cards with arrows on them to instruct your robot to move around a grid of squares. Also, in returning to the magic 45-omino problem, I was considering grids that could be used in sparse magic squares.

It might be possible to make an interesting grid puzzle, along the lines of sudoku, using this kind of grid as a basis. Most of the grid would start empty, except for a few squares in which arrows would be given at the start. Then the solver would fill in the rest of the grid by logical deduction so that the horizontal and vertical lines contain instructions for paining all of the pentominoes as above. Since the grid would have significantly fewer squares than a sudoku, this puzzle might be quicker to solve, but that doesn’t mean that it would necessarily be less interesting.

Complete combination colorings on the torus

January 9, 2017January 14, 2017 ~ munizao ~ Leave a comment

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.

The Happiest and Saddest Tilings

June 15, 2016April 16, 2023 ~ munizao ~ Leave a comment

(Tagging under “A Polyformist’s Toolkit”, as I feel that series ought to have an entry on coloring, and this more or less says what I have to say about that.)

At Gathering for Gardner 11 in 2014, I gave a talk about crossed stick puzzles. It was the obvious thing to talk about, since I had been making a lot of interesting discoveries in that area. Unfortunately there was too much good stuff, and I couldn’t bear to trim very much of it out, so I made the classic mistake of going over on time and having to rush the last slides. (G4G talks are generally limited to 6 minutes.) When I was looking for a subject for this year’s talk, there was nothing I felt an urgent desire to talk about. This would be the 12th Gathering for Gardner, and there is a tradition that using the number of the current Gathering, either in your talk or your exchange gift, is worth a few style points. Since I’m a polyformist, and Gardner famously popularized the twelve pentominoes, revisiting some of my pentomino coloring material seemed reasonable.

Finding interesting map colorings is a nice puzzle that we can layer on top of a tiling problem. A famous theorem states that all planar maps can be colored with four colors so no two regions of the same color touch. Since this can always be done, and fairly easily for small maps like pentomino tilings, we’ll want some properties of colorings that are more of a challenge to find. I know of three good ones:

Three-colorability. Sometimes we only need three colors rather than four. For sufficiently contrived sets of tiles we might only need two, but for typical problems that won’t work.
Strict coloring. For most purposes, (like the Four Color Theorem) we allow regions of the same color to touch at a vertex. If we do not allow same colored regions to touch at a vertex, we call the legal colorings strict. Notice that a 3-coloring of polyominoes is strict if and only if it contains no “crossroads”, i.e. corners where four pieces meet.
Color balance. If the number of regions of each color is equal, a coloring may be considered balanced. Conveniently, 3 and 4 are both divisors of 12, so we can have balanced 3-colorings and 4-colorings of pentomino tilings.

The above information would make up the introduction to my talk. It would also, suitably unpacked and with examples, take up most of the alloted time. That left little enough room to show off nifty discoveries. So whatever nifty discoveries I did show would serve the talk best if they could illustrate the above concepts without adding too many new ones. One that stood out was this simultaneous 3- and 4-coloring with a complete set of color combinations, discovered by Günter Stertenbrink in 2001 in response to a query I made on the Polyforms list:

5-omino-6x10-happiest

This is the unique pentomino tiling of a 6×10 rectangle with this property where the colorings are strict. I used it to illustrate 3- vs. 4-coloring by showing the component colorings first, before showing how they combine. To my astonishment, the audience at G4G12 applauded the slide with the combined colorings. I mean I think it’s pretty cool, but I consider it rather old material.

I still wanted one more nifty thing to show off, and while my page on pentomino colorings had several more nifty things, none of them hewed close to the introductory material, and the clever problem involving overlapping colored tilings that I was looking at didn’t seem very promising. Setting that aside, I wrote some code to get counts of the tilings of the 6×10 rectangle with various types of colorings. That gave me the following table:

	Total	Balanced
4-colorable, non-strict	2339	2338
4-colorable, strict	2339	2320
3-colorable, non-strict	1022	697
3-colorable, strict	94	53

What stood out to me was the 2338 tilings with balanced colorings. Since there are 2339 tilings in total, that meant that there was exactly one tiling with no balanced coloring:

5-omino-6x10-saddest

Notice that the F pentomino on the left borders eight of the other pentominoes, and the remaining three border each other, so there can be at most two pentominoes with the color chosen for the F, and no balanced coloring can exist. A unique saddest tiling balancing out the unique happiest tiling was exactly what my talk needed. Now it had symmetry, and a cohesive shape. Having important examples all using the 6×10 rectangle removed the extraneous consideration of what different tiling problems were out there, and helped to narrow the focus to just the coloring problem. Anyway, I don’t want to go on any more about how awesome of a talk it was, (especially because video of it may eventually go up on the internet, which would show how non-awesome my delivery was) but it was my first G4G talk that I was actually proud of. The slides for the talk are here.

One thing I’m curious about that I didn’t mention in the talk: has anyone else found the saddest tiling before me? Looking through old Polyform list emails, I found that Mr. Stertenbrink enumerated the 3-colorable tilings of various types (essentially, the bottom half of the table above) but not the 4-colorable tilings. From the perspective of looking for the “best” colorings, it makes sense to focus on the 3-colorable tilings, but it meant missing an interesting “worst” coloring.

Some Contributed Solutions

October 2, 2013July 6, 2015 ~ munizao ~ Leave a comment

I’ve had a few solutions sent in recently, so I wanted to share them with you all.

First, Abaroth noticed that my rhombic-cell pentomino tiling had just enough space to fill out into a five pointed star if the tetrominoes were also included:

But that was just the beginning! He then proceeded to produce an entire collection of tilings with these pieces, which he calls flexominoes. One problem that can come up in tilings of this sort is that if there is a vertex with three rhombi around it, a polyomino containing all three rhombi has an ambiguous identity, since there is more than one way to “unglue” the polyomino at that point. I contributed an ambiguity-free solution to one of the patterns Abaroth found:

Speaking of rhombuses, Abaroth has been investigating color-matching puzzles using rhombic tiles. His puzzle page has more interesting material on color matching puzzles and symmetrical polyhex tilings.

Next up, George Sicherman sent in a symmetrical tiling for the flexible tetrarhombs:

What’s interesting here is that although the outline of the tiling is symmetrical, the pattern of the cells isn’t. The lesson here is that being able to trade off some cell-level symmetry for more pattern-outline symmetry can give us a little variety in our choices of what we can tile.

Finally, Bryce Herdt provided a de Bruijn sequence of invertible length 5 binary words. (That is, a cyclic sequence where each word occurs once as a substring.) Since he did so in text format, I made a visualization:

Tag: pentominoes