Tag: hexominoes

Touring Tilings

~ munizao ~ Leave a comment

A few months ago, I noticed that a king can tour a pentomino tiling so that every cell in each pentomino is visited exactly once in an uninterrupted sequence, and the tour forms a closed loop.

Not every pentomino tiling admits such a tour, but it’s not hard to find one that does. A more restricted form of loop could be made using a wazir (an archaic chess piece that moves one cell orthogonally, W for short) instead of a king. Such loops would be more challenging to find. They also restrict the polyominoes that can occur, for example, only 8 of the pentominoes are available.

There are 18 hexominoes that can be traversed by a wazir without visiting the same cell twice. They can make a W-tourable tiling of a 9×12 rectangle:

When I posted this to the Puzzle Fun Facebook group, Rodolfo Kurchan referred me to a previous exploration of similar pieces in the Journal of Recreational Mathematics. It covered the W-traversable 2- through 5-ominoes, (called “rookominoes” in that source) which have an area of 64, and can tile an 8×8 square. But the passage that Kurchan shared only mentioned tiling the pieces, and didn’t consider tours at all! Could they really have been that close to discovering tours on tilings, and just missed them? I adapted my PolySolver model that I used for the above hexomino tiling to find tilings of these pieces instead. Polysolver could find solutions for this set about 10,000 times faster than for the hexominoes. That made me feel that these toured tilings ought to be well within range of manual solving. Surely the JRM contributors could have found them.

I was intrigued, and wanted to find out if there was more about these rookominoes in the JRM than just that brief passage. I looked up the JRM on WorldCat, and found that there was a copy at Reed College, only about 10 miles away from me.

So I drove over, and found where the JRM bound volumes were kept in the basement of the Reed College library. The material I wanted wasn’t in an article per se, but in a section titled “Solutions to Problems and Conjectures”. I found the piece that Kurchan shared from 1990, but also several more from later issues over the next several years. It turned out that the JRM contributors did indeed consider W-tours on these pieces, and Brian Barwell found the first solution. Another variation considered was maximizing the number of loops. Barwell and Michael Reid found a seven loop solution:

They note that the I pentomino cannot be part of a loop of fewer than three pieces. All of the 12 remaining polyominoes, excepting the square tetromino, cannot make a loop alone. So for all of the pieces to be used, there must be at most six more loops, so seven is the maximum.

These problems are related to the snake polystick Hamiltonian circuit problem I posted some time ago. The paths that the tours take within polyominoes are in fact snake polysticks. One difference is that there are extra monosticks connecting these snakes where the path crosses from one polyomino to the next. Another is that we are taking a complete set of polyominoes rather than a complete set of polysticks. For example, we only use one of the two tetrasticks that can traverse a P pentomino. We could instead use an extra P pentomino, and require that both snake tetrasticks occur.

I’ve left this exercise in library spelunking excited about the possibilities for tours on polyform tilings, but a little saddened about the state of polyform knowledge in the world generally. When I did a web search on “rookominoes”, the only results were indices to Stanford’s archive of Martin Gardner’s papers. (There’s something in Box 54, folder 18. It is highly unlikely that I will ever see the contents of that box.) The Journal of Recreational Mathematics wasn’t too hard to track down, given Kurchan’s tip, but who would even know where to look? With the original publisher defunct, I couldn’t find even an index of article titles not behind a paywall, not that that would help me find material strewn between different “Solutions to Problems and Conjectures” columns over several years. Cubism For Fun has an online index, and back issues are purportedly available, but ordering very many of them would be prohibitive. As for the Polyforms Yahoo group, there I’m up on the rest of the world; I have everything since I joined on my hard drive. Good luck to the next poor soul looking for anything to be found there though. The Puzzle Fun Facebook group should stay around for as long as it takes for Meta to go the way of Yahoo. And everything here? Once I’m no longer around to pay for hosting, it goes into the limbo of stuff you can only find via the Wayback Machine, and only if you already know where to look.

Rescued by Flexible Polyominoes

~ munizao ~ 2 Comments

See the previous Flexible Polyomino post here.

One unfortunate lesson that you quickly learn about tiling problems involving a full set of (free) n-ominoes is that the pentominoes are the only really nice set. Monominoes through trominoes are trivial. And tetrominoes and hexominoes have checkerboard parity problems. Here’s an example. Suppose we wanted to tile a figure containing five copies of a 6×7 rectangle with the hexominoes. (It might be a 30×7 rectangle, or a 35×6 rectangle, or something more fanciful.)

These rectangles (suitably checkered) have an odd number of both black and white squares, and since an odd times an odd is odd, so do five of them. But 11 hexominoes are “even” (they will always cover an even number of both black and white squares) while 24 are odd (they cover an odd number of squares of each color.) Since an even number times an odd number must be even, there must be an even number of squares of both colors in both the even and odd hexomino subsets, and thus also in the full set. So our figure is impossible to tile.

