Archive for the ‘Recreational Mathematics’ category

Monomatch Dice

July 12th, 2021

A game called “Spot It!” has received a lot of attention from recreational mathematicians in recent years. There’s a good video by Matt Parker, and a blog post about it by one of my five readers. (Hi MJD!) The game contains a number of cards each with eight symbols, and the object is to be the first to spot the matching symbol between the pair of cards. The designers of the game, in finding an elegant set of cards where every pair has exactly one match, used a structure that can be understood in terms of finite projective geometry. Parker calls these monomatch sets of symbol sets.

This led me to consider monomatching on symbols on the faces of a pair of dice. (I guess I’m on a roll with the dice content here. Sorry, there’s really only one decent dice related pun; if you try to stretch beyond that, things get dicey.) The obvious thing to do with a pair of d6’s is to have a set of 36 symbols. You could consider the symbols as being arranged in a 6×6 grid. The faces on one die would each contain all of the symbols on one row, and the faces on the other die would each contain the symbols on one column. For an added trick, the numbers 1 through 6 could be six of the symbols, and if they are on a diagonal of that grid, the dice could be used as regular dice by ignoring the non-numerical symbols.

This seems like an idea worth exploring, once my laser engraver arrives. There is a version of Spot It! with 30 cards and 6 symbols per card that is marketed to be played by young children, so it seems like it would be somewhere near the realm of playability. (Adding dice beyond the first two might help.) And although Spot It! already comes in a compact tin, there’s not much that’s more portable than a pair of dice. But there’s not really any kind of interesting puzzle to be found in it, so I was hoping to find something else to do with symbol matching on dice.

And I did come up with another idea, and it is good, and it is dumb. Imagine, if you will, that you could use a pair of dice as… 2d6!

Here, unlike with Spot It!, it’s desirable to make spotting the match be easy, so I’ve put the numbers in order and used colors as an aid.

But not, of course, 2d6 as we know it. Instead of adding numbers on the two dice, we’d have the numbers 2 through 12 as symbols for matching. The frequencies in which the numbers occur on the two dice would have to be such that the probability of getting a number as a match would be the same as the probability of getting that number as a sum using a regular pair of d6’s.

2d6 rollFrequencyFaces per die
211, 1
321, 2
431, 3
542, 2 or 1, 4
651, 5
762, 3 or 1, 6
851, 5
942, 2 or 1, 4
1031, 3
1121, 2
1211, 1

Now, finding a set of number sets for the symbols on the faces of each die becomes an interesting puzzle, especially if we add constraints to make our dice more nice. One type of constraint we might care about is on the quantity of numbers on each die. Minimizing the total quantity on both of the dice would be good, as would be balancing the quantities on the dice.

Unfortunately, we cannot do both. The minimum total quantity is 43, which is odd. So in order to balance the quantities, we need to use the inefficient alternative for either 5 or 9. (Using the inefficient alternative for 7 doesn’t change the parity of the total, so I’ve dismissed that option.)

We could try to go further in our pursuit of balance. The solution I found above has balanced number quantities on the two dice, but at the level of faces, there are issues. The first set has face quantities of {2, 3, 3, 4, 5, 5}, while the second has {2, 3, 4, 4, 4, 5}. Having the same face quantities between the two dice would be desirable, especially if it could be done while minimizing the number of faces with five numbers, since those faces look more cluttered.

You could also drill down to the numbers themselves. The sum of all of the numbers on the upper die above is 158, while the sum on the lower die is 148. Ideally, we’d make those sums equal, or at least closer.

Problem #50: Find a “nicer” numbering for a pair of monomatch 2d6 dice than the one I found. One potential flaw that I haven’t mentioned already is having a pair of faces on the same die with identical number sets. When I was manually looking for numberings, they seem to want to have pairs like this, so they are harder to avoid than you might think.

Shaker Dice and Edge Labelings

June 21st, 2021

Last year I saw an interesting Kickstarter campaign for “shaker dice”. The product was shaped like a credit card, with a number of reservoirs with tiny balls. Instead of tossing, you would shake the device and then read off random numbers based on where a specially colored ball ended up in a channel below the reservoir. When the campaign failed to fund, I felt pretty motivated to produce my own version, for a couple of reasons. First, it used lasercut plastic. This is a medium I’ve used for a bunch of puzzles, so I felt that the design work would be pretty straightforward for me. Second, they just got the implementation all wrong.

This was the top image on the campaign page for that Kickstarter. The first clue that they didn’t understand their market is they thought folks would not want more dice.

To see why I thought that, let’s take a step back, and consider what the function of dice actually is. It seems obvious, at first glance, it’s just to produce a random number. But I’d argue there’s more to it than that. Games are social; what you really want is to communicate a random result to other people around a table. This is why you can expect to get a bit of side-eye if you bring a D-Total to a D&D night.

It’s eighteen dice in one! Want to know what number I just rolled? It’s really simple, just read the included manual.

The biggest problem with No More Dice is that because it produces a large number of different results at the same time, it doesn’t communicate which one is the one you care about. So the first change in my design was to split each die into a separate item. I also wanted to increase the size of the balls and the numbers at the positions where the balls end up, in order to make the dice readable from farther away. There was an important practical limitation; the thickest available plastic sheet for the middle layer was 4.9mm thick, so I was looking at 4mm balls. That’s not really enough to make numbers that are readable from across a table, but at least you can see the positions of the balls reasonably well.

At this point, it became clear that the size of the dice was going to be an issue. Even a d4 would be bigger than most regular dice; a d6 would be huge, and d10 or above would be entirely impractical, once we consider that you’d be carrying each of the standard RPG dice together as a set. Getting to a full set of dice that gamers might consider reasonable was going to take a bit of creativity.

My first observation was that I could abandon the biggest selling point of No More Dice: that you didn’t have to toss them. Early on, I decided that I wanted there to be a bit of padding on the back of the dice so you could set them down on a table and let gravity hold the balls in place at the bottom of the channel. But if there was padding on the front side as well, and the dice had numbers on both sides, and you could toss them… my d4 could also be a d8. Uh oh. Multiple functions? Was I heading down the dark path to the D-Total? It’s a fair worry, but, most importantly, the result requires no interpretation. It’s still just the number above the specially colored ball. Second, the physical gesture used communicates which die was rolled. If I shook it and set it down, it was a d4. If I shook it and tossed it, (so it could land on either side with equal probability) it was a d8.

That idea was enough to get me most of the way to a full set. The same principle could give me a d6/d12, and a d10 with 5 balls. (The d10 could also be a d5, but since that isn’t a standard die, it seemed better to balance the numbers by putting the odds and evens on opposite sides.) Two problems remained. The d6/d12 was bigger than I wanted it to be, and there was just no reasonable way to get a d20.

There was a good reason to hope that solutions existed. Having only one ball be distinguishable from the others leaves a lot of potential information unused. In principle, with 5 balls of different colors, there are 5! permutations, or enough for a d120. Just one that requires a manual to decode a numerical result from the permutation. If only there was a genuinely good die-roll decoding technique. Something where a single symbol would be enough to tell you how to find your result, no manual required. Something that gamers already do all the time with the results of dice rolls. Something like basic arithmetic.

In fact, the answer was a mathematical structure that I already knew about, in another context. A perfect Golomb ruler is a way of marking a line with n marks such that each of the integers between 1 and n choose 2 is one of the distances between two marks. One perfect Golomb ruler with 4 marks is {0, 1, 4, 6}.

Another model for the same structure is a “graceful labeling” of the edges of a complete graph. We label the nodes with integers, and the edge labeling is induced by taking the absolute difference of the nodes on that edge. By using two specially colored balls whose positions correspond to nodes on the graph, the edges give us our die-roll results. Slap a minus sign on the die, and what you need to do is clear enough.

That allows us to have a d6 that is the same size as the d4, but now we’ve lost the d12 that occupied the same die. Can we get it back? Not with a graceful labeling, unfortunately, but if we use addition rather than subtraction on the other side of the die, we can get all of the numbers between 7 and 12 using {3, 4, 5, 7} as our set of numbers on the other side.

We could, in fact, have used addition on both sides of the die, as the sums from {0, 1, 2, 4} also give us 1 through 6. Complete edge labelings induced by addition have been studied by mathematicians as well: they’re called “harmonious labelings”. (The usual definition uses addition modulo the number of edges. I didn’t think gamers were likely to put up with mod though, so I’m not using it.) While I could have gone with the design with addition on both sides, I ended up preferring the one with a plus side and a minus side, mostly because it echoes what I used for the d20.

Right, the d20. Taking 5 choose 2 gives us 10 for the number of possibilities given two specially colored balls out of five. It would be really great if we could pull off the same trick that we used for the d6/d12, by getting 1 through 10 on one side of the die and 11 through 20 on the other side. Alas, no combination of addition and subtraction on the two sides of the die will allow this. However, if we remove the requirement to have it also be a d10 we can get all of the numbers for a d20 with addition on one side and subtraction on the other. I wrote Python code using Google’s or-tools constraint solver to find valid numberings; the one I went with is {0, 1, 5, 18, 20} on the minus side and {1, 2, 5, 7, 9} on the plus side.

And that’s the entire set of standard RPG dice! It worked out pretty nicely that the whole set could be done with just two different sizes of the same design, each with a one dark ball version, and a two dark ball version with extra arithmetic.

As a coda, I did put some thought into what could be done with 6-ball shaker dice. One dark ball gives us my original d6/d12 design. Two dark balls gives us 6 choose 2 = 15, from which we could make a d15 or d30 if any solutions existed. But they do not. Three dark balls — well that would be ridiculous. 6 choose 3 is 20, so you could get an alternative d20 that didn’t require tossing, or a d40 that does. But what would you even do for labeling such a die? I settled on adding the two outside numbers, and subtracting the middle one. A d20 wasn’t possible, but a d40 was:

