Posts Tagged ‘polyominoes’

The Devil’s in the Angles

July 27th, 2017

Recently, while I was considering possible designs for a puzzle for my exchange gift for the next Gathering for Gardner, I thought about doing something with multiple layers of clear plastic, where interactions of markings on the layers define the puzzle. When you’re going to lasercut a large quantity of puzzles, keeping down the cost, and therefore the cut length, is paramount. So I wanted to be able to use the simplest possible markings on the pieces.

A straight line segment looked like a pretty good candidate, and it leads to an obvious puzzle goal: make the segments on two layers perpendicular. I still needed to choose pieces for these markings, but after a little trial and error, I landed on dominoes, with a segment centered in each square. For these, given some reasonable restriction on the allowable angles of the segments, the number of different pieces possible would land somewhere in the range of what would make for a good puzzle.

I ended up using segments that were turned either 15° or 45° off from the edges of the pieces. These admit exactly 12 different pieces, which can tile two layers of a 3×4 rectangle:


What makes this set particularly nice is that you can get two more puzzle challenges by changing the goal angle for the crossing segments. In addition to making them all perpendicular, you can make them all cross at 30° or 60°. These challenges should be easier, as there are two ways for an angle to differ from another one by 30° or 60°, but only one way to be perpendicular.

I also found a related puzzle that uses 10 dihexes. There are 13 pieces possible in this scheme, but I’ve omitted the ones with a lengthwise axis of symmetry from the puzzle:

In the end, I decided not to make either of these my exchange gift. I had a couple of prototypes made of the first puzzle, and it was clear to me that it needed to be larger than I could afford to make it and give away a few hundred copies. It also works best with a frame to hold the pieces and keep them neatly aligned, which adds considerably to the time and expense per copy. But even though I won’t be able to give this away at G4G13, I hope to be able to be able to sell a few copies at my vendor table there!

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.

A Polyformist’s Toolkit: Symmetry Variations

May 25th, 2012

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.)

Polyform Link Roundup

March 25th, 2012

There have been a few recent developments worth noting in the world of polyform puzzles:

Rodolfo Kurchan has posted Puzzle Fun #25. Some good new coloring problems using multiple sets of polyominoes.

David Goodger has been doing some good work on triangular and hexagonal grid polysticks.

George Sicherman is continuing to make advances in the realm of polyform compatibility problems. He also recently posted a catalog of the polypennies up to order 6.

KSO Glorieux Ronse is a school in Belgium that has, over the past decade, conducted a wonderful educational experiment by posting contests based on polyomino problems that could be engaged with by their own students just as much as the world’s puzzle solving elite. (The latter tended to win, of course.) Their 50th contest, which they state was their final one, was held late last year. They solicited the polyform puzzle community for problems to use in the contest and got quite a few, including one from me. No word yet on the results of the contest, (or their previous one for that matter) but the problems there are still pretty interesting.

I’ll be at the 10th Gathering for Gardner (G4G10) this week, and I expect that I’ll come back with quite a lot to think and post about. If you’re going to be there, my talk on Flexible Polyforms has tentatively been scheduled for the Thursday morning session. I hope to see some of you there!

Maximal Irreducible Contiguous Covers

April 28th, 2011

A cover of a set of polyforms is a shape (or set of shapes) into which each member of the set could fit. Mostly I’ve looked at problems involving minimizing the size of a cover. This problem goes the other direction.

A reducible cover is one where a cell can be removed and the remaining figure is still a cover. An interesting problem then is to find an irreducible cover in a single piece that is as large as possible. (Why a single piece? Well, without specifying that, the largest irreducible cover will simply be all of the shapes in the set in separate pieces.) Here’s a (conjectured) maximal irreducible contiguous cover (MICC) of the pentominoes:

The above solution has been on my polyomino cover page for a while. Here are a couple of new results, (still just conjectured since I found them by hand rather than exhaustive computer search, and I am not able as yet to prove they are maximal.)


An MICC (?) of the hexiamonds


