Posts Tagged ‘pentominoes’

Pentominoes on paths and trees

February 3rd, 2017

Here’s a path that could be taken by a chess king. All subpaths of length four describe a different pentomino:

A pentomino train

This led from the grid of pentomino painting instructions that I posted previously. Consider a string of arrows for which the subsequences of length 4 include instructions for producing all 12 pentominoes. (This is somewhat analogous to a de Bruijn sequence.) For the case shown, the string is ←↑↖→→→→↓↓←↓←↘↗↓, although the graphic seems more illuminating than the arrow string here.

Instead of a path, we could have a tree of pentominoes:

Along with the constraints that each pentomino occurs exactly once, and no square is used more than once, I wanted to limit the number of branches per node. The root node having three branches might be considered a flaw, but this was the best I could do.

Pentomino Painting Robots

February 1st, 2017

In the diagram below, each row (reading from left to right) and column (reading from top to bottom) gives instructions for painting one of the 12 pentominoes:

Sometimes an idea languishes in one of my notebooks for a few years before I can come up with the right iteration of it. My original idea here was to use a 4×4 grid. That would give me 8 pentominoes, (perhaps 10 using diagonals) but elegance surely requires all 12 to be present.

A combination of circumstances led me back to this problem. Some friends of mine have a tradition of playing RoboRally on New Year’s Day every year. This is a board game where you use cards with arrows on them to instruct your robot to move around a grid of squares. Also, in returning to the magic 45-omino problem, I was considering grids that could be used in sparse magic squares.

It might be possible to make an interesting grid puzzle, along the lines of sudoku, using this kind of grid as a basis. Most of the grid would start empty, except for a few squares in which arrows would be given at the start. Then the solver would fill in the rest of the grid by logical deduction so that the horizontal and vertical lines contain instructions for paining all of the pentominoes as above. Since the grid would have significantly fewer squares than a sudoku, this puzzle might be quicker to solve, but that doesn’t mean that it would necessarily be less interesting.

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.

The Happiest and Saddest Tilings

June 15th, 2016

(Tagging under “A Polyformist’s Toolkit”, as I feel that series ought to have an entry on coloring, and this more or less says what I have to say about that.)

At Gathering for Gardner 11 in 2014, I gave a talk about crossed stick puzzles. It was the obvious thing to talk about, since I had been making a lot of interesting discoveries in that area. Unfortunately there was too much good stuff, and I couldn’t bear to trim very much of it out, so I made the classic mistake of going over on time and having to rush the last slides. (G4G talks are generally limited to 6 minutes.) When I looking for a subject for this year’s talk, there was nothing I felt an urgent desire to talk about. This would be the 12th Gathering for Gardner, and there is a tradition that using the number of the current Gathering, either in your talk or your exchange gift, is worth a few style points. Since I’m a polyformist, and Gardner famously popularized the twelve pentominoes, revisiting some of my pentomino coloring material seemed reasonable.

Finding interesting map colorings is a nice puzzle that we can layer on top of a tiling problem. A famous theorem states that all planar maps can be colored with four colors so no two regions of the same color touch. Since this can always be done, and fairly easily for small maps like pentomino tilings, we’ll want some properties of colorings that are more of a challenge to find. I know of three good ones:

  1. Three-colorability. Sometimes we only need three colors rather than four. For sufficiently contrived sets of tiles we might only need two, but for typical problems that won’t work.
  2. Strict coloring. For most purposes, (like the Four Color Theorem) we allow regions of the same color to touch at a vertex. If we do not allow same colored regions to touch at a vertex, we call the legal colorings strict. Notice that a 3-coloring of polyominoes is strict if and only if it contains no “crossroads”, i.e. corners where four pieces meet.
  3. Color balance. If the number of regions of each color is equal, a coloring may be considered balanced. Conveniently, 3 and 4 are both divisors of 12, so we can have balanced 3-colorings and 4-colorings of pentomino tilings.

The above information would make up the introduction to my talk. It would also, suitably unpacked and with examples, take up most of the alloted time. That left little enough room to show off nifty discoveries. So whatever nifty discoveries I did show would serve the talk best if they could illustrate the above concepts without adding too many new ones. One that stood out was this simultaneous 3- and 4-coloring with a complete set of color combinations, discovered by Günter Stertenbrink in 2001 in response to a query I made on the Polyforms list:


This is the unique pentomino tiling of a 6×10 rectangle with this property where the colorings are strict. I used it to illustrate 3- vs. 4-coloring by showing the component colorings first, before showing how they combine. To my astonishment, the audience at G4G12 applauded the slide with the combined colorings. I mean I think it’s pretty cool, but I consider it rather old material.

I still wanted one more nifty thing to show off, and while my page on pentomino colorings had several more nifty things, none of them hewed close to the introductory material, and the clever problem involving overlapping colored tilings that I was looking at didn’t seem very promising. Setting that aside, I wrote some code to get counts of the tilings of the 6×10 rectangle with various types of colorings. That gave me the following table:

  Total Balanced
4-colorable, non-strict 2339 2338
4-colorable, strict 2339 2320
3-colorable, non-strict 1022 697
3-colorable, strict 94 53

What stood out to me was the 2338 tilings with balanced colorings. Since there are 2339 tilings in total, that meant that there was exactly one tiling with no balanced coloring:


Notice that the F pentomino on the left borders eight of the other pentominoes, and the remaining three border each other, so there can be at most two pentominoes with the color chosen for the F, and no balanced coloring can exist. A unique saddest tiling balancing out the unique happiest tiling was exactly what my talk needed. Now it had symmetry, and a cohesive shape. Having important examples all using the 6×10 rectangle removed the extraneous consideration of what different tiling problems were out there, and helped to narrow the focus to just the coloring problem. Anyway, I don’t want to go on any more about how awesome of a talk it was, (especially because video of it may eventually go up on the internet, which would show how non-awesome my delivery was) but it was my first G4G talk that I was actually proud of. The slides for the talk are here.

One thing I’m curious about that I didn’t mention in the talk: has anyone else found the saddest tiling before me? Looking through old Polyform list emails, I found that Mr. Stertenbrink enumerated the 3-colorable tilings of various types (essentially, the bottom half of the table above) but not the 4-colorable tilings. From the perspective of looking for the “best” colorings, it makes sense to focus on the 3-colorable tilings, but it meant missing an interesting “worst” coloring.

Some Contributed Solutions

October 2nd, 2013

I’ve had a few solutions sent in recently, so I wanted to share them with you all.

First, Abaroth noticed that my rhombic-cell pentomino tiling had just enough space to fill out into a five pointed star if the tetrominoes were also included:


But that was just the beginning! He then proceeded to produce an entire collection of tilings with these pieces, which he calls flexominoes. One problem that can come up in tilings of this sort is that if there is a vertex with three rhombi around it, a polyomino containing all three rhombi has an ambiguous identity, since there is more than one way to “unglue” the polyomino at that point. I contributed an ambiguity-free solution to one of the patterns Abaroth found:


Speaking of rhombuses, Abaroth has been investigating color-matching puzzles using rhombic tiles. His puzzle page has more interesting material on color matching puzzles and symmetrical polyhex tilings.

Next up, George Sicherman sent in a symmetrical tiling for the flexible tetrarhombs:


What’s interesting here is that although the outline of the tiling is symmetrical, the pattern of the cells isn’t. The lesson here is that being able to trade off some cell-level symmetry for more pattern-outline symmetry can give us a little variety in our choices of what we can tile.

Finally, Bryce Herdt provided a de Bruijn sequence of invertible length 5 binary words. (That is, a cyclic sequence where each word occurs once as a substring.) Since he did so in text format, I made a visualization:


Flexible polyrhombs

September 11th, 2013

From time to time, a pentomino tiling still manages to surprise me.

pentomino tiling with 5-fold dihedral symmetry

Normally, the largest number of symmetries you can make a pentomino tiling have is eight, the number of symmetries of the square. For example, we can tile an 8×8 square with the corner cells removed. (If we leave the plane for other topologies like cylinders and tori we can get more.) However, it’s a basic principle of flexible polyform tilings that we can generally try to squeeze one more repeated unit around the center of a rotationally symmetric tiling. So I did.

But my starting point for this was not the pentominoes. In my Hinged Polyform post, I discussed polyforms where the connections between pieces could occur at arbitrary angles. Conversely, we could look at polyforms where the shapes of the individual cells could contain arbitrary angles. If we assume that all of the edges are the same length, there is only one possible triangle, so polyiamonds in this scheme aren’t interesting. Rhombuses are the simplest example of cells where the angles can vary. Since they have only one degree of freedom per cell, they are reasonably tractable. The flexible tetrarhombs include flexible versions of the five tetrominoes in addition to the three shapes in blue below:


The flexible pentarhombs include the flexible pentominoes, the 18 forms that can be derived by adding a single red cell to one of the blue forms above, and the six additional forms in green. (I may well have missed some.)

It may be possible to find a good flexible tetrarhomb tiling, but I haven’t yet managed it. And 36 pentarhombs is too many for me to handle. If only there were some subset with a better number of pieces for a puzzle, something like the 12 pentominoes.

Oh. Right. (And that was more or less the thought process that led to the tiling above.)

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

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.

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.

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

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.

Pentomino Layer Cake

February 27th, 2010

On the Polyforms list, Erich Friedman posed a very interesting new pentomino tiling problem:

Tile a rectangle of minimal area with pentominoes so that for each pentomino there is exactly one stratum, or cluster of one or more copies of that pentomino that reaches from one side of the rectangle to the opposite side. Pentominoes in a stratum must form a single group, connected by edges, not just corners.

Michael Reid found this 3×30 solution:

It’s not hard to prove that it is minimal. A natural extension of the problem is to find minimal solutions for 4×n and 5×n rectangles. Michael Reid found the first 5×n solution, but I improved on it with this 5×32 solution:

The 4×n problem seems to be the hardest, and initially it was not clear that it would be possible. The X pentomino has only one possible stratum, which only can only be bordered by Y, I or N, and it is also difficult to find matches for a Z stratum. Additionally, only Y, L, and P can form straight line stratum boundaries usable for the top and bottom of the rectangle. (See wikipedia’s pentomino page if you don’t know the correspondence between letters and shapes.) I did eventually find this 4×50 solution:

This solution seems rather prolifigate with its pentominoes, but finding any solution at all was a bit of a surprise.

Update: Erich Friedman’s Math Magic for April 2010 further explored this subject.

2-coloring Pentomino Packings

January 24th, 2010

I like to collect pentomino coloring problems.

So it should come as little surprise that I was intrigued by the cover of Puzzle Fun 16. Puzzle Fun was a ‘zine produced by Rodolfo Marcelo Kurchan in the ’90s covering a variety of polyomino problems. I missed out on subscribing to it myself, and the Puzzle Fun website languished for a decade after new issues stopped appearing.

A few months ago, Kurchan put the content of all of the back issues of Puzzle Fun online.

Puzzle Fun 16 focused on pentomino packing problems. Packing problems differ from tiling problems in that empty space is allowed, and the goal is to minimize the amount of empty space required. Packing, usefully, makes some kinds of problems possible to solve that would not be solvable as tiling problems.

One such puzzle type is packing polyforms that are 2-colorable, (that is, one can use two colors to color every piece such that no piece touches another of the same color.) This is the puzzle type I saw on the cover of Puzzle Fun 16.

The problem itself was this: Place two sets of pentominoes in the smallest possible rectangle such that no pentomino touches another in the same set. [PF problem #549]

A solution was printed in Puzzle Fun 18:

(Solution by Hector San Segundo.)

I should note that this problem implies strict coloring: pieces are not allowed to touch even at corners. I am more interested in non-strict coloring, which is generally the default in coloring problems, and I am interested in colorings of a single set of pentominoes. (Which all of the problems on my pentomino coloring page are.)

#1: Place a 2-colorable (non-strict coloring) set of pentominoes in the smallest possible rectangle. My best attempt has 65 squares:

Filling out the matrix of variations gives two more problems:

#2: As #1, but with a strict coloring.

#3: As in PF #549, but with a non-strict coloring.

(The following problem in PF 16 (#550) was a variation on #549 minimizing perimeter rather than area, but this is less interesting to me.)