Author: munizao

Extremal Structure-Excluding Polyforms

~ munizao ~ 1 Comment

Here’s a problem that Ed Pegg posted on the Puzzle Fun Facebook group recently: how large can a polyomino be where no line connects four cells? (Diagonal lines in any direction count, and we require the lines to pass though the centers of cells, for this problem and all that follow.)

This turns out to have been an old problem, which was included in Rodolfo Kurchan’s book, Mesmerizing Math Puzzles. The maximum size is 15 cells, as shown.

It reminded me that I had seen a couple of similar problems. Jan Kristian Haugland found the largest polyominoes with no four equally spaced cells on any line, and detailed his discovery and proof of maximality in a paper. Here’s one; the others are minor variants on this one:

I’d also seen a no three equally spaced cells on a line problem for polykings. I had in my notes that it was studied on a bulletin board called Zompist and the maximum size was conjectured to be 48, but the post is gone and was not archived by the Wayback Machine. So I set myself the puzzle of reconstructing a 48-king with the desired property.

The gray squares here are not just an aesthetic flourish. I used them as a tool to keep track of cells adjacent to the figure that were excluded from being added. That way, when all squares adjacent to the figure were gray, I’d know that I’d found a local maximum. I could have taken them out afterward, but I think it’s fun to share and learn about how we work on problems. Or I’m just lazy, your pick.

With the no four equally spaced in a line problem leading to such a visually distinctive maximal polyomino, you might think (I did) that no n equally spaced in a line problems would give ever more intricate ones for higher n, if we could manage to find them. When I posted about the above problems on Ma(th)stodon, Dömötör Pálvölgyi (name order westernized) asked if there is always a maximum size of poloyomino for any n. I didn’t know, so Pálvölgyi took the next reasonable step, and asked on MathOverflow. Renan Gross answered in the negative; in fact, the maximum n which gives a maximal polyomino is 4, as in Haugland’s solution!

To show this, Gross first restricts his scope to Monotone Path Polyominoes: ones that can be formed by always taking steps up or to the right after placing the first cell. Every MPP can then be represented by a sequence of two symbols, one that means “go right” and one that means, “go up”. (We could use → and ↑. Then, for example, the W pentomino could be represented as →↑→↑.) Gross’s key realization was that any segment of an MPP starting with the first and ending with the nth equally spaced point in a line would have n – 1 consecutive blocks where each has the same number of →’s and ↑’s as the others.

At this point, Gross consulted the literature to find out whether someone had found a construction for a binary sequence where, for some number of consecutive blocks, this never happens, and a paper by F. M. Dekking from 1978 had just such a construction. Gross has written a blog post where he discusses his process in finding this result, which I highly recommend reading.

Where does this leave a recreational mathematician such as myself, whose major motivation is seeing results that make pretty pictures? Well, one direction we can go is to try this problem with other polyforms. With polyhexes, it looks like we can get 9 cells for n = 3. Because there is an affine transformation between the centers of the squares in a regular square tessellation and the centers of hexagons in a regular hexagon tessellation, we know that there is no maximal polyhex for n = 5, but n = 4 is open. One point to be careful about is the definition of the center of the cell that we’re using. For polyplets, (polyforms based on unit right triangles) we could get different results depending on what triangle center we use.

Another option would be to change the set of structures that must be excluded. If we think of 5 equally spaced points in a line as an exploded I pentomino, can we add other exploded pentominoes to our exclusion list to get interesting finite maximal examples? (I plan a post in the near future about exploded polyominoes, so I won’t define them formally for now, but you catch my drift. We may consider an unexploded polyomino to be a trivially exploded polyomino.)

A third direction would be to add cell coloring. If we have two colors, we can consider only lines containing the same color of cell. I’m a little pessimistic about there being maximal polyforms to be had here. Even n = 3 may generally be enough to escape confinement. But I’m optimistic in general about there being much more to be discovered in this area!

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.

Component Colorings

~ munizao ~ 1 Comment

Previously, I looked at problems concerning colorings of individual cells of polyominoes. These were not map coloring problems, (i. e., problems of giving a set of shapes a limited number of colors so no two adjacent shapes share the same color.) Map coloring the cells of a square grid isn’t very interesting, beyond noting that the grid is 2-colorable, with a checker pattern being the 2-coloring.