An MICC (?) of the pentaedges (shown in two copies for clarity)

Between these solutions, we see some patterns emerging. Certain polyforms are in some sense distinctive: they have features that do not occur in other polyforms in the set. This makes it easy to make a large cover that includes exactly one copy of them. Other polyforms end up serving a connective function. For example, there are quite a few occurrences of the L pentomino in the first figure, so removing a cell will never make the cover cease to include an L. By using a few pentominoes as many times as possible in this connective function, more pentominoes are left over to occur singularly.  In some cases multiple polyforms that occur only once are forced to overlap, so we don’t get their full number of cells to add to the cover, but we do get a few. This is shown with the outlined hexiamonds above. In the case of the pentominoes, we have one cell where two T pentominoes overlap; since these are the only two T pentominoes in the figure, the cell can’t be removed from the cover.

Problem #25: Find maximal irriducible contiguous covers of anything and everything! This problem ought to yield interesting results for any kind of polyform you can throw at it.

One final note: It was slightly unfortunate that I chose the word “cover” to represent a concept in polyforms when it already had an unrelated meaning in graph theory; it’s even more problematic now that I’m using graphs themselves as polyforms. It appears that in graph theory, the appropriate term is “common supergraph”. I could use “common superform”, although one problem is that polyforms, unlike graphs, are generally not allowed to be disconnected, and for some problems (though not this one) we want sets of polyforms that aren’t connected to each other. Perhaps “common superformsets” in that case, as ugly as it sounds.

A Semimagic Magic 45-omino

March 1st, 2011

Bryce Herdt has found a solution to problem #21:

The shape of the darker region is “magic” because the number of cells in each 3×3 block corresponds to a number in a magic square, while the number of cells in each row, column, and main diagonal is 5. The sum of the numbers in each row and column is 115.

There’s still room for improvement here: note that the diagonals do not add up to the magic sum. (A mostly magic square with this property is called semimagic.)

Problem #21.1 Find a magic magic 45-omino, as above, but with diagonals adding to the magic sum.

It’s interesting that this solution was found by manually tweaking the output of a program that I wrote to solve the problem. I was never able to get the program to find an actual solution, so I had it give up after a certain number of trials and output the best near solution. There may well be a large number of solutions, but the search space is enormous.

It’s pretty simple to get fairly close by picking a random permutation of numbers and repeatedly swapping them around to get sums closer to the magic sum. But getting from this local minimum to a real solution is the hard part. The problem would seem to call for something like simulated annealing, and indeed I found a reference to a magic square finder algorithm using something similar. (It should be noted that if all you want is a magic square of a given size, there are deterministic methods that will get you one very quickly.) I added a hack to my code to make it do a crude version of this, but it doesn’t seem to have helped much. (The near solution that Herdt fixed up was made with the old version of the code.)

Feel free to look at my solver code (in Python). I do wonder if there is some way it can be fixed up to be better at getting from near solutions to real solutions.

3×3 block Pentominoes and Hexominoes

January 21st, 2011

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.

Magic Squares and Polyominoes

January 21st, 2011

