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.
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.)
I’ve found a solution where two trominoes of one kind touch at a corner. Is that a problem?
D: Oriented parallel
L: Oriented diagonal
S: Polar one-sided
That’s not a problem at all, at least until such time as somebody finds a solution where that doesn’t happen.
I’m looking at this again (new e-mail, in case anyone wonders why my icon’s different), and while I don’t have a new solution or the programming skill to do an exhaustive search, I think I can see how to accomplish such.
First, the programmer has to tell the solver to pack a 6×6 square with 5 I and 7 L trominoes. This can start unrestricted, depending how easy it is to add search parameters, although locking three I’s horizontal and two vertical will save later work.
The next restriction is to look only for solutions with a balanced three-coloring. Since my answer has two D pieces touching at a corner, you may choose to focus on strict three-colorings. And this means there is no way to “wall off” any section of the packing, so the coloring is always unique up to… uh, palette swaps. (I don’t know the math term for it.)
Last, you must check (either directly or through the solver) whether the colorings correspond to the three sets. Part of this is checking that no two pieces of the same shape and color are oriented identically. If that checks out, the color with a single I is the oriented-diagonal set. There’s no need to check each candidate orientation for any set; for instance, the “missing” L-tromino in the oriented-diagonal set is symmetric under one diagonal, but the different orientations of the other three is enough to show the other diagonal works.
The different orientations of the two I’s and two L’s in each of the two remaining sets allows either to be oriented-parallel to some axis. So all that’s left is to check that one of the sets can be polar-one-sided. That only requires either set’s two L’s to be a quarter-turn apart and not a half-turn.