Notation Notions: Operations on Ominoes

~ munizao ~ Leave a comment

Here’s a tiling of the 3+2-ominoes:

This use of a plus sign seems natural enough, but we might want to think a bit more about what it implies. We have established an operation on polyform sets, and a notation for that operation. This raises some questions: what other operations might we want to use? How should we notate them? And finally, can we design a notation system that readably describes a wide variety of polyform sets? (And should we?)

After addition, a notation for multiplication would be handy. We’ve recently looked at di-triamonds and tri-diamonds. We can call these 2·3-iamonds and 3·2-iamonds respectively. Notice that this multiplication, unlike the addition, doesn’t commute. But it does decompose into addition in the natural way; the 3·2-iamonds are the same as the 2+2+2-iamonds.

In a way, we were already using polyform multiplication to define n-forms in the first place. The pentominoes are essentially the 5·monominoes. In the interest of brevity, we can use symbols for common base monoforms:▲, ■, ⬣, and ◣ for the moniamond, monomino, monohex and monotan respectively. If we are consistent with the above examples, a n■ has subdivisions for the individual cells. That may seem a little weird, but it can be useful; a 2×1 rectangle could be either a domino or a tetratan, and we’d like to be able to know which. I won’t show these subdivisions in my graphics unless it aids with clarity.

We would also like to combine sets together into a larger one. This is multiset addition rather than set union, because we could want to work with multiple copies of the same polyform. I’ll use circled operator symbols for multiset operations, even though that’s a little nonstandard. They’re nicely readable, and the circle will be our mnemonic that we’re doing multiset things. The tetrominoes and pentominoes together would be 4⊕5■. We can read the ‘⊕’ as “and”, so 4⊕5■ is read as “the four and five -ominoes”. Making a set from multiple copies of the same set is the same as scalar multiset multiplication. So five copies of the tetrominoes is 5⊙4■. As before, this is non-commutative left multiplication; the dot is our mnemonic for that. And it decomposes as expected into multiset addition: 5⊙4■ = 4⊕4⊕4⊕4⊕4■. I can’t think of any reason I would ever want to do element-wise multiset multiplication with polyforms, but ⊗ is there if I ever need it.

Now that we have multiset operations and polyform connection operations, we can start to combine them. There are 22 4+1■. I hope to share more problems involving them soon, but one thing I noticed was that with some smaller pieces included I could get an area of 144, and make a square. With my notation system, I can call these 2+1⊕3+1⊕4+1■. Or I could write that as (2⊕3⊕4)+1■. Polyform addition distributes over multiset operations!

(Well, I could have made a square. I’m showing this shape instead because PolySolver wasn’t finding solutions for the square with separated monominoes. Thanks to Bryce Herdt for showing me a technique for getting PolySolver to find solutions with this property.)

Finally, I must address the final question from the start of this post. Is a notation system for polyform sets actually a reasonable thing to develop, given that I am a lone crank and nobody else is likely to use this stuff? And I think that I am finding, for my own explorations with polyforms, that the answer is yes. With algebraic notation, the concepts behind the notation can be expressed with words, and were for a long time. But symbols are easier to mentally manipulate, and formulas that could not fit into working memory as a paragraph can do so as a modest number of symbols. I am already finding it easier to think about polyform sets because I have symbolic notation for them. As I hinted in my fuzzy polyominoes post, I’m working on notation for related concepts, so more posts on polyform notation are sure to follow.

Fuzzyominoes: Weighty equivalence

~ munizao ~ Leave a comment

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.

Polysticks and Polyominoes, Together at Last

~ munizao ~ Leave a comment

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!

Three paths to pick from, part 2: Distant connections

~ munizao ~ Leave a comment

I promised two more path puzzles in part 1, and their time has come. When I posted recently about “starmaps” as a variation on edgematching puzzles, my variation there was actually the second puzzle inspired by them that I had found recently. The first was this set of 2×2 square tiles with one cell being marked with 2 orthogonal or diagonal arrows. (The tiles can be flipped.)

Part of the inspiration to use arrows may have come from the game of Trippples, [siccc] which uses a complete set of fixed square pieces with arrows in three directions. I recently read about Trippples in issue 7 of Abstract Games magazine. Once I had these squares with arrows, a puzzle challenge seemed natural: connect the arrows into a single path, which may not enter any cell with arrows in any direction that does not correspond to an arrow.