Lee Sallows recently created a new site, geomagicsquares.com, about geometric magic squares. These differ from standard magic squares in that the numbers are replaced with shapes, and instead of having a magic sum which all of the rows, columns, and main diagonals must add up to, they have a target shape that the shapes in each row, column, and main diagonal must tile. (As in standard magic squares, each entry in the square must differ from all of the others. I really recommend the site highly; the presentation of the geometric magic squares is nearly as beautiful as the underlying mathematics. Many (but not all) of the geometric magic squares there use polyominoes or other polyforms.

Several years ago, I came up with a different way of combining polyominoes and magic squares. My magic 45-ominoes are polyominoes contained in a 3×3 configuration of 3×3 blocks, such that each row, column, and main diagonal has 5 cells within the polyomino, and each 3×3 block has a number of cells corresponding to a number in a magic square.

After reading Sallows’ site, I wanted to try my own hand at a geomagic square, and I came up with a variation that incorporates ideas from my magic 45-ominoes:

The rows and columns in the diagram all contain 5 cells. I wasn’t able to make the main diagonals work out. Maybe you can?

#20: Find a geomagic square of polyominoes that can be presented in a 3×3 grid of 3×3 blocks as above, where all rows, columns, and main diagonals have an equal number of cells that are contained within polyominoes.

By the way, I’m still looking for what I call a Magic Magic 45-omino; that is, a Magic 45-omino where each cell contains a different number between 1 and 45, and each row and column adds up to 115. (Make that problem #21.) Here’s a near solution:

All Pentominoes in 5

December 13th, 2010

I’ve been thinking about variations on the problem of cycling through all twelve pentominoes by moving a single cell at a time. (I wrote about this in a previous post.) Constraining the way that the squares are allowed to move led to something almost like a chess problem.

The problem:

Starting with the above position, take five turns as follows:

A turn consists of moving one white knight, then moving one black knight, according to standard chess rules.

After each turn, the squares occupied by the ten knights must form two separate pentominoes.

After the fifth turn, all twelve pentominoes must have appeared exactly once. (This includes the two that are present in the starting position.)

[I may make a separate post discussing and spoiling the puzzle later.]

Rectangular Pentominoes

October 29th, 2010

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.)

Polystick Problems from Polyomino Solutions

September 7th, 2010

Polysticks (or polylines) are connected sets of segments in a square grid. (Polysticks on other grids are possible, but haven’t seen much attention.) The tetrasticks, of which there are 16, seem to be the most natural set for puzzle making. Donald Knuth has explored tetrastick problems, and posed the problem of tiling an Aztec Diamond with the 25 one-sided tetrasticks, which was solved by Alfred Wasserman. Here’s one I’ve come up with:

Problem #15: Tile the above shape with two sets of the five tetrominos and one monomino, and tile the borders of these polyominoes with the 16 tetrasticks. Here’s an attempt I made that fell short by a few tetrasticks, but it should give you an idea of the form a solution would take:

The observation that the lines formed by the pieces in a polyomino tiling could themselves be tiled by polysticks seems obvious, but I have not seen it elsewhere. After picking the 16 tetrasticks as my puzzle pieces for the polystick stage, I had to find a set of polyominoes to use. Since one of the tetrasticks is, in fact, the outline of a 1×1 square, or monomino, the monomino had to be present. A double set of tetrominoes plus the monomino gives a good quantity of segments for our tetrasticks to cover, and gives us an area of 2 * (5*4) + 1 = 41. The perimeter of the figure to be tiled is constrained by the following formula:

2 * total segments in the polystick set – sum of perimeters of polyominoes = perimeter of entire figure

In this case, (2 * (4 * 16)) – (4 + 2 * 48) = 28

So I needed a figure to tile with area 41 and perimeter 28, and came up with the shape above.

There are 136 solutions for the tetromino tiling with the monomino in the center as shown. (See these solutions in a Java solver applet.) I’ve experimented a little with the tetrastick stage of the problem by hand, and I’m convinced that there are no tetrastick solutions for most, if not all, of these tetromino solutions. But if it doesn’t work out in the case with the monomino in the center, I suspect there are enough solutions with the monomino elsewhere for it to be very likely that one will work. Many of the tetromino solutions fail to contain a site where the “+” tetrastick can be placed that doesn’t overlap the “□”.

Another issue that surfaces in this problem is horizontal-vertical segment parity. Eleven of the tetrasticks have even parity, that is, however you place them, they will always contain even numbers of both horizontal and vertical segments. Five of them have odd parity, and will always contain three segments of one orientation and one of the other. Because there are an odd number of pieces of odd parity, the parity of the set of tetrasticks as a whole must be odd. This means, without even starting to try placing tetrasticks on a tetromino solution, we can rule out the possibility of tiling it just by counting the number of horizontal or vertical segments. (Because the total is constant, we don’t need to count both.) If that number is even, the tetrasticks can’t tile the figure. The tetromino solution that I used in my attempt above has the correct (odd) parity.

I dredged this problem up from my archive of the polyforms mailing list, where I posted it in February, 2001. It got no takers then, but I thought it an interesting enough problem to deserve a second airing. I looked for other problems of this type in preparing this post, but I didn’t find anything good. Having both the area and the perimeter of the figure to be tiled constrained by the pieces used limits the possibilities a lot.

Gordon Hamilton’s Polyanimal Zoo

April 6th, 2010

Here’s a problem that I heard from Gordon Hamilton at Gathering for Gardner 9, and tracked down to an article of his in issue #10 of Pi in the Sky, a western Canadian math magazine for high school students and teachers.

A polyomino animal can eat another polyomino animal (his perhaps overly cute term is “polyanimal”) if the second one can be placed inside the first. Find animals of sizes 4, 5, 6, 7, 8, 9, and 10 that can live together peacefully (none can eat any of the others) within a 7×7 square pen.

This is really a satisfying puzzle to solve. Usually in polyform tiling puzzles, you spend a fair amount of time feeling out the territory, learning which pieces like to go in certain places, and which you want to deal with first and which you want to save for the end. But then, the larger part of the solving time is spent in trial and error with various configurations attempted at random until at last you run into a solution.

Here, the whole solving process is learning about the territory of the puzzle, and none of it feels like random crunching. I highly recommend giving it a try, but if you just want to see a solution, mine is here.

Of course, the matter of polyominoes fitting inside other polyominoes is an area that I’ve dealt with in my Polyomino Cover material, which I summarized in my presentation for G4G9. And one of the problems in Hamilton’s Polyanimal problem set is the same as what I’ve called the minimal pentomino cover problem. But most of them are completely different, which only reinforces my belief that this is an area with a lot more waiting to be discovered. (His last problem is “Design a Polyanimal Game.” Now that’s open-ended and provocative!)

Pentomino Cover Cycles

March 17th, 2010

What’s the smallest shape into which any of the 12 pentominoes can be placed? I call this old chestnut the “minimal pentomino cover” problem, and I’ve spent a lot of time working on a number of variations on it. For the purpose of introducing and illustrating the basic problem to my dear readers, I wanted to use an animated GIF file showing all of the pentominoes in turn being placed on a minimal cover.

An aesthetically pleasing way to cycle through the pentominoes would be to move one square at a time. This is in fact possible:

A couple of variations on the problem of finding such a cycle suggest themselves:

#9: Minimize the total distance the squares move per cycle. The taxicab metric seems to be more sensible and simpler than Euclidean distances here. I made no attempt to do any minimization in the above solution, so I’m sure there is room for improvement.

#10: If you gave every square in the pentominoes a distinct color, and kept the color the same when a square moved, you could keep track of where the squares end up at the end of a cycle. During the cycle illustrated above, two pairs of squares switch places. Is there a cycle of single-square moves through the pentominoes that ends with each square in the same place it began?

Notice that the central square can never move, because the only pentomino placement without the central square is one of the P pentomino, for which the only valid square movements turn it into a U pentomino. It would need movements to two different pentominoes to be part of a cycle.

For both of the above problems, the other 9 square pentomino cover would also be a valid substrate:

Since this one has no immobile squares, another problem using it may be solvable:

#11: Find a cycle where the permutation of the squares from one cycle to the next is cyclic (in the second sense in the linked article.) That is, successive iterations of the cycle will eventually take each square in a pentomino to all of the other positions in that pentomino.


Some very good news: I’ve been invited to the 9th Gathering for Gardner conference in Atlanta later this month. The Gathering for Gardner is an invitation-only conference  held in honor of Martin Gardner, who brought recreational mathematics to a generation through his columns in Scientific American. That generation was not my generation, but it was impossible to miss his imprint on later writers, and I’ve picked up used copies of several of the collections of his columns. A large proportion of the names on the spines on my recreational mathematics bookshelf are represented among the invitees, so this will be really special for me.