In analogy to dominoes, polyominoes are contiguous sets of cells in a square grid. Polyominoes with 5 cells are called pentominoes, and quite a bit of effort has been put into devising puzzles using them. If reflections and rotations of a given pentomino are considered the same, there are 12 distinct pentominoes, which are shown below with the letter commonly used to identify each.
Many puzzles involve fitting a set of pentominoes together so that they tile a certain shape, for example, a 6 unit by 10 unit rectangle. We will instead be examining common superforms of sets of pentominoes and other polyforms. A superform of a polyomino is a set of cells in the grid onto which the original polyomino can be placed so that all of it is contained within the superform. A common superform (CS) of a set of polyominoes is a set of cells that is a superform of each of the polyominoes in the set.
It's not at all difficult to come up with a common superform for a set of polyominoes. For the sake of having interesting puzzles to solve, we will be concerned with minimal common superforms (MCS). An MCS of a set is a CS that contains the smallest number of squares of any CS of that set. The problem of finding the MCS of the pentominoes was originally described by T. R. Dawson in Vol. 5, No. 4 of the Fairy Chess Review, published in 1942. (Thanks to G. P. Jelliss for helping me track down the origins of this problem. His Games and Puzzles Journal is an excellent recreational mathematics resource.)
The set of pentominoes has two 9-cell MCS's. To see that they are minimal, consider the I and W pentominoes. If they are overlapped, the combined shape must include eight squares. But no octomino formed in this way can contain the X pentomino. Therefore, an MCS must contain at least nine squares. Since the CS's shown contain exactly nine squares, they must be minimal.
Our definition of a CS requires that each polyomino in the set we are considering can be placed in at least one position within the CS. We might want to look for other qualities in the number of positions where each polyomino can be placed in a configuration. Erich Friedman suggests this generalization: an n-CS is defined as one where each polyomino occurs at least n times.
A succinct common superform (SCS) is one where each polyomino can be placed in exactly one position. Most of the rest of this essay is concerned with minimal succinct common superforms (MSCS). Note that it may not be possible to create a succinct common superform of a set that is in one unbroken piece. For example, when making an SCS of the pentominoes, the X pentomino, because of its symmetry, cannot have a cell added to it without the resulting hexomino containing two instances of the same pentomino, so it must appear as a separate piece. When there are multiple disconnected pieces in a CS, the position of those pieces relative to each other does not affect the character of the CS in any way, so we can consider CS's as sets of polyomino pieces; the placement of each piece in the diagrams here is arbitrary.
Erich Friedman has suggested the term n-succinct CS for a CS where each polyomino occurs exactly n times. I like this concept, but I'm less sure about the term; I chose "succinct" because metaphorically, a succinct CS says everything it needs to say exactly once, and no more. If a 4-succinct CS says things exactly 4 times, is it really being succinct? However, I can't think of a better term, and metaphors are made to be broken anyway.
Polyominoes that have fewer symmetries, or are more compact, tend generally to occur in higher frequencies in a pattern than the others. This is illustrated in the problem of finding a contiguous CS of the tetrominoes where the frequency of each tetromino's occurance is an unique integer between 1 and 5 inclusive. There are many different solutions, the one shown, which Erich Friedman found, is probably the smallest.
An interesting set of classes of polyominoes can be made by selecting the symmetries of the square grid under which shapes are considered equivalent. For example, the one-sided polyominoes are those for which reflected polyominoes are considered different but rotations are still considered the same.
Notice that an MSCS of the one-sided pentominoes is actually smaller than one of the set where reflections are equivalent. Despite the greater number of pentominoes, (18, versus 12 in the two-sided set) the narrower definition of each type of pentomino makes it easier to avoid making duplicates.
Rectangular and rhombic polyominoes have cells in the shape of rectangles and rhombi respectively. Sets of rhombic pentominoes made out of plastic are sold by Kadon under the name Rhombiominoes. Equivalently, we can use cells with markings with the same symmetries as rectangles and rhombi. Since this was easier to draw, I chose to do this for the solutions shown to the right. In this form, ignoring the markings, the pieces of this MSCS of the rhombic pentominoes are both symmetrical, which I found surprising and elegant.
When we are talking about polyominoes, what exacty are the points in the plane we are talking about? Implicit in the problems to this point is that we have been considering polyominoes as closed figures in the plane, that is, figures that include their perimeters as well as their interiors.
What if we consider only the perimeters of polyominoes? It might be possible to come up with SCS's that are smaller than those of the closed figures. In fact, as you can see to the right, a 12 cell SCS is possible. I found this by hand, and haven't proven that it's minimal, but I'm almost certain that it must be.
Conversely, we may consider polyominoes as open figures excluding their perimeters. Surprisingly, sets of these can also have SCS's smaller than those of "closed" polyominoes. The key is to notice that we can cut out line segments from the interiors of polyominoes we use as pieces of the CS.
If we allow the cells within a CS to be colored, it is possible to count in the CS only polyominoes that meet some requirement based on the colors of the cells within a given polyomino. One natural way to do this for a set of polyominoes of the same order n is to use n colors, and require that each polyomino occur in a form containing all n colors. A panchromatic CS is one where all of the polyominoes contained are present in such a form.
I like the minimal succinct panchromatic CS problem because of the balance that needs to be achieved in choosing the color of a cell so that it is different from enough nearby cells to make it usable for many polyominoes, while simultaneously making it the same color as other cells in order to avoid duplicates.
Erich Friedman contributed another problem using colored cells. The cells of a 4 by 5 rectangle can be filled with 2 colors such that each tetromino has the same number of placements with its cells all being the same color. One solution is shown to the right.
My program for finding MSCS's first must find all of the polyforms that could be legal pieces in a succinct CS, that is, polyforms with at most one placement for every polyform in the original set. These pieces are mathematically interesting in their own right.
We can look for pieces with distinctive characteristics, for example, the largest piece, and the piece within which the largest number of polyforms can be placed. (I call the latter prolific in analogy with my use of the term succinct. A prolific piece is one with a lot to say.)
Of interest for the MSCS problem is the ratio of number of polyforms in the set of interest that can be placed in the piece to the size of the piece. We would expect a MSCS to have pieces with high ratios. And in fact, the piece with the highest ratio for the hexominoes is part of an MSCS, as we can see below. A good greedy algorithm for finding a small CS would be to repeatedly take the piece with the best ratio among the pieces that only contain polyforms with no placements in the pieces we've already taken.
The area of polyomino CS's is still relatively unexplored, and plenty of new problems are waiting to be discovered. If you discover new problems of interest or better solutions to the problems I have discussed, please send them to me, and I will credit you on here.
All of the puzzles discussed in these pages can be adapted to larger polyominoes. My python program for solving MSCS problems is, unfortunately, very slow when handling relatively large polyomino sets. Even the heptominoes are currently out of the range of what it can solve on my computer.
Likewise, the principles used here can be extended to other polyforms. Ed Pegg has a page with a section about the minimal CS of tridominoes on mathpuzzle.com. There was a contest based on a CS of Chaos Tile combinations there, but it appears that nobody entered. My MSCS program is able to find solutions for polysticks, polyhexes and polyplets, a.k.a. polykings (polyominoes with cells that may be connected by corners instead of just edges.)
A CS can be said to be reducible if it is possible for a cell to be removed from it with the result still being a CS. A minimal CS is of course irreducible. How many cells does the largest contiguous irreducible CS of the pentominoes have? My best solution has 31. The coloring scheme I used shows the pentomino that would be lost if any of the cells within were removed. The lone cell is part of two T pentomino placements that would both be lost if the cell were removed.
Different coloring schemes than the one used for the panchromatic CS could be considered. For example, we could have 3 colors and require that they occur in a 2:2:1 ratio in each pentomino.
With 3 colors there are exactly 12 combinations for filling 5 cells with 2 of the 3 colors. Can you find a MCS for which each pentomino occurs with a unique combination? (Pentominoes with all 3, or only 1 color would not be counted.) There are two ways to interpret this probem. Either the same pentomino may occur more than once, if it contains the same combination of colors in each occurance, or it may occur only once in the entire CS. I've been able to make a CS with the latter rule with 25 cells.
I've written some code in Python for solving MSCS problems. You can download it here:
Python 2.4 or later is required to run it. This is open source / free software, and may be used under the terms of the MIT license below. Patches, either to improve performance or to add new functionality, are very much welcome.
Copyright © 2004-2006 Alexandre Muñiz
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
If you have questions, comments, solutions to unsolved problems, or ideas for new, related problems, please email me.