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.
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
| F | I | L | P | N | T | U | V | W | X | Y | Z |
Many puzzles involve fitting a set of pentominoes together so that they cover a certain shape, for example, a 6 unit by 10 unit rectangle. We will instead be examining covers of sets of pentominoes. A cover of a set of polyominoes is a set of cells in the plane (not necessarily contiguous) with the property that any of the members of the polyomino set can be placed within it.
It's not at all difficult to come up with a cover for a set of polyominoes. For the sake of having interesting puzzles to solve, we will be concerned with minimal covers. A minimal cover of a set is a cover that contains the smallest number of squares of any cover of that set. The problem of finding the minimal cover 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 minimal covers. 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, a minimal cover must contain at least nine squares. Since the covers shown contain exactly nine squares, they must be minimal.
Our definition of a cover requires that each polyomino in the set we are considering can be placed in at least one position within the cover. We might want to look for other qualities in the number of positions where each polyomino can be placed in a configuration of squares. Erich Friedman suggests this generalization: an n-cover is defined as one where each polyomino occurs at least n times.
A succinct cover is one where each polyomino can be placed in exactly one position. Most of the rest of this study is concerned with succinct covers. Note that it may not be possible to create a succinct cover of a set that is in one unbroken piece. When making a succinct cover of the pentominos, for example, 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. When there are multiple unconnected pieces in a cover, the position of those pieces relative to each other does not affect the character of the cover in any way, so we can consider covers as sets of polyomino pieces; the placement of each piece in our depictions is arbitrary.
Erich Friedman has suggested the term n-succinct cover for a cover 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 cover says everything it needs to say exactly once, and no more. If a 4-succinct cover 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 cover 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 a minimal succinct cover 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 minimal succinct cover 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 succinct covers that are smaller than those of the closed figures. In fact, as you can see to the right, a 12 cell cover 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 succinct covers 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 cover.
If we allow the cells within the cover to be colored, it is possible to count in the cover 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 cover is one where all of the polyominoes covered are present in such a form.
I like the minimal succinct panchromatic cover 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 minimal succinct covers first must find all of the polyforms that could be legal pieces in a succinct cover, 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 minimal succinct cover 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 minimal succinct cover to have pieces with high ratios. And in fact, the piece with the highest ratio for the hexominoes is part of a minimal succinct cover, as we can see below. A good greedy algorithm for finding a small cover 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 covers 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 minimal succinct cover 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 cover of tridominoes on mathpuzzle.com. There was a contest based on a cover of Chaos Tile combinations there, but it appears that nobody entered. My minimal succinct cover 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 cover can be said to be reducible if it is possible for a cell to be removed from it with the result still being a cover. A minimal cover is of course irreducible. How many cells does the largest contiguous irreducible cover 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 covers 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 minimal cover 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 cover. I've been able to make a cover with the latter rule with 25 cells.
I've written some code in Python for solving minimal succinct cover 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.