More pentomino coloring problems on torus tilings

April 8th, 2018 by munizao | Print this post

Recently I revisited one of my old pentomino coloring problems, modified to apply to a tiling of a torus rather than a rectangle. That worked out well, so I might as well shamelessly continue to mine this vein.

There are 18 one-sided pentominoes. Six of them have reflection symmetry, and the other 12 are 6 sets of mirror pairs. A while back, I asked if there was a tiling with a three-coloring where the 6 with reflection symmetry share a color, and each mirror pair has one pentomino of each of the remaining two colors. Patrick Hamlyn found that there was no rectangle tiling that could be colored in this way, but there was such a tiling of the shape below: The one-sided pentominoes have area 90, which is the area of a tilted square on a grid: Problem #47: Find a tiling of a torus with this tilted square as its fundamental domain by the one-sided pentominoes with a three-coloring as described above. If possible, find a tiling with no crossroads.

Another older problem that could be adapted to a torus is the minimal 2-colored packing problem. Here’s my conjectured minimal 2-colored pentomino packing of a rectangle: (I had forgotten that this was problem #1 on this very blog!)

Problem #48: Find a two-colored packing by the pentominoes of a torus with minimal area.

Obviously, you could just take the rectangular packing above and add a one unit “moat” around it to get a torus with a 14×6 rectangle as its fundamental domain, but surely we can do better.

Vexed by Convexity, part two

March 25th, 2018 by munizao | Print this post

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: Flexible pentominoes on rhombic polyhedra

February 26th, 2018 by munizao | Print this post

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

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

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

February 11th, 2018 by munizao | Print this post

Recently* I was perusing the section on edge matching puzzles on Rob’s Puzzle Page. While puzzles using a 3×3 square grid are the most common, one that I found interesting was the 2×3 grid “Matador” puzzle, where matches form dominoes with doubled numbers of pips. Possibly to compensate for the reduction in size, an extra rule requires that not only must edges match, but one match must be present for each pip number between 0 and 6. My first impulse was to find the simplest complete set that would work as a puzzle. There are 6 different cyclic permutations of a set of four different numbers. Why not try edge-matching with cards using these? It turns out that this is a pretty easy and not terribly interesting puzzle.

However, in exploring the space of similar puzzles, I found what I think is a particularly elegant gem. If we use cards with edge values between 0 and 8, there are 17 different sums between 0 and 16, which is the same number as the number of internal edges in a 3×4 grid of 12 cards. Coincidentally, 12 is also the number of sets of different numbers between 0 and 8 that sum to 16, so those can be the sets of numbers on our 12 cards.

The last detail is the matter of how we arrange those numbers. Making all of the cards have clockwise ascending edge values is simple enough, although it hurt my symmetry senses to have to pick a direction. And indeed, we don’t have to, because we can make the cards flippable, so that the other sides have values in counterclockwise ascending order. Luckily, the flippable cards are just what the puzzle needed to handle another issue: without them, the puzzle would be unpleasantly hard to solve. In addition to the collect-all-the sums puzzle, simply matching the numbers makes a good puzzle with this set: A third challenge is to make a 4×4 square with the corners removed such that every difference between values at the same edge between 1 and 8 occurs exactly twice. I believe I solved this at some point, but I didn’t record the solution, so I can’t show it to you right now.

As you may have noticed, the last puzzle set has higher production quality than the first two. That’s because I’ve had a prototype custom deck of cards made including several different puzzle sets. I intend to have a small run of these made to sell.

*By recently, I mean, whatever was recently last June, when I started writing this post. I don’t mean to only finish blog posts during the earlier part of the year, but it does seem to tend to work out that way.

Vexed by Convexity, part one

February 2nd, 2018 by munizao | Print this post

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.

The Devil’s in the Angles

July 27th, 2017 by munizao | Print this post

Recently, while I was considering possible designs for a puzzle for my exchange gift for the next Gathering for Gardner, I thought about doing something with multiple layers of clear plastic, where interactions of markings on the layers define the puzzle. When you’re going to lasercut a large quantity of puzzles, keeping down the cost, and therefore the cut length, is paramount. So I wanted to be able to use the simplest possible markings on the pieces.

A straight line segment looked like a pretty good candidate, and it leads to an obvious puzzle goal: make the segments on two layers perpendicular. I still needed to choose pieces for these markings, but after a little trial and error, I landed on dominoes, with a segment centered in each square. For these, given some reasonable restriction on the allowable angles of the segments, the number of different pieces possible would land somewhere in the range of what would make for a good puzzle.

I ended up using segments that were turned either 15° or 45° off from the edges of the pieces. These admit exactly 12 different pieces, which can tile two layers of a 3×4 rectangle: What makes this set particularly nice is that you can get two more puzzle challenges by changing the goal angle for the crossing segments. In addition to making them all perpendicular, you can make them all cross at 30° or 60°. These challenges should be easier, as there are two ways for an angle to differ from another one by 30° or 60°, but only one way to be perpendicular.

I also found a related puzzle that uses 10 dihexes. There are 13 pieces possible in this scheme, but I’ve omitted the ones with a lengthwise axis of symmetry from the puzzle: In the end, I decided not to make either of these my exchange gift. I had a couple of prototypes made of the first puzzle, and it was clear to me that it needed to be larger than I could afford to make it and give away a few hundred copies. It also works best with a frame to hold the pieces and keep them neatly aligned, which adds considerably to the time and expense per copy. But even though I won’t be able to give this away at G4G13, I hope to be able to be able to sell a few copies at my vendor table there!

A Pocketful of Pentapennies

May 12th, 2017 by munizao | Print this post

We can think of two connected unit coin configurations (or polypennies) as being equivalent if we can transform one into the other by reflection and/or sliding coins without changing which coins are adjacent. (Coins may not overlap.)

There are 13 pentapennies. A tiling with fivefold rotational symmetry may be possible, but I haven’t been able to find one. (This is problem #27.) However, I recently found a way to tile a figure with fourfold rotational symmetry with them: Since I’ve had trouble with five symmetries, you’d think ten would be out of the question. But I found a repeating pattern on the plane with ten symmetries that can be tiled with the pentapennies: Notice that there are five translation symmetries. Reflecting the pattern on a vertical axis gives five more symmetries. This pattern uses the wallpaper group cm. (Conway orbifold symbol: *×) We could also try to find a tilable pattern with the same amount of symmetry using the wallpaper group p2. (Conway orbifold symbol: 2222)

Problem #45: Find a tiling of the pentapennies on a repeating pattern on the plane that has at least as many symmetries as the one above, but a different wallpaper group. I don’t think going above 10 symmetries is possible, but I’d love to be surprised.

Edgematching with Catalan number patterns

March 11th, 2017 by munizao | Print this post

Edgematching puzzles are a genre that I haven’t previously explored very deeply. A classic example is the MacMahon squares puzzle. If you subdivide a square diagonally into four triangles, there are 24 ways to color the triangles using three colors. Using a set of 24 squares with all of the possible colorings, it is possible to make a 6×4 rectangle where all of the edges match. As I was pondering the possibility of designing my own edgematching puzzle, I considered that pieces with multiple colors are a bit of a pain to make with a laser cutter. However, engraving lines is relatively easy. And I found a promising set of line patterns related to the Catalan numbers. The Catalan number sequence (1, 2, 5, 14, 42, 132…) is one that comes up in a surprising variety of contexts. For example, Catalan(n) is the number of distinct ways that n pairs of matched parentheses can occur in a string. For n = 3, we have ()()(), (()()), ((())), ()(()), and (())().

Replacing the parentheses with diagonal lines, and stretching them until they connect, we can make the following figures: We can place these figures around the edges of a square, and use them to do edgematching— but with a new twist as to what counts as a match. Looking at the patterns that are made when two of these figures meet at an edge, we see that one thing that distinguishes them is the number of loops they make. One, two, or three loops can be made. This gives us three different puzzle objectives: place the pieces of the puzzle so that all internal edges have the same number of loops, where that number can be one, two, or three. The fact that there are three loop numbers is promising because it means that, on average, the probability of an edge in these three puzzles being a match will be one-third, the same as in the MacMahon Squares puzzle. This table shows the possible edge patterns, colored according to the number of loops: From the perspective of puzzle design, it’s convenient that the proportion of pattern matches of each type is different; this seems likely to result in puzzles that are correspondingly different in difficulty, which is desirable. The table also reveals symmetries in how the edge figures form the different types of patterns. If you swap both the rows and the columns of the mirror pair of figures, you get a table with the same loop numbers in the same places, as we would expect. Perhaps more surprisingly, this also works with the first and second rows and columns. Thus those two edge figures form a sort of hidden symmetric pair. If you swap all instances of one in a puzzle solution with instances of the other, you will get a second solution.

There’s still one task remaining before we have a puzzle design: choosing the pieces. The MacMahon squares puzzle used every possible piece. Since we have five edge types here, instead of three, that would give us more pieces than we’d really want for a good manual puzzle. There are probably several reasonable options here, but in the interest of prototyping, I wanted to start with a small piece set, so I decided to explore a set of nine pieces with bilateral symmetry. Here’s a solution with single loops: And here’s a double loop solution for comparison: I’ve already had prototypes made of this puzzle, and it feels promising. I hope to have at least one more post about variations on this design, but for now I’ll stop here.

Pentominoes on paths and trees

February 3rd, 2017 by munizao | Print this post

Here’s a path that could be taken by a chess king. All subpaths of length four describe a different pentomino: This led from the grid of pentomino painting instructions that I posted previously. Consider a string of arrows for which the subsequences of length 4 include instructions for producing all 12 pentominoes. (This is somewhat analogous to a de Bruijn sequence.) For the case shown, the string is ←↑↖→→→→↓↓←↓←↘↗↓, although the graphic seems more illuminating than the arrow string here.

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

Pentomino Painting Robots

February 1st, 2017 by munizao | Print this post

In the diagram below, each row (reading from left to right) and column (reading from top to bottom) gives instructions for painting one of the 12 pentominoes: Sometimes an idea languishes in one of my notebooks for a few years before I can come up with the right iteration of it. My original idea here was to use a 4×4 grid. That would give me 8 pentominoes, (perhaps 10 using diagonals) but elegance surely requires all 12 to be present.

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

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

Finally, a Magic Magic 45-omino

January 14th, 2017 by munizao | Print this post

In the figure below, the numbers in each row, column, and main diagonal sum to 115: Quite a long time ago, I came up with the idea of representing the lo shu (3×3 magic square) as a set of squares in a 9×9 grid, partitioned into nine 3×3 cells. The number of squares in each cell would correspond to a number in the lo shu. The most “magic” way to arrange the cells would seem to be to have 5 squares in the set in each row, column, and main diagonal. (This can be done because the lo shu’s magic sum of 15 can be divided among three rows or columns.) Although it doesn’t affect the “magicality” of a figure, I thought it aesthetically desirable for such a figure to be connected (i.e., a single polyomino) and hole-free. There are 12 hole-free magic 45-ominoes, if my code for discovering them is correct.

A figure with the same number of squares in each row, column, and main diagonal makes an ideal canvas for a sparse magic square. But with 45 numbers to place, and 20 constraints to meet, we start to push on the edge of what’s computationally feasible. The solver I wrote (which, I admit, might not have been very good) could not find a solution. Bryce Herdt manually tweaked the output of my solver to make a semimagic solution, that is, one where the rows and columns add to the magic sum, but the diagonals still didn’t work.

When I discovered that the Numberjack constraint engine could easily be used to code solvers for magic figures, I tried it on this problem, but got nowhere. The solver would run for an arbitrarily long period of time without spitting out any solutions. Recently I tried it again, and this time I got solutions. Paradoxically, what made the problem easier to solve was that I added more constraints. I manually placed the numbers 1 through 9 in the 3×3 cells that they correspond to. This seems to have made the search space small enough that the solver would not be able to spend an inordinate amount of time stuck in a barren zone.

Complete combination colorings on the torus

January 9th, 2017 by munizao | Print this post

I posted previously about my talk at Gathering for Gardner 12 on colorings of pentomino tilings. One unexpected consequence of that is that my work has now been cited in a very prestigious… um… coloring book. Alex Bellos and Edmund Harriss previously collaborated on Patterns of the Universe, a mathematical coloring book for adults, and were looking for material for the sequel. They were attending G4G12, and saw my talk, and thought that they had found some. They wanted to use something like the strict complete combination 3,4-coloring of the pentomino tiling that I showed, but for the purpose of a coloring book page, they needed something with more shapes to color. Could I come up with such? It seemed to me that the problem called for a pentomino tiling of a torus, which they could use as a wallpaper-like pattern, repeated as many times as they needed. The choice of the particular torus to use is a matter of taste, but I thought it would be nice to maximize the minimum distance between two images of the same point. (I haven’t proven that I succeeded, but it’s close.) In coding the solver for this, I used a shortcut: instead of directly checking whether a given tiling had a coloring of the correct type, I checked whether each pentomino bordered exactly six others. This turns out to be a necessary condition, but not a sufficient one, so I manually checked a few such tilings until I found one that worked. This is the pattern that appears, in user-colorable form, in Visions of The Universe by Bellos and Harriss. The hexiamonds were the other obvious set of 12 polyforms to try to tile with this coloring scheme. Here, there is one torus with maximal symmetry. Amazingly, my solver found just two tilings where every piece bordered 6 others, of which exactly one had the right coloring properties. Recall that the solution for the pentominoes on the 6×10 rectangle was also unique. It seems incredible to me that this problem type has yielded two instances that were so finely balanced as to be solvable, but only by the barest of margins.

Tiling tilted tori

November 15th, 2016 by munizao | Print this post

A friend of mine recently complained about not being able to tile anything nice with the full set of polyominoes of size 1 though 5. (No, I didn’t make that up! I have weird friends. Who are not made up.) The area of these pieces is 89, which is prime. So our usual tactic of making a rectangle using divisors of the area won’t work.

But there is in fact something highly symmetrical that these pieces can tile. And its existence follows from the fact that while 89 may not be composite, it is the sum of two squares. 89 = 25 + 64 = 52 + 82.

Taking the sum of two squares may remind you of the Pythagorean Theorem, and that is exactly where I was headed. Make a right triangle where the legs have length 5 and 8, and the hypotenuse will have a length of sqrt(89). And then, naturally, if you make a square out of four sides with that length, it will have an area of 89: So I have something that indeed has the desired area, but you might complain that having sides that slice obliquely to the square grid makes it entirely unsuitable for tiling with a set of polyominoes. But suppose we stitched the pairs of opposite sides together. That would turn the figure into a torus, which “unwraps” into a repeated, plane-filling pattern: Which we can tile! If fact, tori are generally relatively easy to tile because they have no edges, and the edge is typically the hardest part of a pattern to tile. Having small pieces in the mix, as we do here, also tends to make tiling easier. So for a challenge, we could try something harder.

Problem #44:

Find a a tiling of the torus above with the 1–5-ominoes where none of the pieces of size 4 or smaller are adjacent to each other. Touching at corners is okay, but if you can find a solution without that, that’s even better. (Weird, it’s been three years since I’ve posed a numbered problem on this blog.)

This problem runs into a wall in my current setup for solving polyform tiling problems. I typically add ugly hacks to my copy of David Googer’s Polyform Puzzler. It’s reasonably handy because it’s open source and written in my language of choice, Python. But it doesn’t include a hook for pruning the search tree when you come to a configuration that doesn’t meet a desired condition. For problems with a small enough search space this doesn’t matter; you can just filter finished solutions as long as the time needed to run a complete search is reasonable. But here the high tilability is actually a curse: the solver starts in an area of the search space where the adjacency condition isn’t met, and because the pieces are so numerous and so tilable, it can stay there for an extremely long time before it decides to change out any of the tiles placed early on. (There are technical reasons why hacking in the hook I would need appears to be difficult, but I won’t get into those here.)

Coincidentally, the area of the 1–4-ominoes, 29, is also a sum of squares: Any parallelogram can be used as the fundamental domain of a torus. Rectangle and rhombus shaped fundamental domains can have just as much symmetry as a tilted square. (Because the square is tilted, flipping it over isn’t a valid symmetry action, though rotating it still is.) But the tilted square tori still strike me as particularly pleasing and unexpected patterns for tiling.

Faux Shu Follies

June 18th, 2016 by munizao | Print this post The Lo Shu, or 3×3 magic square, was discovered in China in antiquity. It is the only way, (up to symmetry) to place the numbers 1 through 9 in a 3×3 grid such that the numbers in each row, column, and main diagonal add up to the same number (or magic sum). This fact seems to be universally known among recreational mathematicians. So when I had the chance to meet a number of them this spring at the fabulous 12th Gathering for Gardner conference, I told them that I knew a different way to do it. When they pronounced me mad, or a liar, I showed them one of these: Mathematics is full of counterexamples that result when the simple way of understanding a conjecture is not exactly what the conjecture literally says, so this kind of cheating is totes legit.

If the fact of the uniqueness of the Lo Shu is new to you, a quick proof might be in order. First, let’s enumerate all of the sets of three numbers between 1 and 9 that sum to 15: {1, 5, 9}, {1, 6, 8}, {2, 4, 9}, {2, 5, 8}, {2, 6, 7}, {3, 4, 8}, {3, 5, 7}, {4, 5, 6}. There are eight sets, so we’ll need all of them to fill the eight lines in the magic square. The number 5 appears four times, the other odd numbers appear twice, and the even numbers appear three times. Therefore the center square, being part of four lines, must be 5, the corner squares, being part of three lines, must be the evens, and the side squares, being part of two lines, must be the other odds. Choose any corner, and put a 2 in it. That forces 8 into the opposite corner. Choose one the remaining corners, and put a 4 in it. After that, the rest of the numbers are forced. No matter what corners you choose, the result can be rotated or flipped to get the square formed by choosing any different pair of corners. Q. E. D.

Well, wait, you say, what if the magic sum isn’t 15? Quite right, 14 and 16 also both have eight sets of numbers between 1 and 9 that sum to them, so our proof is not done. I will leave it as an exercise to the reader to show that they cannot be used to form a 3×3 magic square.

And then, once the reader is satisfied, I’ll say: there is a way to place the numbers 1 through 9 in a 3×3 grid, with exactly one number in each cell, (you didn’t think I’d try the same shenanigans twice?) so that they occupy eight lines that each connect exactly three numbers that sum to 14. And having followed me this far, you are now enough of a recreational mathematician to be able to call me mad, or a liar. But you might want to have a look at this before you wager money on it: This result was adapted from one discovered by Lee Sallows, which is described in his book, Geometric Magic Squares.

Well, clearly the problem here is that you’re allowing me to draw my own graphics. If you forced me to use physical number tiles as in the first image, I couldn’t get up to any fancy tricks. So if I told you that I could arrange those exact same nine number tiles in a block of three rows of three tiles each, and make it so that for every line that passes through the center of three tiles that form a connected group, the sum of those tiles is 14, I would have to be mad. Mad as a loon.