Posts Tagged ‘torus’

Complete combination colorings on the torus

January 9th, 2017

I posted previously about my talk at Gathering for Gardner 12 on colorings of pentomino tilings. One unexpected consequence of that is that my work has now been cited in a very prestigious… um… coloring book. Alex Bellos and Edmund Harriss previously collaborated on Patterns of the Universe, a mathematical coloring book for adults, and were looking for material for the sequel. They were attending G4G12, and saw my talk, and thought that they had found some. They wanted to use something like the strict complete combination 3,4-coloring of the pentomino tiling that I showed, but for the purpose of a coloring book page, they needed something with more shapes to color. Could I come up with such?

It seemed to me that the problem called for a pentomino tiling of a torus, which they could use as a wallpaper-like pattern, repeated as many times as they needed. The choice of the particular torus to use is a matter of taste, but I thought it would be nice to maximize the minimum distance between two images of the same point. (I haven’t proven that I succeeded, but it’s close.) In coding the solver for this, I used a shortcut: instead of directly checking whether a given tiling had a coloring of the correct type, I checked whether each pentomino bordered exactly six others. This turns out to be a necessary condition, but not a sufficient one, so I manually checked a few such tilings until I found one that worked. This is the pattern that appears, in user-colorable form, in Visions of The Universe by Bellos and Harriss.

The hexiamonds were the other obvious set of 12 polyforms to try to tile with this coloring scheme. Here, there is one torus with maximal symmetry. Amazingly, my solver found just two tilings where every piece bordered 6 others, of which exactly one had the right coloring properties. Recall that the solution for the pentominoes on the 6×10 rectangle was also unique. It seems incredible to me that this problem type has yielded two instances that were so finely balanced as to be solvable, but only by the barest of margins.

Tiling tilted tori

November 15th, 2016

A friend of mine recently complained about not being able to tile anything nice with the full set of polyominoes of size 1 though 5. (No, I didn’t make that up! I have weird friends. Who are not made up.) The area of these pieces is 89, which is prime. So our usual tactic of making a rectangle using divisors of the area won’t work.

But there is in fact something highly symmetrical that these pieces can tile. And its existence follows from the fact that while 89 may not be composite, it is the sum of two squares. 89 = 25 + 64 = 52 + 82.

Taking the sum of two squares may remind you of the Pythagorean Theorem, and that is exactly where I was headed. Make a right triangle where the legs have length 5 and 8, and the hypotenuse will have a length of sqrt(89). And then, naturally, if you make a square out of four sides with that length, it will have an area of 89:
area-89-square

So I have something that indeed has the desired area, but you might complain that having sides that slice obliquely to the square grid makes it entirely unsuitable for tiling with a set of polyominoes. But suppose we stitched the pairs of opposite sides together. That would turn the figure into a torus, which “unwraps” into a repeated, plane-filling pattern:
1-5-ominoes-torus
Which we can tile! If fact, tori are generally relatively easy to tile because they have no edges, and the edge is typically the hardest part of a pattern to tile. Having small pieces in the mix, as we do here, also tends to make tiling easier. So for a challenge, we could try something harder.

Problem #44:

Find a a tiling of the torus above with the 1–5-ominoes where none of the pieces of size 4 or smaller are adjacent to each other. Touching at corners is okay, but if you can find a solution without that, that’s even better. (Weird, it’s been three years since I’ve posed a numbered problem on this blog.)

This problem runs into a wall in my current setup for solving polyform tiling problems. I typically add ugly hacks to my copy of David Googer’s Polyform Puzzler. It’s reasonably handy because it’s open source and written in my language of choice, Python. But it doesn’t include a hook for pruning the search tree when you come to a configuration that doesn’t meet a desired condition. For problems with a small enough search space this doesn’t matter; you can just filter finished solutions as long as the time needed to run a complete search is reasonable. But here the high tilability is actually a curse: the solver starts in an area of the search space where the adjacency condition isn’t met, and because the pieces are so numerous and so tilable, it can stay there for an extremely long time before it decides to change out any of the tiles placed early on. (There are technical reasons why hacking in the hook I would need appears to be difficult, but I won’t get into those here.)

Coincidentally, the area of the 1–4-ominoes, 29, is also a sum of squares:
1-4-ominoes-torus
Any parallelogram can be used as the fundamental domain of a torus. Rectangle and rhombus shaped fundamental domains can have just as much symmetry as a tilted square. (Because the square is tilted, flipping it over isn’t a valid symmetry action, though rotating it still is.) But the tilted square tori still strike me as particularly pleasing and unexpected patterns for tiling.

A Polyformist’s Toolkit: Practical Topology

May 23rd, 2013

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.

The tetrominoes, and a 5×4 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.

The tetrominoes tiling a 5×4 cylinder a cylinder

…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:
Topologies for polyomino tilings
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:

7-colored 7-omino torus

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:

The 35 hexominoes in 7 3×10 tori, 3-colored

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.