# Edgematching with Catalan number patterns

March 11th, 2017 by munizao

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.

1. Jake Wildstrom says:
2. Jake Wildstrom says: