The first tiling problem using the 12 pentominoes was designed by Henry Dudeney and published in 1907, and in the years since much has been done to expand the realm of polyform puzzles, by finding new shapes to tile and new shapes of pieces to tile them with, by using larger and larger pieces and sets of pieces, by defining sets of pieces using criteria other than their sizes, by exploring higher dimensions, et cetera. This is all great, but to me many of these problems miss the aesthetic ideal approached by the simple problem of tiling a rectangle with the 12 pentominoes. I've found a few variations on this problem all using one additional element: color.
All of these problems involve colorings of the set, that is, choosing colors for pieces so that no two pieces that border each other are the same color. A famous theorem states that it is always possible to color a set of regions on the plane using only 4 colors. In polyomino tiling problems it is frequently possible to find 3-colorings, and basically never possible to find 2-colorings unless you use very contrived sets of polyominoes or shapes to tile. Mathematicians generally consider regions that meet only at a single point to not border each other, (simply because this is required to make the 4 color theorem and a lot of other stuff work,) but there is no reason why we have to follow this. We'll call the coloring scheme that considers two pieces to border each other even if they meet only at a point strict, and the scheme that only considers them to border each other if they share an edge non-strict.
A few years ago I bought myself an Icehouse set, which consisted of 60 pyramidal pieces, 5 each of every combination of four colors and three sizes. (An extraordinary number of worthwhile games can be played with these pieces, so allow me to recommend buying them from your local game store or directly from the manufacturer, LooneyLabs.)
Of course it occurred to me that this set would be great for pentomino explorations, since the pieces of each type could be placed on the squares of a grid to form different pentominoes. And the set naturally lends itself to coloring problems too; 4-colorings can be made by keeping the pentominoes with the same color of pieces from touching, and 3-"colorings" can be made by keeping those with pieces of the same size apart.
Is it possible to do both at once? I called this combination of 3- and 4-colorings, where each pair of colors from the two different colorings is present, an Icehouse coloring. Günter Stertenbrink found 142 solutions for the 6x10 rectangle, but only one strict coloring:
For the 8x8 rectangle with corners removed he again found 142 solutions, 15 of which are strict colorings. Elliott Evans set up giant spray-painted cardboard icehouse pieces on a giant chessboard, illustrating one of these solutions:
Some open problems:
There are also 12 hexiamonds, (pieces composed of 6 equilateral triangles,) which can tile numerous shapes. Do any of these shapes have tilings with Icehouse colorings?
It's possible to generalize the notion of an Icehouse coloring to any set of simultaneous colorings with the property that each color combination occurs exactly once. We'll use the notation "(n1, n2, ... ni)-Icehouse coloring" to denote the number of colors in each coloring of a set with n1*n2* ... *ni pieces.
So, the first step is to find sets whose members' numbers have felicitous factors. There are 20 rhombic pentominoes. (4, 5)-Icehouse colorings shouldn't be too hard to find. I wonder what proportion of 4-colorings can be used in one.
There are 60 one-sided hexominoes. Can a (3, 4, 5)-Icehouse coloring be found for a rectangle tiled by these pieces?
Suppose you have a coloring of a polyomino tiling with no "crossroads", that is, no point where four pieces meet. How many different ways can the space around the points where three pieces meet be colored? Of course, it depends on how many colors you use, but if there are four colors, and reflections and rotations of the combinations are considered equivalent, there are 12. I noticed that 12 seemed to be a reasonable number of "3-roads" to occur in a tiling of a 6x10 rectangle with the pentominoes, and I asked on the polyforms mailing list whether it was possible to find a coloring of such a tiling for which each of the 12 combinations occurred once.
Surprisingly, Patrick Hamlyn found that even though there are no such colorings on the 6x10 rectangle, there is exactly one on the 5x12 rectangle:
Elegant problems with unique solutions are rare in polyform tilings. If the problem is just a little too hard, it will have no solutions at all, if it is too easy, it will have multiple solutions, and if one tweaks a problem specifically in order to give it a unique solution, this takes something away from its elegance, (which I admit is a subjective quality.)
So I think it's a pretty cool bit of luck that only months after the solution to the Icehouse coloring problem was found, I happened upon a second problem with a unique solution. Of course, the best bit of luck was finding a mailing list with people willing to modify their programs to solve these problems.
Update: (January 2003) Aad van de Wetering has found some new solutions for this problem tiling different shapes. The page is in Dutch, but the diagrams speak for themselves.
Remember when I said that you can't generally find 2-colorings of polyomino tilings? While this is certainly the case for both the strict and non-strict adjacency schemes, I thought it might be possible to make a scheme loose enough for 2-colorings to become possible. I defined a loose coloring scheme as one in which two pieces of the same color are allowed to border each other with a border of at most one unit-length, and asked if loose 2-colorings of pentomino tilings of rectangles were possible. Again, Patrick Hamlyn took up the challenge. He found that there were 18 loose 2-colored tilings on a 6x10 rectangle, 6 on the 5x12, and 2 on the 4x15. Here is one of the 6x10 solutions:
This is the only solution on the 6x10 rectangle with no crossroads. (One of the 4x15 solutions also has this property.)
Unlike the first two problems, this one generalizes pretty well to any set of polyforms composed of cells with edges of uniform length. So go knock yourself out finding loose 2-colorings.
I wondered if the one-sided pentominoes could tile a rectangle so that they had a 3-coloring with the following properties:
Patrick Hamlyn found that the answer was that they couldn't. He did however find that such a coloring was possible on a tiling of this shape:
Since I collect pentomino coloring problems, 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. For a long time, only images of the 'zine's covers were available on the web, but now Kurchan has placed 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 type of puzzle made possible with packing is finding a 2-coloring of a set of polyominoes. 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 Puzzle Fun's problem statement implied strict coloring. I was also interested in non-strict coloring, and I was interested in colorings of a single set of pentominoes. My best attempt for a non-strict 2-colored packing of of a rectangle with one set of pentominos has 65 squares:
Filling out the variations, two more puzzles would be to pack, in a rectangle of minimal size, the following:
Bryce Herdt pointed out that adjoining my solution to the second problem with a flipped and color-inverted copy of itself would produce a solution to the latter problem.
[This section is based on a blog post. Feel free to contribute your comments there.]
I hope that I have shown that the hundred year old problem of tiling pentominoes still has some life in it, and I believe that there is still much more to be discovered. If you're interested in learning more about polyominoes and other polyforms, Andrew Clarke's Poly Pages site is a good place to start, and the polyomino page on David Eppstein's Geometry Junkyard is a good place to find random juicy info nuggets.
If you have questions, comments, solutions to unsolved problems, or ideas for new, related problems, please email me.