But suppose our polyform components are more complicated than individual cells. For example, the components could themselves be polyominoes. Now component-wise map coloring can be a source of interesting problems.

Since 4-coloring is always possible, 3-coloring is the usual place to go to when we want a challenge. Given three colors, the di-dominoes can be component colored in 15 ways. (There are 4 di-dominoes, and because the L-tetromino is asymmetrical, there are two ways to color it for each color pair.) Here is a tiling with 3-colored components:

Moving up to the tri-dominoes, there are 26, which can tile a 12 × 13 rectangle. Problem #58: Find a 3-coloring of the dominoes in such a tiling where each tri-domino contains all three colors. Edit: As Bryce Herdt pointed out in a comment, this is impossible, because there are tri-dominoes where all three dominoes surround a square that could not then take any of the three colors.

Four-coloring can be a worthwhile problem, provided that we can find a good additional restriction on color usage. With the 11 heterogeneous di-trominoes, we can restrict ourselves to two colors each for the I and L trominoes. Then we can find a component-wise 4-coloring of the set using those colors:

Notice that this is a “non-strict” coloring, since two red L’s meet at a vertex. Problem #59: find a strict 4-coloring of the components of the heterogeneous di-trominoes in a 6 × 11 rectangle.

There are undoubtedly other fruitful directions to take component coloring. Perhaps there is something to do with poly-polyiamonds, or poly-polyhexes. I would be delighted to see what you can find!

Can 3½ Colors Suffice?

~ munizao ~ 2 Comments

The loan seemed like an incredible break. You got back on top of your mortgage, even had enough to put your oldest into a decent private school. And all they asked you to do was solve puzzles.

The puzzles were actually fun, for a while. But they got harder. And when you couldn’t solve them fast enough, the threats started. And that’s how you ended up here, wherever here is, kidnapped, bruised and bloody, on a floor covered with grit and sharp angular tesserae.

There’s a note. Another puzzle. In order to leave, you’re going to have to pick out some of the tesserae and use them to tile a shape. And no two tiles of the same color may touch. Pretty basic.

And then you realize that it’s too dark for you to be sure what the colors of the tiles are.

There’s a real problem with constraining the number of colors in a colored tiling as an additional challenge: our options just aren’t very granular. Literally everything (on a plane, which sometimes we aren’t!) can be 4-colored, a small proportion of things can be 3-colored, and almost nothing that isn’t highly contrived can be 2-colored. If only there were some options in between!

To our relief, and our hero’s consternation, there can be. Observe that we can make a graph with colors as nodes and edges connecting colors that are permitted to touch. For an n-coloring, this is simply the complete graph Kn. But there might be other graphs (we’ll call them color graphs) that produce interesting results. For example, consider this one:

We might consider one color graph to have greater “coloring power” than another if it can be used to color a proper superset of the graphs that the second graph can color. This graph turns out to have a coloring power intermediate between those of K2 and K3.

Here’s a tiling of the 2–5-iamonds colored according to the above graph. (Kadon sells these shapes as its Mini-Iamond Ring puzzle.)

There’s a reason I showed the color graph as a pentagram, even though you could rearrange the nodes into a pentagon and get rid of the crossings. Let’s take a simplified model of color where allowed instances lie on a circle of hues. From the perspective of our hero with color vision reduced by darkness, nearby colors around the circle might be too similar to safely place next to each other.

As we raise or lower the level of light in this dungeon, the minimum distance between colors that can be allowed to be adjacent in a coloring will change. We can make arcs along the circle that correspond to hues that can be legally adjusted to the hue at the center of the arc. Finally, we connect the nodes for the arcs that don’t overlap to make a color graph.

For arc lengths (as a proportion to the circumference of the circle) that are fractions of the form 1/n, we get the complete graph, Kn. But for other rational arc lengths, we get different graphs. Here’s the one for an arc length of 2/5:

What’s nice here is that the reciprocal of the arc length describes the coloring power of the corresponding graph. For the above graph, the reciprocal is 2½, and this does in fact mean that its coloring power is stronger than 2-coloring and weaker than 3-coloring. This type of coloring is called a “circular coloring“, and it extends our usual definition of chromatic numbers into “circular chromatic numbers”. The graphs that are formed by this process are “circular complete graphs”.

