Polyominoes: Puzzles, Patterns, Problems, and Packings

The book collects together material previously published by Golomb in various articles and columns, especially in Recreational Mathematics Magazine.^[3] It was originally published by Scribner's in 1965, titled simply Polyominoes, and including a plastic set of the twelve pentominoes. The book's title word "polyominoes" was invented for the subject by Golomb in 1954^[1] as a back-formation from "domino".^[4][5]

A translation into Russian by I. Yaglom, Полимино, was published by Mir in 1975; it includes also translations of two papers on polyominoes by Golomb and by David A. Klarner.^[6]

A second English-language edition of the book was published by the Princeton University Press in 1994. It added to the corrected text of the original addition two more chapters on recent developments, an expanded bibliography, and two appendices, one giving an enumeration of polyominoes and a second reprinting a report by Andy Liu of the solution to all open problems proposed in an appendix to the first edition.^[1]

After an introductory chapter that enumerates the polyominoes up to the hexominoes (made from six squares), the next two chapters of the book concern the pentominoes (made from five squares), the rectangular shapes that can be formed from them, and the subsets of an ${\displaystyle 8\times 8}$ chessboard into which the twelve pentominoes can be packed.^[3]

The fourth chapter discusses brute-force search methods for searching for polyomino tilings or proving their nonexistence, and the fifth introduces techniques from enumerative combinatorics including Burnside's lemma for counting polyominoes and their packings.^[3] Although reviewer M. H. Greenblatt considers this more theoretical material a digression from the main topic of the book,^[4] and the book itself suggests that less mathematically-inclined readers skip this material,^[7] Alan Sutcliffe calls it "the heart of the book", and an essential bridge between the earlier and later chapters.^[3] The question of using these methods to find a formula for the number of polyominoes with a given number of squares remains unsolved, and central to the topic.^[5]

The final two chapters of the first edition concern generalizations of polyominoes to polycubes and other polyforms,^[3][4] and briefly mention the work of Edward F. Moore and Hao Wang proving the undecidability of certain tiling problems including the problem of whether a set of polyominoes can tile the plane.^[3] The second edition adds a chapter on the work of David Klarner on the smallest rectangles that can be tiled by certain polyominoes, and another chapter summarizing other recent work on polyominoes and polyomino tiling, including the mutilated chessboard problem and De Bruijn's theorem that a rectangle tiled by smaller ${\displaystyle 1\times n}$ rectangles must have a side whose length is a multiple of ${\displaystyle n}$.^[8]