Archive for February, 2018

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