Problem 61: Find a closed circuit using these pieces. I spent enough time finding the path above; I suspect that a closed circuit may be solvable if you have the patience of a Lewis Patterson, which I do not.

One element I like to consider in puzzle design is non-locality. A puzzle exhibits non-locality if, when you are placing a piece, you must consider pieces that are not immediately adjacent. Most polyform and edgematching puzzles are generally local. If half of a puzzle frame is filled, pieces in the interior of the filled region do not directly affect how new pieces can connect to the edge of that region. (Of course, I am eliding the fact that they reduce the set of remaining pieces that are available to place.) In the above puzzle, the empty space allows long distance connections, turning path-making into a non-local problem.

My Color Tubes puzzle from my Edge Collection Connection set of edgematching card puzzles was also a path puzzle with non-local considerations. I neglected to introduce it on the blog back when I produced the set, so let’s remedy that now.

The configuration shown is a solution to the challenge of placing the pieces so that each tube has three segments of three different colors. Segments can break in the middle of a card, or at a connection across a card boundary with non-matching colors. (Here, the cards cannot be flipped over; the back sides of the cards contain a second, related puzzle.) Other challenges for the cards are placing them so there are two differently colored segments, or four. This was definitely more of a “designed” puzzle than a “discovered” puzzle, which was a bit of a departure for me. I’ll have another excuse to muse about the distinction in a future post, but at this point I’ve hinted at more than one future post, so they can’t all be the next one.

With a couple of instances of non-locality under our belts, can we say anything useful about it as a puzzle design tool? In the case of Color Tubes, I think it gives it a little more depth than a typical 3×3 edgematching puzzle, which would seem to be welcome. In the arrow path puzzle, it adds difficulty and complexity, but the result is a little too much difficulty and complexity, at least for my tastes. It is a spice that should be judiciously applied. But then, so is hinting at coming posts, and that won’t stop me from teasing more material about non-local puzzles in the near future!

Border Marking

~ munizao ~ Leave a comment

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

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

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

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

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

And here are the pieces individually:

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

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

~ munizao ~ Leave a comment

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

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

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

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

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

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

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

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

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

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

Edgematching to the Stars

~ munizao ~ 1 Comment

The best known combinatorially complete set of edgematching tiles are the 24 squares with 3 edge colors discovered by Percy MacMahon. These can be rotated, but not flipped over. I showed an illustration of them when I first discussed edgematching puzzles on this blog. And now I’ll do it again!

Can we find an even more basic set? After all, 3×3 square edgematching puzzles were common as advertising promotions in the first half of the 20th century. A set of 24 tiles seems excessive. And surely 2 edge colors would be simpler than 3.

The problem is that with 2 colors, you get only 6 tiles, and they don’t make an interesting puzzle at all. But if you use tiles with fixed orientation, you get 16 tiles. Per David Singmaster’s Sources in Recreational Mathematics, this set was described by J. J. M. Verbakel in 1975. We’ll use a line pointing out of a side to represent one of the colors, and a blank edge to represent the other, as this convention will help us to make better visual sense of some of the later figures.

They still don’t make a very good puzzle, as the above solution is basically trivial, so even adding the restriction that only one color can touch the border adds no challenge. But as a starting point for further exploration, they lead in some very interesting directions. Christian Freeling shows some of these on his page on the “BackSlide” puzzle, which turns the pieces into a double-sided sliding 15-puzzle. (Freeling’s site also contains information about variations of these puzzles using hexagons as well as squares with diagonal connections.)

The binary nature of the colors allows us break out of the 4×4 square. Instead of both colors matching themselves, we can arrange the tiles into sets of polyominoes where one color matches itself, and the other matches an outer edge. Freeling calls these “transcendental” solutions. Finding these is still not much of a puzzle, but any unusual polyomino recreation is appreciated around here!

Breaking up the tiles further leads to the “starmaps” discovered (in the hexagonal context) by Martin Medema. Here, we place these tiles on an 8×8 board. A line pointing out of a piece must connect, at some distance, to one pointing out of another piece. An empty edge must see only empty space in its direction. Conveniently, there are 32 empty edges, exactly as many as edges in the perimeter of the board. Freeling states that it is “considered good form” for no tiles to be adjacent. If we don’t use good form, it is not hard to transform a regular transcendental solution into a starmap by breaking it apart until no empty edges see each other. Finding a good form starmap isn’t a trivial puzzle at all.

My impetus for this post was an idea I had for a new type of starmap. We might require one edge type to match an adjacent instance of itself, and have an additional edge type that must see itself from more than one square away, enforcing “good form” for that type. The third edge type must see only empty space as before. There would be 81 fixed orientation pieces with three edge types, which is way more than I want to deal with. Surely there must be some better set with three edge types.

Right, the MacMahon tiles! There are 32 instances of each edge type, so we can use an 8×8 board again. I found this puzzle to be quite challenging.

Puzzles with sparse (or sparse-but-clumpy) piece placements are unusual and visually distinctive, and I hope to encounter more like these.

Tantalized by Polytans

~ munizao ~ Leave a comment

There are two fundamental methods for deriving a type of polyform. One is to begin with a tessellation, and consider connected subsets of that tessellation as its associated polyforms. The other is to begin with a single tile, and create instances of a polyform type by agglomeration of ever more copies to the starter tile. Regular polygon tiles do not allow us to distinguish between these methods. The triangle, square, and hexagon give us the same polyforms whether you use their planar tilings or accretion, and the other polygons do not tile the plane at all, and so admit only the latter method.

The tan, (a.k.a. isosceles right triangle) by contrast, does admit both methods in a way that gives us distinct sets of polytans for each. There are 3 different isohedral tilings of the plane with tans:

The first two are topologically equivalent to an equilateral triangle tiling, and polytans based on those tilings can be treated as equivalent to polyiamonds with restricted symmetry actions. But the last one, the tetrakis square tiling, does give us its own set of polyforms. George Sicherman has catalogued the tetrakis grid polytans. (Polytans are called polyaboloes there and in some other sources.) Since both tessellation and agglomeration methods give us reasonable polyform sets from the same base cell, pithier terms for each are desired, so I will go with “grid” and “glom” respectively. Due to the freer choices of orientations for tans, the glom n-tan sets grow much more quickly than the grid n-tans. Here are tilings of the 30 glom pentatans and the 8 grid pentatans:

The glom pentatans solution is from the Poly Pages.

A consideration for both grid and glom polytans is whether we choose to include all of the shapes with the same outline, but different internal divisions. If our only use for a set of shapes is to make a tiling, it may feel awkward to have extra copies of some of them. I fall on the side of preferring sets where all subtilings are present, because they may be relevant for problems other than tiling, and even tiling problems with additional challenges based on the subtilings. (I propose we use the terms “subtiled” and “unsubtiled” to distinguish the cases where different internal tile placements do and respectively do not give us distinct polyforms. There are other polyform types where this distinction is useful; consider polydominoes and polydiamonds.)

The pentatans in the above graphic are unsubtiled. In fact, for grid polytans up to size five, subtiling doesn’t give us extra pieces. But as we go up to hexatans, it does. Here’s a tiling of the subtiled grid tri-ditans:

Notice that there are two L tromino shaped pieces with the same first level subtiling into squares, but a different ultimate subtiling into tans, as well as two trapezoid shaped pieces with different first level subtilings, but the same ultimate subtiling. There is some subtlety in subtiling! [Edit: well, as pretty as that is, I missed a tri-ditan. There’s an S-shaped one with two big tans and a square in the middle. Darn.] [Later edit: okay, here’s the best I can do: use the 16 tri-ditans in the above figure to tile an inflated version of the missing one.]

There are 18 subtiled glom di-ditans, which, fortuitously, can tile a square. I set the additional challenge of finding such a tiling where there was symmetry in the orientations of the base tans. Bryce Herdt found this one:

Herdt reported that this appears to be the only one with this property upon a visual scan of all of the tiling solutions, but it’s possible another might have been missed.

I have, perhaps unjustly, ignored polytans before now. My first inclination when presented with a type of polyform is to ask, does this really give us any insights that we couldn’t have gotten from polyominoes or polyiamonds? When I found my first internet polyformist community in the Polyforms Yahoo group, there seemed to be quite a lot of exploration of new polyforms, and a lot less of new questions to ask about polyforms. So I focused on the latter, and mostly stuck with the most basic polyform types in order to keep to that path. But polytans really do give us important insights, and I hope to find and post about more of them in the future.

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