It’s utterly chonky, and makes you do an entirely unreasonable amount of arithmetic, all in order to give you a die that absolutely nobody needs — and I kind of love it.

This is How I Roll: Non-transitive Pips

April 29th, 2021

A set of three non-transitive dice has the property that if you roll two of them and compare numbers, the first tends to beat the second, the second beats the third, and the third beats the first. I recommend this article by James Grime, which describes how these dice work and covers some more recent variations on the theme.

Red beats blue and blue beats green, both on 7/12 of rolls. Green beats red on 25/36 rolls.

I recently acquired some Sicherman dice with indented pips, which inspired me to use acrylic paints to color the faces so that matched colors on a die roll indicate doubles, in the manner described in this post. Since I had a method for altering dice, I wondered if there was anything interesting I could do with standard pipped dice.

Non-transitive dice inspired an idea: what if we could color the pips with three different colors so that, with a single roll of one die, the results are non-transitive over the pip counts of the three colors? Some experimentation showed that it is in fact possible:

Unlike the usual non-transitive dice, ties occur on these. For a roll of 1, a tie between the two missing colors is inevitable, and for a roll of 2, either one color is used, and the other two tie, or two colors are used, and those two tie. It’s possible to have those be the only ties, but I prefer the symmetry of having each pair of colors give the same results, so I want one more tie. Here, white beats red, red beats blue, and blue beats white, all with a 3-2 record, with one tie.

The “standard” non-transitive dice shown at the top have the interesting property that if you roll them twice, the results become non-transitive in the opposite direction. I found that there are no individual non-transitive pip dice that have this property, but there are pairs of dice that work. For example, you could add this die to the one above:

This die works the same way as the previous one as an individual die. (White beats red, red beats blue, and blue beats white.) But when you roll both dice together, white beats blue, blue beats red, and red beats white.

Problem #49: There are sets of 4 and more non-transitive dice, where each beats the next in a cycle. Can there be a non-transitive pip die with four colors, or even five? Since the total number of pips is 21, the number of pips of each color would have to be unbalanced (or the remainder pip could use a neutral color.)

Sparse and Magic Squares

April 20th, 2021

A while back, I had the insight that the 3×3 magic square could be transformed into a sparse square, or a set of cells within a square in a grid where every row and column contains the same number of cells. The converse transformation of turning a sparse square into a magic figure is not original to me, but applying it to the sparse square from the first transformation gave a pleasing result. And then I stopped there.

Or I almost did:

Right, so if I had set the 1 where the 34 is, and the 6 where the 26 is before running the solver, (and likewise the 4 and 9) that would have been more elegant.

This is a figure I came up with before my blogging hiatus that never made it into a post. The rows, columns, main diagonals, and 3×3 blocks all sum to 115. This could be seen as a version of my doubly transformed magic square on a slightly degenerate 3×3 magic square whose entries are all 5’s.

But it was hard to see where to go from there. The next size up, the 4×4 square, was unsuitable. Its magic sum is 34, and since we’d be using a 4×4 block, we wouldn’t be able to evenly split the squares from each row and column into four lines. And 5×5 seemed big enough to be a mess to work with. So I was done.

But it turns out we can do something nice with the 4×4 after all. Suppose we number the squares starting with 0 instead of 1. We still can’t use 4×4 blocks, but since the highest value is now 15, 3×5 blocks look like a possibility. And indeed, our magic sum is now 30, of which 3 and 5 are both factors, so it works:

There was an interesting bug in the code I used to produce this. I was looking for figures that are single, hole free polyrects. One way to help filter these out from other solutions is to check for 2×2 blocks with checkered corners. If one is present, you must have either a hole or more than one polyrect. But by accident the constraint I added was more broad; it applied to any 2×2 block with two dark and two light rects. I was not able to get a single polyrect solution with this constraint, but I did find something at least as interesting. Notice that every 3×5 block is the same, after swapping dark and light, as the complimentary block with the number that you get by subtracting from 15. This was not an explicit constraint in my code, so it’s interesting that this property managed to emerge. I still haven’t found a single hole-free polyrect solution without the buggy constraint, but I’m confident they are out there. My solver code is just too inefficient to find them in a reasonable amount of time.

Once I was back on the trail of magic sparse squares, I came back to the magic partition square I discussed in a previous post. (There are four ways to partition the numbers from 1 to 8 into two subsets of four numbers that sum to 18. Each of the 8 subsets is present as a row or column in the square.) Since this figure uses smaller blocks, my solver had no trouble with it.

My work on magic sparse squares is ongoing, and I hope to have more to share with you soon. I’ve put my solver code up on GitHub. I know I’ve had a long hiatus without coming up with new material, but I expect to have a few more blog posts in the coming months, and I hope you’ll enjoy the shiny objects that I find and share.

More pentomino coloring problems on torus tilings

April 8th, 2018

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

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

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

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

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.

A Pocketful of Pentapennies

May 12th, 2017

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

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

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

A pentomino train

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

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

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

Pentomino Painting Robots

February 1st, 2017

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

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.