Here’s the color graph for a circular chromatic number of 7/2:

This one can also be useful for coloring polyform tilings. Consider this tiling of the 21 5-rects:

It is not 3-colorable, as we can see by starting at the starred pieces and following the colors that are forced until we come to the checkered yellow pieces. But it is “7/2 colorable”!

One nice aspect of this coloring scheme is that we can get balanced colorings of sets that have a multiple of seven pieces. There are undoubtedly balanced 3-colorable solutions to the above tiling problem however, so this isn’t necessarily the “best” coloring possible here. A solution to the following problem might have a good claim to the title though: Problem #57: Find a tiling of the above figure with the 5-rects that has a 3-coloring and a 7/2-coloring such that all 21 color combinations occur exactly once.

Now, you may be grumbling at this point about my title being inaccurate and click-baity, because there are clearly seven different colors here, not three and a half. And certainly, there are for you and I, who have plenty of light to see them by. But for the poor soul toiling with ambiguously colored pieces in my basement some entirely hypothetical dungeon, it really does feel like having somewhere between three and four colors available.

This is just the beginning of a rabbit-hole that can go a lot deeper than this blog post can contain. A curious person might wonder: what about other color graphs? Playing around a bit shows that a lot of different color graphs have the same “coloring power”. For example, any even cycle graph can color exactly the same graphs as K2. If you number the nodes around the cycle, even colors may only be adjacent to odd colors, (and odds to evens) and the even and odd sets of colors can color exactly the graphs that the 2 nodes of K2 can color.

In more standard mathematical terms, what the last paragraph says is that even cycle graphs are homomorphic to K2. Generally, homomorphically equivalent color graphs have the same coloring power. Every graph is homomorphically equivalent to a so called “core”, a minimal graph that captures the information we need for coloring. (In the previous example, K2 was the core.) So we can restrict ourselves to just cores when we’re looking for interesting color graphs.

The circular complete graphs we looked at are cores. Other cores exist, but they don’t fit nicely into the ordering that the circular complete graphs do, and so don’t give us meaningful chromatic numbers. But they could still be fun things to apply to polyform colorings. (Or even problems of actual mathematical import. In 2018, the lower bound of the Chromatic Number of the Plane was improved to 5. Perhaps a unit distance graph with a circular chromatic number of 11/2 could be found, effectively improving the lower bound for an extended version of the problem.)

And that’s all I have for now, although I expect that this won’t be the last time I visit the subject of colorings. Until next time, be well, and beware loan sharks bearing puzzles.

Piling Polyominoes

~ munizao ~ Leave a comment

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

No OverlapOverlap
No holesTilingPiling
HolesPackingTacking

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

Cell Numbering Sums

~ munizao ~ Leave a comment

Before I started this blog, I explored polyominoes with cells individually labeled with numbers. I called these sumominoes, as I was looking at sets of all polyominoes with a given sum. Erich Friedman discovered them independently, and called them weightominoes in his July 2009 Math Magic Problem of the Month. I prefer his term for the general concept, as there is no reason they need to be grouped by sum. Both Friedman and I looked at problems where the goal was to overlap these polyominoes in a rectangle so that every cell had the same sum of labels. While I looked at a particular complete set, Friedman looked at pilings of multiple copies of the same cell numbered polyomino. (Aside: “pilings” isn’t a standard term, but it’s a concept we need a term for. We have “packings” for deficient tilings that don’t fill a space, so “pilings” for abundant tilings that fill it with overlap. Then a “tacking” is when there is both empty space and overlap, of course.)

All polyominoes with positive integer labels that sum to 4.

In this kind of problem we looked at sums of cells in the “z” direction. But we could instead look in the x and y directions. There is a common type of figure where we do this already: magic squares!

For this type of problem, excluding 0 as a potential cell label isn’t necessary. Standard numbered dominoes include 0 (blank) as a label, so we might want to do the same for physical puzzles using pips. (Pip patterns are preferable to numerals for physical puzzle pieces since they don’t have a preferred orientation.)

In fact, in the context of standard dominoes, examples have existed for some time. Here is a domino magic rectangle using a full set of double-six dominoes. The row sums are all 24, and the column sums are 21.

Solution from “The Existence of Domino Magic Squares and Rectangles”, by Michael Springfield and Wayne Goddard, graphic mine.

Of course, the fact that it can be done doesn’t make it a good puzzle, and working with a full set of dominoes might get tedious. Since I’ve been looking for simple puzzles with small piece sets, I tried to find one in this format. There are two cell numbered dominoes and four L-trominoes with a cell sum of 2. Their total area is 16, good for a 4×4 square,. and their total label sum is 12, giving a row and column sum of 3. One nice thing about a magic square type puzzle is you get an extra challenge for free. Finding a configuration with just row and column magic sums is a fairly light challenge, but getting the main diagonals to also match the magic sum is much harder. I had a small number of these made to give away at the 2022 MOVES conference:

Show Solution

Looking upward in size, there are 12 trominoes with a cell sum of 3, good for a 6×6 square with line sums of 6. I made a prototype:

But this isn’t quite as great as a puzzle, which is why I didn’t bother to conceal the solution as a spoiler. The reason is that it’s easy to make subunits where pip sums are preserved on applying a symmetry action. For example, in the solution above the three I trominoes in the upper left can be permuted in any order without changing row or column sums. Likewise, the two 2×3 rectangles formed from two L trominoes on the bottom can be flipped over one axis. This makes it much easier to turn a semimagic (row and column only) solution into one where the diagonals also work. (Subunits like these can appear in the smaller puzzles here, but there isn’t really enough room for them to dominate a solution.)

What I really want from going one step up from a 4×4 puzzle is a 5×5 one. Well, if we exclude the pieces with 3’s, we have an area of 24, which is almost right. We can make a 5×5, but it would have an unfortunate hole:

Or a fortunate one! Since my pips were lasered out holes to begin with, the big hole should clearly just count as one hole for the purpose of line sums. Now we have 25 holes, and 5 will work as the line sum. (While I normally like rounded corners for pieces since they have a softer tactile feel, if I made more of these, I’d use sharp corners and square pip holes, to visually unify the two different hole sizes.)

Show Solution

Is there anything else we can do with cell numbering? Polyhexes seem promising since there is an extra direction for sums to happen on. And perhaps we can use the numbers for something other than sums. I’m sure there are more creative discoveries waiting to be made!

The Pentominoes My Destination

~ 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

~ 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

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

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.

Revenge of Flexible Polyominoes

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

(Solution again by Edo Timmermans.)

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?

Polykingsticks

~ munizao ~ Leave a comment

I noted a while back that triangular polysticks hadn’t received the study they deserved. Perhaps we can say more generally that a fruitful way to find understudied polyforms is to take the polysticks that correspond to connections between cells in some other polyform set. Since I was recently looking at polykings, it makes sense to ask what nice sets we can make out of polykingsticks, and what we can do with them. There are only six dikingsticks. Here are the 41 trikingsticks: [Edit: numbers fixed per communication from GS]

That’s a lot! We can distinguish some categories. First, “proper” polykingsticks (in red) exclude those that have only one type of connection. “Snakes” (bolder lines) are polysticks for which there is a single path that visits each vertex once. Most of the non-snake trikingsticks are branched. There are a couple of oddballs, a right triangle and one self crossing snake, which you might need to omit if you have a problem where you want to avoid crossings.

What kinds of problems can we explore with these? They’re a bit awkward for tiling. Compatibility problems should work, as long as the pieces have the same balance between diagonal and orthogonal segments. Common superform problems should also be doable.

We can also try Hamiltonian circuit problems like the one that I looked at with regular polystick snakes. There is a parity issue here. If we checker the vertices of the grid, we require an even number of snakes where the two ends are opposite colors in order to make a circuit. This means we can’t use the set of proper trikingstick snakes with the self-crossing snake omitted. Perhaps with it included, we could do a Hamiltonian circuit of a 6×11 grid. If we just make a path, rather than a circuit, and exclude the self-crossing snake, visiting all of the points on an 8×8 grid might be possible.

With so many trikingsticks, tetrakingsticks might seem too large of a set to contemplate, but I have a couple of ideas for interesting reasonably sized subsets. These will have to wait for another post, however.

Tilings and Reconstructions

~ munizao ~ Leave a comment

There are nine proper 4-WFD-ominoes:

Recall that a proper WFD-omino is one where every spanning tree of W, F or D connections between the cells includes at least one of each. Recall that W, F, and D connections correspond to the moves of the Wazir, Ferz, and Dabbaba in historical chess variants. And recall that these moves are, respectively, a one space orthogonal move, a one space diagonal move, and a two space orthogonal jump respectively. (It’s fine if you don’t recall these things. I’ll recall them for you. Or you can read this post, and then recall them.) The full set is the right size to tile a 6×6 square. And indeed, it can!

And yet, you might find that graphic just a little unsatisfying. The solver that I use for polyomino tilings displays results with all of the pieces in the same color. This is fine for standard polyominoes, but for disconnected (or differently connected) polyominoes, it’s hard to see where all of the loose monominoes fit. But that just turns reconstructing the tiling into a logic puzzle. Indeed, there are entry points where a domino is constrained to be in a particular proper 4-WFD-omino, which removes certain monominoes from consideration and forces other dominoes to belong with their monominoes, and like a sudoku, the chain of logic eventually forces a complete solution. Try it!

But a 6×6 puzzle may feel a little small if you’re used to Sudoku or other puzzles in the Nikoli mold. So let’s try out the proper 4-WFA-ominoes. (Recall that the A (Alfil) is a two space diagonal jump.) There are 15 of these:

They have area 60, so they can tile a 8×8 square with corners removed, just like the 12 pentominoes.

Reconstructing the tiling here is a substantially harder puzzle than the previous one. The monominoes belonging with particular dominoes can be farther flung, which makes it harder to constrain which bits must be connected. I had to try out a large number of tilings before I found one where I could make some headway in the reconstruction puzzle. But rest assured that I did indeed solve this one.

Where to go from here? There are 21 proper 4-WFN-ominoes, (recall that N is for knight) but they have odd checkerboard parity, which interferes with trying to find a nice thing for them to tile. Another possibility would be to combine the proper 4-WFDs and 4-WFAs in a single puzzle. Either way would make it even more difficult to constrain which monominoes go with the dominoes. There may be solvable reconstruction puzzles in the space of tilings, but the strategy of picking tilings at random to find solvable ones will probably break down. I suspect that there are more good puzzles in this vein waiting to be discovered, but they may require more creativity in coming up with new piece sets that will work, or in puzzle design or discovery techniques.

Proper Polyking Solutions

~ munizao ~ Leave a comment

George Sicherman sent in some solutions to Problem 51, which was to tile a certain torus with the proper polykings and a monomino hole. There were several optional challenges presented, and each of these solutions met two of them. (For the present post, we’ll pretend that challenge 4 asked specifically for a 4-coloring, rather than vaguely asking for a reduced number of colors.) The first satisfied the no-crossed bridges constraint and the no four-piece corner constraint:

The second is 4-colorable, and has no crossed bridges:

And the third is 4-colorable, and has no “fault lines” passing through it:

These results got me thinking about the combinatorics of independent optional challenges of a given problem. A realizable subset of optional challenges is “optimal” if it isn’t a proper subset of another realizable optional challenge set. From the perspective of a problem designer, a full set of optional challenges might be said to optimize interest if it maximizes the number of optimal realizable subsets. For example, problem 51, with four optional challenges, would be most interesting if all six pairs of challenges were realizable, but no triples of challenges were. In general, a problem with n optional challenges will be optimally interesting if all realizable subsets of size n/2 are optimal, if n is even. For odd n, optimal realizable subsets would have to be all of size (n + 1) / 2 or all of size (n – 1) / 2.

Problem 51a: Make Problem 51 “better” by finding solutions with that satisfy missing pairs of challenges.

Problem 51b: Make Problem 51 “worse” by finding solutions that satisfy a set of challenges that is a superset of two or more of the challenge pairs satisfied by the above solutions.

Metaproblem: Design an optimally interesting puzzle with four or more challenges!

A Polyformist’s Toolkit: Connections

~ munizao ~ Leave a comment

We may say that a polyomino is a connected set of squares in a grid; now I want to examine what we mean by “connected,” and what we can mean.

The usual definition requires cells to be connected along their edges. A common variation allows cells to connect either with neighbors either by edges or by corners. These have been variously called polykings, polyplets, and pseudo-polyominoes. My personal preference is polykings: I know what a chess king does, and it immediately suggests how a polyomino variation based on the concept would work. I don’t know what a plet is, and pseudo is both wrong, (there’s nothing fake or false about them) and unspecific, (if we are going to go around calling things false polyominoes, we have plenty of options.)

