Polyomino Covers: an Introduction

The 12 Pentominoes:

F
I
L
N
P
T
U
V
W
X
Y
Z

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. The number of distinct pentominoes depends on how you count them. If reflections and rotations of a pentomino are considered the same, there are 12 distinct types, which are shown to the left with the letter commonly used to identify each.

A minimal cover of the tetrominoes:

Minimal covers of the pentominoes:

Many puzzles involve fitting a set of pentominoes together so that they cover a certain shape, for example, a 6 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. This problem is described in Solomon Golomb's book, Polyominoes, which shows both of the minimal covers of the pentominoes.

To see that they are minimal, consider the I and W pentominoes. If they are overlapped, the combined shape must include 8 squares. But no octomino formed in this way can contain the X pentomino. Therefore, a minimal cover must contain at least 9 squares.

Next: Succinct Covers