Category: Zapped Puzzles

A Polyformist’s Toolkit: Symmetry Variations

~ munizao ~ 3 Comments

It lately occurred to me that there are concepts that I use (and see used by others) in creating variations on polyform puzzles that I haven’t seen explained very thoroughly, and it might be helpful if I used this space for just that purpose.

Some polyomino puzzles using symmetry variations

The first of these is the use of different kinds of symmetry in defining the set of pieces used in a puzzle. (I touched on this in my post on rectangular-cell pentominoes.) Normally, all combinations of rotations, translations, and reflections of a polyomino in a grid are considered to be equivalent. Leaving aside translations for the moment, the possible rotations and reflections of a polyomino are equivalent to the group of symmetries of a square. We can find variations on polyominoes by restricting the allowed symmetries to subgroups of that group. For example, the one-sided polyominoes are the result of allowing only rotations, not reflections. Rhombic cell pentominoes (which Kadon sells) allow 180° rotations, plus diagonal reflections. My Agincourt puzzle allows only reflections over vertical axes, assuming that the arrows are pointing vertically. Notice that it doesn’t matter which direction the arrows point as long as they point in the same direction; this suggests that what we are interested in isn’t symmetry subgroups per se, but classes of subgroups where two subgroups that are related to each other by symmetries of the square are equivalent.

What are all of the possible variations with different allowed transformations? We can generate a representative subgroup of every class by using some combination of reflection over a particular axis parallel to the grid, a particular diagonal axis, and 90° and 180° rotations. Here’s a chart of the symmetry variations this produces.

  Polyomino Type Reflection Rotation # of Symmetries
Free Either 90° 8
Parallel (a.k.a. Rectangular) y axis 180° 4
Diagonal (a.k.a. Rhombic) x=y 180° 4
One-sided None 90° 4
Oriented Parallel y axis None 2
Oriented Diagonal x=y None 2
Polar One-sided None 180° 2
Fixed None None 1

I chose the above terminology for the types (after keeping “free”, “one-sided”, and “fixed” as established terms) in order to build in some helpful mnemonics. The types with four symmetries have short names. The types with two symmetries have longer names based on the names of the types whose symmetry groups their symmetries are subgroups of. The odd duck here is “polar one-sided”, which is a subgroup of all of the larger symmetry groups, but putting “one-sided” in its name makes the types with two symmetries nicely echo the names of those with four.

Here’s a chart of the number of polyominoes of each type for a given size:

Polyomino Type 1 2 3 4 5 6 7 OEIS #
Free 1 1 2 5 12 35 108 A000105
Parallel 1 2 3 9 21 68 208 A056780
Diagonal 1 1 3 7 20 62 204 A056783
One-sided 1 1 2 7 18 60 196 A000988
Oriented Parallel 1 2 4 12 35 116 392 A151525
Oriented Diagonal 1 1 4 10 34 110 388 A182645
Polar One-sided 1 2 4 13 35 120 392 A151522
Fixed 1 2 6 19 63 216 760 A001168

(The odd entries for the polar one-sided polyominoes track those for the oriented parallel polyominoes exactly for several terms, before eventually diverging. There are 4998 9-ominoes for both, and 67792 polar one-sided, and 67791 oriented parallel 11-ominoes. It seems unlikely that this is a coincidence. Does anyone know why this occurs?)

These types can be realized geometrically by replacing square cells in a planar tiling with cells with the appropriate symmetry. Another way they can be realized is by keeping the cells square and marking them with a figure with the appropriate symmetry. This is essentially what I did by cutting arrow shaped holes in the Agincourt pieces. The latter method allows the possibility of mixing different symmetry types in the same tiling. I don’t believe I’ve seen such a problem before, so let me be the first to fill what may be a much needed gap:

Problem #28: Tile a 6×6 square with the oriented parallel, oriented diagonal, and polar one-sided trominoes. No tromino should touch another of the same type.

With these symmetry subgroup based polyform variations in mind, any type of polyform on a square grid can be transformed into an entire family of polyforms. In particular, polysticks would reward exploration in this light, which does not seem to have occurred yet. A similar analysis to the one above can be made for symmetry based variations of polyiamonds and polyhexes. Bringing translation symmetry subgroups into the picture leads to things like checkered polyominoes. I may get to these in later posts; this one was getting long enough that I needed to wrap it up.

I should note that Peter Esser’s pages on polyforms cover these variations, and that his polyomino solver program can work with any of the 8 symmetry types (but not with mixed types.) (It is, sadly, a Windows binary, but I’ve been able to make it work under Wine on Linux.)

Binary System, Decimal Star

~ munizao ~ Leave a comment