The 22 tetrakings.

Wikipedia titles its page on them Pseudo-polyominoes, because Golomb called them that in his book, and printed books override all other forms of knowledge. Except, at the time I am writing this, everywhere on that page except for the title, where Wikipedia continues to calls them polykings.

Unfortunately, rather than leave well enough alone and stick with just “polykings”, I’m going to introduce my own confusing and awkward terminology. Because there are actually many more choices for ways to associate pairs of connected cells on a square grid, and we’re going to need a systematic method to keep track of them. As with “polykings”, chess piece moves more generally can correspond to allowed connections between cells in a type of polyomino. And we may turn to a standard notation for chess piece moves, which was developed by Ralph Betza and adopted more widely by chess variant designers.

The initials used to designate short piece moves mainly come from pieces in historical versions of chess. W, for Wazir, (Persian, minister or vizier) is the one orthogonal space move,. F, for Ferz, (Persian, counselor) is the one diagonal space move. D and A are for Dabbaba (Arabic, siege engine) and Alfil (Arabic, elephant) respectively. N is the standard initial for a chess knight, since the king takes the K. Instead of polykings, now we may speak of poly-WF-ominoes. Likewise, we can construct poly-WD-ominoes, and poly-WFD-ominoes, etc. Peter Esser has looked at the poly-WFD-ominoes, which he calls “Far-Bridged Polyominoes”, and also some symmetry variants based on them.

Not every possibility is equally interesting. For example, the poly-F-ominoes are equivalent in a way to the poly-W-ominoes: by rotating and dilating the positions of the cells, you can uniquely transform any of the former to one of the latter.

There is a practical problem with the poly-WF-ominoes and some of the other connection based variants we can come up with. The sets generally grow so fast with the size of polyomino that they skip right past the domain of practical manual solvability. Twenty-two 4-WF-ominoes is just too many, but five 3-WF-ominoes is trivial. But if we observe that just 12 of the 4-WF-ominoes aren’t W-ominoes or F-ominoes, we get a set that is manageable. We can call these the proper 4-WF-ominoes, and define them more formally as all of the 4-WF-ominoes for which every spanning tree of connections contains at least one W-connection and one one F-connection.

Unfortunately, the proper 4-WF-ominoes have odd checkerboard parity, so we can’t use them to tile a rectangle. I did however manually find a tiling of a 7×7 square torus with the proper 4-WF-ominoes plus a monomino.

Problem #51: There are some improvements upon that solution I’d like to see. How many of the following can be achieved, either individually or together?

  1. Avoid any “Fault lines”, or runs of border segments that pass all the way through a tiling. With standard polyominoes, this is rarely difficult. These pieces have fewer orthogonal connections that can block a fault line. There are 14 rows and columns, and only 18 orthogonal connections, so they must be spent somewhat carefully.
  2. “Crossroads”, or vertices that join four border segments are unavoidable due to the diagonal connections. A constraint that would be equivalent to “No crossroads” for standard polyominoes is “No four-piece corners”. Here, this constraint is weaker than the original, and should be achievable.
  3. No crossed bridges. Physical sets of polykings require “bridges” joining cells across diagonal connections, and rounded corners that allow bridges to pass. Tilings where two bridges cross could not be made from such pieces. Bernd Karl Rennhak has explored bridged polyforms in depth. Kadon’s Roundominoes are another variation on the theme, where some “bridges” aren’t connected to cells on both sides.
  4. Reduce the number of required colors. Since there are diagonal connections, same color pieces should also not meet at diagonals. (What I had previously called “strict” colorings.) But with rounded bridged pieces, that would not necessarily be visually confusing. Balanced colorings are nice.

Another way around the checkerboard parity issue is to use flexible rhombus based proper polykings. These can tile the following figure:

Problem #52: The same features that were desired in Problem #51 are also missing here. Can you improve it?

It seems that having spent so much time introducing Betza notation, I’m past my ideal post length, so I’ll have to close without using it enough to justify it for now. I hope to rectify this not too far in the future, when I intend to post about the proper poly-WFD-ominoes and other connection-based polyform variations.