Pentomino tilings: twelve shapes and an exact-cover search
Pentomino tilings begin with twelve shapes, each made from five equal squares joined along their edges. Turning or reflecting a shape does not create another member of this twelve-piece collection. The pieces can form rectangles or fill other prescribed regions without overlap. Solomon Golomb coined the broader name polyomino in a 1953 lecture to the Harvard Mathematical Club. Donald Knuth later used pentomino arrangements to demonstrate an exact-cover search in Dancing Links. [1, 2, 3]
A domino contains two squares; a pentomino contains five. The prefix identifies the number of constituent squares rather than a particular outline. Squares meet along full edges, so a connection through a corner alone does not join a polyomino. Changing the number of squares changes the available collection of shapes. The geometrical task can then specify the pieces, the target region and which rotations or reflections are permitted. [1]
The twelve free pentominoes have names resembling their outlines: F, I, L, N, P, T, U, V, W, X, Y and Z. A different counting convention produces eighteen one-sided pentominoes, where turning a piece over is restricted. Holding orientation fixed produces 63 fixed pentominoes. These totals count the component shapes under different equivalences. They do not count the arrangements of a complete set inside a rectangle. [2]
Golomb’s lecture did not mark the first appearance of a five-square dissection. Henry Ernest Dudeney had published a pentomino problem in The Canterbury Puzzles in 1907. Golomb’s work appeared in the American Mathematical Monthly in 1954. Martin Gardner’s Scientific American discussion in May 1957 helped expand interest, and Golomb’s Polyominoes followed as a book in 1965. The subject developed through recreational designs, mathematical exposition and correspondence about new constructions. [1, 4]
In the preface to his first edition, Golomb recalled learning about earlier pentomino work after his lecture. He described a stream of correspondents who asked for information, offered arrangements and proposed further problems. The 1994 revision followed almost three decades after the first edition. Its contents extended from checkerboards and impossible constructions to larger polyominoes, higher dimensions and tilings of rectangles. A named family of small pieces had become a much broader geometrical subject. [4]
Knuth’s packing example uses a chessboard with its central two-by-two square removed. Sixty cells remain for the twelve pieces. The arrangement can be translated into a matrix with 72 columns: sixty identify board cells and twelve identify individual pentominoes. Each possible placement supplies one matrix row. That row marks its piece column and the five cells it occupies. Selecting a collection of rows must cover every column exactly once. [3]
This exact-cover condition combines two requirements. Each piece must appear once, and each cell must be covered once. A collection that repeats a piece fails even if its occupied cells are distinct. A collection that overlaps on a cell fails even if every selected piece has a different name. In Knuth’s formulation, pieces and board cells receive the same mathematical treatment: both are columns that need a single covering row. [3]
The search branches by selecting one uncovered column and trying its possible rows. Choosing a placement removes incompatible placements from further consideration. If the choice leads to a dead end, backtracking restores the removed options before exploring another branch. Dancing Links uses a linked representation whose removals can be reversed. The method organizes a systematic search while avoiding a fresh copy of the complete arrangement data at every stage. [3]
Symmetry reduces repeated work in pentomino tilings. In the central-hole chessboard example, Knuth restricts the X piece to selected locations and uses a further orientation restriction in one case. A six-by-ten rectangle has 2,339 essentially different arrangements of all twelve pentominoes. His study compares the work involved in that rectangle with the central-hole board and with earlier specialized packing programs. Different target regions create different search trees even though the inventory of pieces stays fixed. [3]
For pentomino tilings of the central-hole chessboard, Knuth divides a symmetry-reduced enumeration into three cases according to the X piece. With that piece at position 23 there are nineteen arrangements, at 24 there are twenty, and at 33 there are 26 with an additional restriction that P is not flipped. The coordinates identify rank and file. These subdivisions organize one board’s arrangements; they are separate from the 2,339 essentially different arrangements of the six-by-ten rectangle. [3]
Coloring supplies a contrasting way to rule out some tilings without listing arrangements. Every domino on a checkered board covers one black and one white cell. Removing two white corner cells leaves unequal color counts, so the remaining board cannot be covered entirely by dominoes. An area divisible by the piece size is therefore insufficient on its own. Pentomino tilings similarly depend on the actual shapes and available placements, beyond the total area of their squares. [1, 3]
[1] ETH Zurich Library, Polyominoes: history, definitions and coloring. https://library.ethz.ch/en/collections-and-archives/platforms/virtual-exhibitions/Its-all-math-and-games/polyominoes.html
[2] Eric Weisstein, Wolfram MathWorld: Pentomino. https://mathworld.wolfram.com/Pentomino.html
[3] Donald Knuth, Dancing Links (2000), primary research. https://arxiv.org/html/cs/0011047v1
[4] Solomon Golomb, Polyominoes, Princeton University Press, second-edition preview. https://api.pageplace.de/preview/DT0400.9780691215051_A39698920/preview-9780691215051_A39698920.pdf
- ETH Zurich Library, Polyominoes: history, definitions and coloring — library.ethz.ch