If you participated in the gift exchange at the 10th Gathering for Gardner, which was held recently in Atlanta, you would have received one of these in your bag of exchange gifts:


It is common, (but by no means required) for participants to use the number of the conference as a theme in their exchange gift in some way. I considered a ten pointed star with pieces that slot together as a promising shape for a puzzle, and I recalled that there were ten distinct reversible binary sequences of length four. (In this scheme 0011 and 1100, for example, are considered equivalent because they reverse to each other.) This meant that with four slots at intersection points, if there were two possible positions for each slot, (like up and down) there would be exactly ten possible pieces, which would make an elegant puzzle set if I used one of each. Conveniently, the pieces could be flipped horizontally to physically realize the reversal of the string. Inconveniently, the pieces could also be flipped vertically, which would invert the 1’s and 0’s, and lower the number of distinct piece shapes to six. Another problem is that some configurations of pieces could not be physically assembled. If there was a triangle of pieces where each had an up slot followed by a down going around the triangle, there would be no way to fit the third piece in, because it would simultaneously need to be slotted in from above and below.

I solved both of these problems at once by changing the inner slots to all face the same direction, and to have shallow vs. deep as their two possible states instead of up and down. Now the ten pieces can be divided into two pentagonal configurations that are connected by their outer slots, and connect to each other by the inner slots. Because every triangle in the star contains the two inner slots of a piece, the triangles are all assemblable. The pentagons must also be assemblable, because there are only four pieces with up and down outer slots, so one side of the pentagon must have two slots pointing the same direction, and that side may be placed last. And because the direction of the inner slots is forced, only horizontal flipping is allowable. Here’s a photo of an assembled puzzle, along with an unassembled set of pieces:

Mathematical niftiness aside, is this a good puzzle? I think so. It has a fair number of solutions, but neither so many that you can easily stumble upon one without applying any strategy to solving the puzzle, nor so few that you have to spend a lot of time engaged in trial and error. Let me know if you have one of these and need hints for solving it.

In an upcoming post, I’ll discuss some variations on this type of puzzle.

Why L-topia Is Awesome

~ munizao ~ Leave a comment

It’s the holiday shopping season, so I figured it couldn’t hurt to write a post or two on the puzzles I am selling.

Every mathematical puzzle designer worth his or her salt has an argument for their puzzle’s awesomeness using impressive sounding mathematical justifications. This, for L-topia, is mine.

There are 12 pieces in the set. Empirically, 12 is a good number of pieces for a mathematical puzzle. There are 12 pentominoes, and 12 hexiamonds.

The shape of the pieces, an l-tetromino, has some desirable properties. It is very highly tileable. Two factors that affect the tilability of a polyomino are its size and its symmetries. Smaller and less symmetrical polyominoes are the most tilable. The l-tetromino is the smallest asymmetrical polyomino, and the only asymmetrical tetromino, so it should be the most tilable of all.

A set of 12 l-tetrominoes tiles a 6×8 rectangle in 1114 ways. That’s probably the most for any set of 12 copies of a single polyomino tiling any rectangle, but it’s not that impressive compared to other sets containing multiple shapes. For example, the 12 pentominoes can tile a 6×10 rectangle 2339 ways. 

But because the shapes are all the same, if you mark all of them in some way to distinguish them from each other, (as the holes on the L-topia pieces do) every permutation of placements of the 12 l-tetrominoes can create a distinct tiling. Now the total number of tilings is roughly 1114 · 12!. (Actually, it’s slightly less because some of the tilings of the rectangle are symmetrical: about 55 of the 1114 solutions are symmetrical by reflection or 180° rotation, so the total is about 1059 · 12! + 55 · 12! / 2, or about 520 billion.)

Well, that’s a pretty impressive number, but having an impressively large space of possibilities does not, by itself, make for a great puzzle. In this case, however, I do think it is helpful, and I’ll explain why presently.

Suppose I think of a proposition that can apply to any of the holes in the set. For example, that the hole appears in an odd numbered row. Because there are two different kinds of holes, it may be elegant to use either the opposite of that proposition, or some proposition that is complementary in some way, to apply to the second kind of hole; in the problem illustrated by the solution above, we have the round holes in odd rows, and the square holes in odd columns. Suppose the probability of the proposition being true is ½, and suppose that the probability for each hole is independent from the others. (One must take care that the placement of holes on the pieces doesn’t fatally interfere with independence; if, for example, we had asked for circles on odd rows and squares on even rows, there would have been pieces that could not have been placed legally anywhere.) Then the probability that the proposition is true for all of the holes is 1/224. Given this piece of information, we can get an expected number of tilings where the proposition is true by multiplying that probability by the total number of tilings.