But flexible polyominoes come to our rescue. This figure, formed from five of the above rectangles with a little distortion, can be tiled with hexominoes!

Why does it work? Well, consider what it would mean to checker the underlying cells. There is a cycle of five cells around the center. If you color one of the cells white, then as you go around the center, the next cells would be black, then white, then black, then white again. But the following cell would be the one where we started, and it would have to be black! So you can see that whenever we have an odd cycle of cells, we can’t have a consistent 2-coloring, and the checkerboard parity argument above no longer applies.

Note that there’s no magical property of flexible polyominoes involved here, just the presence of an odd cycle. The following figure has no odd cycle, so checkerboard parity applies, and it turns out to be untileable with the hexominoes.

Checkerboard parity problems can only occur with sets of even-sized polyforms. Our next odd size is the heptominoes, but here a new problem emerges. One of the heptominoes has a hole:

Thus every heptomino tiling must either incorporate a hole or omit the holey heptomino. Either solution is inelegant. Flexible polyominoes rescue us once again!

Solution by Edo Timmermans

The holey heptomino is there, but the hole is not. Can you find it?

Once you move to the octominoes and beyond, “opening” a holey polyomino can require breaking a connection between cells, so we’ll stop here. But the 9-iamonds, like the heptominoes, have a single holey piece where the hole is pinched together with disconnected “fingers”.

Problem 54: Tile this figure with the flexible 9-iamonds. There are 160 9-iamonds, which brings us into the zone where we’d want a pretty efficient solver in order to make headway.

This gets us through most of the 2022 Flexible Polyform Renaissance material that I wanted to post, but there is still enough for a brief coda, which I hope to complete soon.

Revenge of Flexible Polyominoes

~ munizao ~ Leave a comment

Several months ago, I felt myself at a bit of a creative ebb. I wasn’t coming up with any bold new polyform ideas, so the best I could do would be to tinker around in a space that was already well-trodden. In this state of mind, I asked myself: did Abaroth miss anything good?

When I came up with the idea of letting the cells in polyominoes be flexible rhombi, Abaroth ran with it, and made an entire gallery of tilable shapes with solutions. Some of Abaroth’s discoveries used rows of squares as seams between the “leaves” of a target shape, but he missed this nice pentomino star:

An obvious thing to want after seeing a tiling like this with five-fold dihedral symmetry is one with sixfold dihedral symmetry. So far, the attempts have run into some problems.

The tiling on the left is Abaroth’s. It contains a couple of ambiguous pentominoes in the upper right. Where the green one wraps around a degree-3 vertex, it could be “unglued” to form either an X or an F pentomino. The red one could be an L, an N, or a Y.

The tiling on the right is mine, and has a different problem. The P pentomino in the upper left is not ambiguous, but it is split. This type of flaw can only occur in a polyomino that contains a square tetromino; P is the only pentomino that does.

Problem #53: Find a flexible pentomino tiling with sixfold dihedral symmetry without ambiguous or split pentominoes.

One-sided flexible polyominoes were another area that had been missed. It turns out that there are some nice tilings here:

George Sicherman, Abaroth, and Edo Timmermans all found one-sided pentomino tilings for the above double star. This double balanced three-coloring found by Edo Timmermans is particularly nice. Remarkably, the one-sided hexominoes also admit a double star:

(Solution again by Edo Timmermans.)

It might not be clear at first that other symmetry variations on polyominoes will survive in this weird flexible world, but in fact some can. If squares can flex into rhombi, then rectangles can flex into parallelograms, and we can get tilings like the following, using the 3-, 4-, and 5-rects:

For the second post in a row, I’m going to stop with at least another post’s worth of material left to share. If I leave you in suspense, you’ll have to keep coming back, right?

A Polyformist’s Toolkit: Practical Topology

~ munizao ~ 6 Comments

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.

3×3 block Pentominoes and Hexominoes

~ munizao ~ 1 Comment

There are 8 pentominoes and 8 hexominoes that fit in a 3×3 cell. The combined set seems to cry out to be presented in a 4×4 grid of 3×3 blocks, with the pentominoes and hexominoes in checkered positions:

The best I could think to do was make a figure that is connected, hole-free, and has a rotationally symmetrical pattern of connections between blocks. I had hoped to make them into a geomagic square, but now I’m pessimistic about that working. And the trick from my magic 45-ominoes of making all rows and columns have the same number of cells in polyominoes won’t work here because the total number in each row of 3×3 blocks is 22, which isn’t divisible by 3.

I’ve looked before at problems involving moving a single cell at a time to cycle through a set of polyforms. Because this set has equal numbers of pieces at two consecutive sizes, it invites using adding and removing single cells, rather than moving them, as the action for taking one piece to the next in a path:

Because the X pentomino has only one possible predecessor or successor, it cannot be part of a cycle, but it is still possible to make a path through all of these pentominoes and hexominoes with the X as one of its endpoints.