Marking external edges of polyforms leads naturally to restrictions on tilings that make for good puzzles. We can simply match marked edges, and if two edges on each piece are marked, we can draw a path between them and make challenges based on properties of the paths formed. Internal cell edges on pieces can also be marked. Since there isn’t a “natural” challenge using these markings, we’ll have to be creative. Here’s a tiling of all 12 ways to mark a single internal edge in a 5-iamond, where the markings have reflection symmetry:
Ah, symmetry, the first resort of the lazy polyform problemist. More symmetry is always better, so that’s Problem #65: Find a tiling of the above figure with the same pieces, where the edge markings have 3-fold rotation symmetry.
There are 10 ways to mark an internal edge in a 4-omino. The challenge that I’ve devised is to place the pieces so that no edge mark is on the same line as an empty internal edge. One of the pieces, the marked square tetromino, inherently breaks this constraint. So, by the law of exclusion of inconvenient pieces, it has to go.
Excluding the inconvenient piece lets us tile a square, giving us a little extra symmetry compared to the rectangle we would have otherwise been forced to tile.
If inconvenient piece exclusion is the first step toward becoming a dirty puzzle designer instead of a pure and noble recreational mathematician, surely the extra symmetry will stand as penitence for my sin.
In planning out blog posts, I typically use the rule of thumb that a post should contain between two and four images. If I have five or more images, I try to break the material up into multiple posts, and if I have only one I will usually wait until I have more material. A single image is a still life; when there are more, I can tell a small story. Unfortunately, this means that over time I build up a number of “orphans”, perfectly good results left to gather dust because I have nothing else that is closely related. I recently noticed that several of my orphans were square shaped. Perhaps I could use this to tie some disparate results that normally wouldn’t belong together into the same post.
1) I noticed last year that the tetrakis grid 4- and 5-tans had a combined area that could make a square. This seemed like a pretty basic result that had to have been known years before. I asked (and looked) around, but I couldn’t find any instances of it being found previously. Then in preparing this post, I discovered that I was almost right. It had, in fact, been foundmonths before, by Thimo Rosenkranz. (That page isn’t visibly dated, but a timestamp in the html code indicates it was published in July of 2023.) For all I know, these pieces may have been studied many times previously, but having done the important step of preventing myself from falsely claiming primacy, I am content to leave off further historical research.
2) I claimed that I couldn’t do anything elegant with just the set of single-striped tetrominoes, but shortly after I posted that, I found the figure below. Here, I relaxed the rule that the stripes must form an unbroken line from one edge of a figure to another. Instead the stripes may have a singe-cell gap in order to allow a perpendicular stripe to pass through. A woven pattern, where each stripe crosses one other and allows another to cross it, seemed like the nicest possibility. (The faded dashed lines are artistic license on my part, not actual markings on the pieces.)
3) The pieces here are based on those in my L-Topia puzzle. That puzzle contained every way to mark two cells of an L tetromino with a circular and a square hole. When I had access to a laser cutter in 2009, I made a variation where, instead, the holes were double headed arrows that could point horizontally or vertically. I was recently reconsidering “pilings”, (tilings with overlap) and wondered what could be done with pieces with marking sites where the markings have two possible orientations by symmetry, and the overlaps must match one orientation with the other. My L-Topia variation came to mind, but I had better results with a similar variation, where the arrows would be diagonal instead. Here, instead of cutting out arrow-shaped holes, I cut out triangles on opposite corners, leaving a bar to overlap. There is a unique piling where the overlaps form a single loop joining all of the pieces.
4) At G4G15, I gave a talk on polykings and other polyomino variations where cells are connected in different ways from standard polyominoes. I based the talk on a couple of earlier blog posts, but I did throw in one additional result. One of my usual creative tricks is “mix ideas, even if they aren’t meant to be mixed.” In the context of tiling problems, that can work out to “tile with sets of pieces that aren’t meant to be mixed.” If we build the five tetrominoes with each of the five shortest cell connection types, we get 100 total cells. Why not throw them together into a 10×10 square? In the diagram below, each tetromino form is represented by a different color, while the crosses indicate the directions and magnitudes of the connection vectors.
Problem #64: Well, everything is always nicer if you can make things of the same kind not touch. Here that means both tetrominoes of the same form, and tetrominoes with the same connection type. But asking for both may be too much, so we may have to accept just one or the other. But wait! What exactly do we mean by not touching here? Simply using Wazirwise adjacency seems contrary to the spirit of the thing. Let us say that two pieces touch if the connection type of one of the pieces can reach, from one of its cells, a cell in the other piece.
We might like there to be some theme that we can tease out from these unrelated square tilings that can retroactively justify shoveling them into the same post. If there is, it might be parity of elegance. A square has high elegance, having maximal symmetry in a smooth, convex shell. But as a consequence of this elegance, we don’t have many sizes of squares available, just one for each integer, so we have to contrive somewhat inelegant sets of pieces to tile them. In the case of the striped tetrominoes, the fixed dimensions of the square forced me to fudge the stripe placement rules to get the stripes to fit.
Of course, there is no such thing as parity of elegance in the universe of possible tilings; many very inelegant tilings may be found. What we see is the effect of me selecting the most elegant tilings that I can find to share on my blog. In these cases, the elegance of the square justified less elegance in other aspects of the tilings.
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?)
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.
In 2022, Jacques Ferroul sent some notes on a remarkable exploration in polyominoes to Kate Jones, who shared them with George Sicherman, who in turn forwarded them to me. I quickly saw that there was quite a lot of potential there, and exchanged a few emails with Ferroul, where we shared ideas riffing off of his original notes. And then I let the matter go, since it would seem unkind to scoop his discoveries in a blog post when he still hadn’t written about them for public consumption. Recently, I came back to thinking about them in the context of a notation system for polyform tile sets that I had been noodling upon. And when I looked to see what he had been up to lately, I found a note on Kadon’s page for a puzzle he designed, stating that he died in December 2023.
Well, crap.
So I guess I can write this post now. A fuzzy pentomino, in Ferroul’s conception, is an equivalence class of tetrominoes connected to weighted adjacent cells where the weights sum to one. All of the figures below are the same fuzzy pentomino:
Equivalence classes of polyominoes shouldn’t be wholly unfamiliar. We use them for aspects of the same polyomino with different symmetries applied. Ferroul was inspired by fuzzy logic, where truth values can take on any value between 0 and 1. (I can also see an analogy to the “cloud of probabilities” model of electrons in an atom.) A simpler version, where the added cell is constrained to have a weight of 1, Ferroul calls “boolean polyominoes”.
When we use fuzzy polyominoes in a tiling, we allow cells from different polyominoes to overlap as long as their weights sum to one. Now it’s reasonable to ask: does this lead to interesting tiling problems? And I think the answer is, not directly! Restricting ourselves to the “boolean” case, a tiling with these would be equivalent to making a tiling with an extra monomino next to each tile. And tiling generally gets pretty easy when you can throw in a bunch of extra monominoes! Ferroul was interested in finding a tiling that required non-boolean polyominoes to realize. I’m pretty sure this is impossible, but I don’t know how to prove it.
We can however make problems where we put some additional constraints on the extra cells. For example, let us fuzzily join each tetromino with two half-weight cells, and for each piece put one copy of the same color in each of two 5×5 squares. The number of extra cells is 10, exactly the same as the number of pairs of tetrominoes. Then a “fuzzy” tiling can be turned into a puzzle using regular tetrominoes and unit tiles matching every color pair:
The generalization of tiling to weighted cells where weights must sum to one may also be used without the equivalence rule. Here are all of the ways to join a dihex or trihex to a weight-½ monohex.
And here’s a tiling where the monohexes overlap:
Problem 62: Find a tiling where the monohex positions have some symmetry. Bilateral or threefold rotation symmetry seem likely to work. Dihedral threefold symmetry seems less likely, but would be cool.
I have a couple more problems I’d like to share in the fuzzy polyform vein, but this is a good place to stop for now. It’s also worth mentioning that some of the previously produced polyomino piling problems can be modeled as “subtractive fuzzy polyominoes”, where for each piece we take an equivalence class of pieces where one of the cells has been reduced to a fractional weight, and we are again making a weight-1 generalized tiling. I mentioned before that working on a notation system for polyform sets was what brought me back to this subject matter. In a future post, I intend to elaborate on some of what I’ve come up with so far. But for a small spoiler, check the tags on this post.
Back in my 11th post on this blog, I posed a problem involving tiling a figure with tetrominoes, and then tiling the edges of the tetrominoes with tetrasticks. Now I’m on my — well, look at that. This is my 100th post here! Anyway, recently I was playing around with Jaap Scherphuis’ PolySolver program, looking to see if there were any of my old problems that it could solve, and that one looked like a good fit. It turned out to have a unique solution, according to the solver.
As it happened, this problem was already at the front of my mind, after meeting William Waite of puzzlemist.com at Gathering 4 Gardner 15 this February. He gave me a copy of a combined polyomino/polystick puzzle he designed after a previous conversation at a G4G where I mentioned the problem above.
I think it’s worth examining how this puzzle differs from my take on the type, and why. I used a complete set of tetrasticks, and the closest thing I could get to a complete set of polyominoes, doubling up on tetrominoes and throwing in a monomino hole only because one of the tetrasticks required it. It’s just my aesthetic as a polyomino problemist to want to use complete sets when I can. Waite has a different objective; this was a puzzle produced for sale, with the object of the customer feeling that they got good value for the purchase price. Thus, where I didn’t care if the puzzle required computer assistance to solve, Waite wants a human puzzler to have a good chance of getting there on their own.
Because of this, both the polyomino set and the polystick set consist of easier pieces to tile. The polyominoes are the full set of 2–4-ominoes, which is at least as nice of a set as what I chose. The polysticks, however, are a mix of 3-sticks and 4-sticks, and neither set is complete. The polystick pieces seem to have been chosen for ease of tiling. The qualities that would make a more tilable piece are having little symmetry, having a smaller bounding box, and having a shape that fits nicely on the edges of the board. These pieces all have at least one of these features. The puzzle claims to have 4326 solutions, so finding one of them should be tractable.
Having a single unique solution doesn’t make a problem better than any other, but it does seem like a remarkable occurrence. Doubly so when lightning strikes again near another instance. Here I adjusted the shape from the first problem to one that had biaxial symmetry rather than quarter-turn rotation symmetry. This too has a unique solution!
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.
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.)
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.
Previously, on Vexed by Convexity, we looked at various measures of convexity as applied to the pentominoes. In order to turn these measures into interesting puzzles, we can try to minimize their values for some family of polyominoes. Arrangements of tetrominoes were one that I found to make good puzzles.
Why minimize convexity? Well, we could maximize, but the different measures converge as we approach a convexity of one, so if we want different puzzles, minimal convexity is a better bet. To mangle Tolstoy, all happy (i.e. convex) polyominoes are alike; every unhappy polyomino is unhappy in its own way. On to the problems:
Problem #46: Find the least convex connected arrangement of the tetrominoes, where convexity is defined as Area / Convex Hull Area. Here is my best attempt, with convexity = 20/55.5 ≈ 0.36036:
Problem #47: Find the least convex connected arrangement of the tetrominoes, where convexity is defined as Convex Hull Perimeter / Perimeter. Again, my best attempt, this time with convexity = (14 + 5√2) / 40 ≈ .5268:
You might be expecting the probabilistic definition of convexity defined in the previous post to be next, but it’s a little unsatisfactory. Checking enough segments to have a good estimate would be computationally intensive, and it’s hard to know how many segments is enough to separate any pair of polyominoes that are competing for minimal convexity. (Presumably there is some way to calculate exact values, but I don’t know it.)
But we can cheat. If we check only segments connecting the centers of squares, we have a reasonably bounded quantity of segments to check. This is at the expense of no longer having a valid convexity measure (for example, this method would find the P pentomino to be convex.) But that’s fine; what we really care about is just having a good puzzle.
Problem #48: Define the “convexity” of a polyomino as the proportion of segments connecting the centers of squares within the polyomino that remain entirely within the polyomino. (The border counts.) Find the least “convex” connected arrangement of the tetrominoes. My best attempt, with convexity = 51/190 ≈ .2684:
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.
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:
In polyomino puzzles, we would frequently like to tile the simplest shape possible, and a rectangle usually seems to fit the bill. But sometimes a rectangle isn’t possible. For example, we can never make a 4×5 rectangle with the five tetrominoes. One way to prove this is with a checkerboard parity argument. Four of the 5 tetrominoes must always occupy even numbers of both black and white squares if they are placed on a checkerboard. The T tetromino must occupy odd numbers of each color. Therefore a rectangle must have odd numbers of each color, but any rectangle of size 20 will have colors evenly divided, 10 and 10. A similar argument can be made to show that the 35 hexominoes cannot tile a rectangle.
This will never work…
Rather than give up and accept that we’ll need to find a less elegant shape to tile, we have another option. If we wrap the edges of a 5×4 rectangle around to form a cylinder, (so that the cylinder is 4 squares tall and 5 squares in circumference) tiling is once again possible. To see why this might be so, imagine that you are coloring the squares as in a checkerboard. Once you got back around to where you began, you would find that in order to continue the pattern, you would need to use the opposite colors from those you already used. Note that this would not work if you wrapped the rectangle in the other direction; because the other side has even length, the checkering colors remain consistent.
…until we wrap the rectangle into a cylinder.
There is a video by Edo Timmermans showing how a tetromino cylinder can be made with toy magnets. He claims that there are seven distinct tilings of a cylinder with the tetrominoes, and poses an interesting puzzle involving them. A commercially produced cylindrical polyomino puzzle is Logiq Tower, designed by Marko Pavlović, which uses wooden pentomino-based pieces that form a cylinder together with some other pieces. Because these pieces are inflexible, they lack some of the allowable symmetry actions of free pentominoes.
A cylinder isn’t our only option. We could give the rectangle a half-twist before connecting the ends; this gives us a Möbius strip. We could also connect both pairs of sides instead of one; this gives a structure that is topologically equivalent to a torus or doughnut. And then we could add twists to that— well, at this point it would be nice to be systematic so we can be sure that we’ve found all of the possibilities. One thing to note is that adding more twists doesn’t actually give us more possibilities. A strip with two twists will have exactly the same tilings as a strip with no twists, and in general, a strip with an even number of half-twists will have the same tilings as the no-twist strip, and a strip with an odd number of half-twists will have the same tilings as the Möbius strip. So for each dimension, we have three options: no connection, connection without a twist, and connection with a half-twist. This gives us the following matrix of possibilities:
Only six possibilities here, not nine, because the ones in the lower left are equivalent to the ones across the main diagonal from them. Note that the Möbius strip, Klein bottle, and projective plane are nonorientable surfaces, which means that they effectively have only one side.
An important consideration when working with these is that one-sided polyominoes don’t exist on nonorientable surfaces. With one-sided polyominoes, translation is allowed, but reflection isn’t. However, on a non-orientable surface, translating far enough leaves an object in a reflected state.
Another consideration is that coloring is harder when we leave the plane behind. On the plane, we have a theorem stating that we never need to use more than four colors to make all of the tiles differ in color from all of their neighbors. On a torus, this may require seven colors. In 2001, Roger Phillips found 18 heptominoes that could tile a 7×7 torus, and sent these tilings to MathPuzzle.com. Here’s one:
Depending on the dimensions of the torus, it may be possible for a polyomino to wrap around and touch itself. In a strict sense, this makes any coloring impossible, since we don’t let tiles of the same color touch. However, we can follow a looser standard, and allow self-touching polyominoes in our colored tilings. Patrick Hamlyn found a 3-coloring of a tiling of the 35 hexominoes in 7 3×10 tori using this scheme in 2003:
This problem has no solutions if the tori are replaced with rectangles or cylinders.
Problems #31-37:
Though it seems like a pretty basic problem, if anyone has counted the number of pentomino tilings of cylinders, I am not aware of it. Wrapping the short sides of the 3×20 together should not give any solutions beyond the two obtained by wrapping the solutions on the 3×20 rectangle. That leaves the 3×20 wrapped the other way, and both ways of wrapping the 4×15, the 5×12, and the 6×10 rectangles.
Problems #38-40: Find the solution counts for the 4×15, 5×12, and 6×10 tori. I don’t know if these are all computationally tractable, but I can hope. (The 3×20 will be the same as the 3×20 cylinder with long sides wrapped together.)
Even more possibilities for tiling become available when you choose parallelograms with diagonal sides to wrap around, but this post is long enough, so that will have to be a matter for another post.
It’s the holiday shopping season, so I figured it couldn’t hurt to write a post or two on the puzzles I am selling.
Every mathematical puzzle designer worth his or her salt has an argument for their puzzle’s awesomeness using impressive sounding mathematical justifications. This, for L-topia, is mine.
There are 12 pieces in the set. Empirically, 12 is a good number of pieces for a mathematical puzzle. There are 12 pentominoes, and 12 hexiamonds.
The shape of the pieces, an l-tetromino, has some desirable properties. It is very highly tileable. Two factors that affect the tilability of a polyomino are its size and its symmetries. Smaller and less symmetrical polyominoes are the most tilable. The l-tetromino is the smallest asymmetrical polyomino, and the only asymmetrical tetromino, so it should be the most tilable of all.
A set of 12 l-tetrominoes tiles a 6×8 rectangle in 1114 ways. That’s probably the most for any set of 12 copies of a single polyomino tiling any rectangle, but it’s not that impressive compared to other sets containing multiple shapes. For example, the 12 pentominoes can tile a 6×10 rectangle 2339 ways.
But because the shapes are all the same, if you mark all of them in some way to distinguish them from each other, (as the holes on the L-topia pieces do) every permutation of placements of the 12 l-tetrominoes can create a distinct tiling. Now the total number of tilings is roughly 1114 · 12!. (Actually, it’s slightly less because some of the tilings of the rectangle are symmetrical: about 55 of the 1114 solutions are symmetrical by reflection or 180° rotation, so the total is about 1059 · 12! + 55 · 12! / 2, or about 520 billion.)
Well, that’s a pretty impressive number, but having an impressively large space of possibilities does not, by itself, make for a great puzzle. In this case, however, I do think it is helpful, and I’ll explain why presently.
Suppose I think of a proposition that can apply to any of the holes in the set. For example, that the hole appears in an odd numbered row. Because there are two different kinds of holes, it may be elegant to use either the opposite of that proposition, or some proposition that is complementary in some way, to apply to the second kind of hole; in the problem illustrated by the solution above, we have the round holes in odd rows, and the square holes in odd columns. Suppose the probability of the proposition being true is ½, and suppose that the probability for each hole is independent from the others. (One must take care that the placement of holes on the pieces doesn’t fatally interfere with independence; if, for example, we had asked for circles on odd rows and squares on even rows, there would have been pieces that could not have been placed legally anywhere.) Then the probability that the proposition is true for all of the holes is 1/224. Given this piece of information, we can get an expected number of tilings where the proposition is true by multiplying that probability by the total number of tilings.
The result is about 31,000. That number is tiny compared to the size of the total space of tilings, but I can say from experience that it makes for puzzles that are challenging but solvable. And it gives us wiggle room to use propositions with probabilities that are a little smaller than ½, or for which the probabilities are not entirely independent. The result is that we can come up with a wide variety of propositions to use in designing puzzles with the expectation that they will provide a good puzzle solving experience. L-topia isn’t just a puzzle, it’s a natural puzzle creation kit!
Why L-Topia isn’t awesome, and Agincourt is
Unfortunately, to be perfectly honest, being a “puzzle creation kit” interferes with L-topia’s accessability as a puzzle. Because the circular and square holes have no inherent meaning, but have to have their meanings imposed by a puzzle’s directions, you can’t simply take the pieces out of the box and start solving.
Agincourt, on the other hand, with its 64 squares with an arrow in each, practically begs to be turned into four 4×4 layers with the arrows aligned. Of course, there are other challenges to be found, but the one that literally comes out of the box is both elegant, and has a reasonable level of difficulty. (Some of the L-topia puzzles are better for hardcore puzzle solvers.)
Once again, I have both puzzles available for sale. Order soon for delivery by Christmas!
Polysticks (or polylines) are connected sets of segments in a square grid. (Polysticks on other grids are possible, but haven’t seen much attention.) The tetrasticks, of which there are 16, seem to be the most natural set for puzzle making. Donald Knuth has explored tetrastick problems, and posed the problem of tiling an Aztec Diamond with the 25 one-sided tetrasticks, which was solved by Alfred Wasserman. Here’s one I’ve come up with:
Problem #15: Tile the above shape with two sets of the five tetrominos and one monomino, and tile the borders of these polyominoes with the 16 tetrasticks. Here’s an attempt I made that fell short by a few tetrasticks, but it should give you an idea of the form a solution would take:
The observation that the lines formed by the pieces in a polyomino tiling could themselves be tiled by polysticks seems obvious, but I have not seen it elsewhere. After picking the 16 tetrasticks as my puzzle pieces for the polystick stage, I had to find a set of polyominoes to use. Since one of the tetrasticks is, in fact, the outline of a 1×1 square, or monomino, the monomino had to be present. A double set of tetrominoes plus the monomino gives a good quantity of segments for our tetrasticks to cover, and gives us an area of 2 * (5*4) + 1 = 41. The perimeter of the figure to be tiled is constrained by the following formula:
2 * total segments in the polystick set – sum of perimeters of polyominoes = perimeter of entire figure
In this case, (2 * (4 * 16)) – (4 + 2 * 48) = 28
So I needed a figure to tile with area 41 and perimeter 28, and came up with the shape above.
There are 136 solutions for the tetromino tiling with the monomino in the center as shown. (See these solutions in a Java solver applet.) I’ve experimented a little with the tetrastick stage of the problem by hand, and I’m convinced that there are no tetrastick solutions for most, if not all, of these tetromino solutions. But if it doesn’t work out in the case with the monomino in the center, I suspect there are enough solutions with the monomino elsewhere for it to be very likely that one will work. Many of the tetromino solutions fail to contain a site where the “+” tetrastick can be placed that doesn’t overlap the “□”.
Another issue that surfaces in this problem is horizontal-vertical segment parity. Eleven of the tetrasticks have even parity, that is, however you place them, they will always contain even numbers of both horizontal and vertical segments. Five of them have odd parity, and will always contain three segments of one orientation and one of the other. Because there are an odd number of pieces of odd parity, the parity of the set of tetrasticks as a whole must be odd. This means, without even starting to try placing tetrasticks on a tetromino solution, we can rule out the possibility of tiling it just by counting the number of horizontal or vertical segments. (Because the total is constant, we don’t need to count both.) If that number is even, the tetrasticks can’t tile the figure. The tetromino solution that I used in my attempt above has the correct (odd) parity.
I dredged this problem up from my archive of the polyforms mailing list, where I posted it in February, 2001. It got no takers then, but I thought it an interesting enough problem to deserve a second airing. I looked for other problems of this type in preparing this post, but I didn’t find anything good. Having both the area and the perimeter of the figure to be tiled constrained by the pieces used limits the possibilities a lot.
