# A Polyformist’s Toolkit: Practical Topology

May 23rd, 2013 by munizao

In polyomino puzzles, we would frequently like to tile the simplest shape possible, and a rectangle usually seems to fit the bill. But sometimes a rectangle isn’t possible. For example, we can never make a 4×5 rectangle with the five tetrominoes. One way to prove this is with a checkerboard parity argument. Four of the 5 tetrominoes must always occupy even numbers of both black and white squares if they are placed on a checkerboard. The T tetromino must occupy odd numbers of each color. Therefore a rectangle must have odd numbers of each color, but any rectangle of size 20 will have colors evenly divided, 10 and 10. A similar argument can be made to show that the 35 hexominoes cannot tile a rectangle.

This will never work…

Rather than give up and accept that we’ll need to find a less elegant shape to tile, we have another option. If we wrap the edges of a 5×4 rectangle around to form a cylinder, (so that the cylinder is 4 squares tall and 5 squares in circumference) tiling is once again possible. To see why this might be so, imagine that you are coloring the squares as in a checkerboard. Once you got back around to where you began, you would find that in order to continue the pattern, you would need to use the opposite colors from those you already used. Note that this would not work if you wrapped the rectangle in the other direction; because the other side has even length, the checkering colors remain consistent.

…until we wrap the rectangle into a cylinder.

There is a video by Edo Timmermans showing how a tetromino cylinder can be made with toy magnets. He claims that there are seven distinct tilings of a cylinder with the tetrominoes, and poses an interesting puzzle involving them. A commercially produced cylindrical polyomino puzzle is Logiq Tower, designed by Marko Pavlović, which uses wooden pentomino-based pieces that form a cylinder together with some other pieces. Because these pieces are inflexible, they lack some of the allowable symmetry actions of free pentominoes.

A cylinder isn’t our only option. We could give the rectangle a half-twist before connecting the ends; this gives us a Möbius strip. We could also connect both pairs of sides instead of one; this gives a structure that is topologically equivalent to a torus or doughnut. And then we could add twists to that— well, at this point it would be nice to be systematic so we can be sure that we’ve found all of the possibilities. One thing to note is that adding more twists doesn’t actually give us more possibilities. A strip with two twists will have exactly the same tilings as a strip with no twists, and in general, a strip with an even number of half-twists will have the same tilings as the no-twist strip, and a strip with an odd number of half-twists will have the same tilings as the Möbius strip. So for each dimension, we have three options: no connection, connection without a twist, and connection with a half-twist. This gives us the following matrix of possibilities:

Only six possibilities here, not nine, because the ones in the lower left are equivalent to the ones across the main diagonal from them. Note that the Möbius strip, Klein bottle, and projective plane are nonorientable surfaces, which means that they effectively have only one side.

An important consideration when working with these is that one-sided polyominoes don’t exist on nonorientable surfaces. With one-sided polyominoes, translation is allowed, but reflection isn’t. However, on a non-orientable surface, translating far enough leaves an object in a reflected state.

Another consideration is that coloring is harder when we leave the plane behind. On the plane, we have a theorem stating that we never need to use more than four colors to make all of the tiles differ in color from all of their neighbors. On a torus, this may require seven colors. In 2001, Roger Phillips found 18 heptominoes that could tile a 7×7 torus, and sent these tilings to MathPuzzle.com. Here’s one:

Depending on the dimensions of the torus, it may be possible for a polyomino to wrap around and touch itself. In a strict sense, this makes any coloring impossible, since we don’t let tiles of the same color touch. However, we can follow a looser standard, and allow self-touching polyominoes in our colored tilings. Patrick Hamlyn found a 3-coloring of a tiling of the 35 hexominoes in 7 3×10 tori using this scheme in 2003:

This problem has no solutions if the tori are replaced with rectangles or cylinders.

Problems #31-37:
Though it seems like a pretty basic problem, if anyone has counted the number of pentomino tilings of cylinders, I am not aware of it. Wrapping the short sides of the 3×20 together should not give any solutions beyond the two obtained by wrapping the solutions on the 3×20 rectangle. That leaves the 3×20 wrapped the other way, and both ways of wrapping the 4×15, the 5×12, and the 6×10 rectangles.

Problems #38-40: Find the solution counts for the 4×15, 5×12, and 6×10 tori. I don’t know if these are all computationally tractable, but I can hope. (The 3×20 will be the same as the 3×20 cylinder with long sides wrapped together.)

Even more possibilities for tiling become available when you choose parallelograms with diagonal sides to wrap around, but this post is long enough, so that will have to be a matter for another post.

1. In Polyform Puzzler (http://puzzler.sourceforge.net), I actually have a puzzle for the long edges connected 3×20 puzzle, which I call a tube (pentominoes-3×20-tube). I never ran it to completion before, but I did just now, and came up with 48,928 solutions.

However, that number depends on how we define unique orientations of pieces. If we consider wrapped-around pieces to be continuous where one end meets another, then that number may be accurate. But there would be more solutions were the duplicate-detection mechanism to differentiate between cases where a piece can wrap around in multiple ways to occupy the same space (e.g. the N pentomino vertical); it doesn’t now.

2. munizao says:

Huh, that’s more than I would have thought, and the running time suggests that some of these, (like the tori) may be out of the realm of tractability. I should have thought to check Puzzler before I wrote this up. I had a vague feeling I had seen a 3×20 cylinder somewhere, and I guess that must have been where.

The point about ambiguous pieces is one that I hadn’t considered; I’m glad you brought it to my attention.

3. munizao says:

And now I’ve tweaked Puzzler to give a few counts. All of these are loops with the long sides wrapped around, (that is, with the short sides connected together.)

4×15: 901 solutions
5×12: 8,272 solutions
6×10: 28996 solutions

David: I’ll send my code to the Puzzler email list soon.

4. munizao says:

And 10×6: 576,619 solutions. That’s all of the cylinders that don’t have the ambiguity problem.

5. Re your vague feeling that you had seen a 3×20 cylinder before, perhaps it was these “ring walls”: http://puzzler.sourceforge.net/docs/solid-pentominoes.html#ring-walls

The 3-D ring walls are more restrictive than flexible 2-D cylinder surfaces. Pieces cannot span two sides beyond the 90° corners.

6. I programmed the 5×4 tetrominoes tube today:
http://puzzler.sourceforge.net/docs/polyominoes.html#tetrominoes

And yes, there is one solution that has a different base shape (#4).