The result is about 31,000. That number is tiny compared to the size of the total space of tilings, but I can say from experience that it makes for puzzles that are challenging but solvable. And it gives us wiggle room to use propositions with probabilities that are a little smaller than ½, or for which the probabilities are not entirely independent. The result is that we can come up with a wide variety of propositions to use in designing puzzles with the expectation that they will provide a good puzzle solving experience. L-topia isn’t just a puzzle, it’s a natural puzzle creation kit!

Why L-Topia isn’t awesome, and Agincourt is

Unfortunately, to be perfectly honest, being a “puzzle creation kit” interferes with L-topia’s accessability as a puzzle. Because the circular and square holes have no inherent meaning, but have to have their meanings imposed by a puzzle’s directions, you can’t simply take the pieces out of the box and start solving.

Agincourt, on the other hand, with its 64 squares with an arrow in each, practically begs to be turned into four 4×4 layers with the arrows aligned. Of course, there are other challenges to be found, but the one that literally comes out of the box is both elegant, and has a reasonable level of difficulty. (Some of the L-topia puzzles are better for hardcore puzzle solvers.)

Once again, I have both puzzles available for sale. Order soon for delivery by Christmas!

Rectangular Pentominoes

~ munizao ~ Leave a comment

When I had Agincourt made, I purchased a bulk order of 4″ × 4″ × 1″ white cardboard jewelry boxes. They look quite nice, and they fit both Agincourt and L-Topia, but I have enough of them that I’m on the lookout for ideas for polyform puzzles that fit nicely into a few square layers. And now I’ve found one:

I stumbled upon this by noticing that there are 21 pentominoes of this symmetry type, which could make three 5 × 7 layers. I wanted square layers; usefully, squashing the cells into rectangles with a 5 : 7 ratio of width to length simultaneously gave me the square layers and gave the cells the right type of symmetry.

It’s been observed that any of the subgroups of the symmetries of the square can be used as the basis for a type of polyomino puzzle. (See Peter Esser on pentomino variations, and particularly the page on parallel polarized pentominoes, which are equivalent to rectangular pentominoes.) For Agincourt, I physically realized one of these types by laser-cutting symmetrical, arrow-shaped holes in every square cell. Other types have been made by changing the shape of the cells themselves. Rhombic pentomino sets have been produced by Kadon as Rhombiominoes. Sets of rectangular polyominoes, shaped like Meiji chocolate bars, have been produced by Hanayama. (These may not be equivalent to the rectangular polyominoes above, if the top is distinct from the bottom, which isn’t clear from the pictures there.) I’m not aware of anyone who is producing complete sets of rectangular pentominoes, so there’s a gap I’m willing to step into.

If you take out the pentominoes with a diagonal line of symmetry in their non-squashed form, (the green ones above) the remaining 18 pentominoes come in 9 pairs, where each pair contains two different squashed versions of the same pentomino. With these pieces it is interesting to try to tile a pair of shapes with the same orientation such that one piece from each piece pair is in each shape. (Note that if the two shapes had different orientations, you could always make the second shape with corresponding pieces in the same position as the first, but squashed in the other direction.)

Since the set has area 90, the obvious thing to try is two 9×5 rectangles. The next most obvious thing to try is two 7×7 squares with corners removed. Neither of these seem to work, although I have no proof.

One thing that does work is a 7×7 square with a 4×4 square cut out of one corner. But this is again just the case where you can trivially get the solution to the second piece by squashing the pieces differently, because this shape has diagonal “mirror symmetry”.

Another problem is finding three congruent shapes, each of which has the following property: three of its pieces have their twin in one of the other two shapes, and three have their twin in the remaining shape:

I’m looking into having some sets of the rectangular polyominoes made, and if I can do so economically, I’ll sell them through the store. (Sadly, TechShop Portland, the facility where I made Agincourt, has gone away, so I will need to look at other options.)

Introducing Agincourt (to the Blog)

~ munizao ~ 2 Comments

Agincourt is one of the lasercut acrylic puzzles which I’m selling through the store. It’s the set of all of the ways to make 2-, 3-, and 4-ominoes with arrow shaped holes in each square pointing in the same direction. The symmetry of the arrows means that you can flip over pieces without changing the arrow directions, but you can’t rotate them. Most of the puzzles I have designed for the set ask for the solver to make all pieces point the same way, but the arrows naturally suggest a scoring system to handicap the puzzle for different levels of solvers — just count the number of pieces you had to put in the wrong direction, and try to improve on your score.

Here’s a solution to the puzzle that literally comes out of the box. (The puzzle comes in the box with 4 layers of pieces in 4 × 4 squares.)

Expect more Agincourt puzzles later.