Polyominoes: Puzzles, Patterns, Problems, and Packings

Last updated
Polyominoes: Puzzles, Patterns, Problems, and Packings
Polyominoes Puzzles Patterns Problems and Packings book cover.png
Revised and Expanded second edition (English)
AuthorSolomon Golomb
PublisherPrinceton University Press
Publication date
1965
ISBN 9780691024448

Polyominoes: Puzzles, Patterns, Problems, and Packings is a mathematics book on polyominoes, the shapes formed by connecting some number of unit squares edge-to-edge. It was written by Solomon Golomb, and is "universally regarded as a classic in recreational mathematics". [1] The Basic Library List Committee of the Mathematical Association of America has strongly recommended its inclusion in undergraduate mathematics libraries. [2]

Contents

Publication history

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]

Topics

The twelve pentominoes Pentominos 001.svg
The twelve pentominoes

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 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 rectangles must have a side whose length is a multiple of . [8]

Audience and reception

Reviewer Elizabeth Senger writes that the book has a wide audience of "mathematicians, teachers, students, and puzzle people", and is "well written and easy to read", accessible even to high school level mathematics students. [7] Similarly, Elaine Hale writes that it should be read by "all professional mathematicians, mathematics educators, and amateurs" interested in recreational mathematics. [9] Senger adds that the second edition is especially welcome because of the difficulty of finding a copy of the out-of-print first edition. [7]

Although the book concerns recreational mathematics, reviewer M. H. Greenblatt writes that its inclusion of exercises and problems makes it feel "much more like a text book", but not in a negative way. [4] Similarly, Alan Sutcliffe writes that "an almost ideal balance has been struck between educational and recreational", [3] and Pamela Liebeck calls its coverage of the topic "fascinating and thorough". [5]

Related Research Articles

<span class="mw-page-title-main">Pentomino</span> Geometric shape formed from five squares

Derived from the Greek word for '5', and "domino", a pentomino is a polyomino of order 5; that is, a polygon in the plane made of 5 equal-sized squares connected edge to edge. When rotations and reflections are not considered to be distinct shapes, there are 12 different free pentominoes. When reflections are considered distinct, there are 18 one-sided pentominoes. When rotations are also considered distinct, there are 63 fixed pentominoes.

<span class="mw-page-title-main">Tetromino</span> Four squares connected edge-to-edge

A tetromino is a geometric shape composed of four squares, connected orthogonally. Tetrominoes, like dominoes and pentominoes, are a particular type of polyomino. The corresponding polycube, called a tetracube, is a geometric shape composed of four cubes connected orthogonally.

<span class="mw-page-title-main">Polyomino</span> Geometric shapes formed from squares

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.

<span class="mw-page-title-main">Packing problems</span> Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must find a solution that satisfies the given conditions. Mathematical puzzles require mathematics to solve them. Logic puzzles are a common type of mathematical puzzle.

<span class="mw-page-title-main">Hexomino</span> Geometric shape formed from six squares

A hexomino is a polyomino of order 6; that is, a polygon in the plane made of 6 equal-sized squares connected edge to edge. The name of this type of figure is formed with the prefix hex(a)-. When rotations and reflections are not considered to be distinct shapes, there are 35 different free hexominoes. When reflections are considered distinct, there are 60 one-sided hexominoes. When rotations are also considered distinct, there are 216 fixed hexominoes.

<span class="mw-page-title-main">Polyabolo</span> Shape formed from isosceles right triangles

In recreational mathematics, a polyabolo is a shape formed by gluing isosceles right triangles edge-to-edge, making a polyform with the isosceles right triangle as the base form. Polyaboloes were introduced by Martin Gardner in his June 1967 "Mathematical Games column" in Scientific American.

<span class="mw-page-title-main">Polyhex (mathematics)</span> Polyform with a regular hexagon as the base form

In recreational mathematics, a polyhex is a polyform with a regular hexagon as the base form, constructed by joining together 1 or more hexagons. Specific forms are named by their number of hexagons: monohex, dihex, trihex, tetrahex, etc. They were named by David Klarner who investigated them.

<span class="mw-page-title-main">Polycube</span> Shape made from cubes joined together

A polycube is a solid figure formed by joining one or more equal cubes face to face. Polycubes are the three-dimensional analogues of the planar polyominoes. The Soma cube, the Bedlam cube, the Diabolical cube, the Slothouber–Graatsma puzzle, and the Conway puzzle are examples of packing problems based on polycubes.

<span class="mw-page-title-main">Tromino</span> Geometric shape formed from three squares

A tromino or triomino is a polyomino of size 3, that is, a polygon in the plane made of three equal-sized squares connected edge-to-edge.

<span class="mw-page-title-main">Solomon W. Golomb</span> American mathematician (1932–2016)

Solomon Wolf Golomb was an American mathematician, engineer, and professor of electrical engineering at the University of Southern California, best known for his works on mathematical games. Most notably, he invented Cheskers in 1948. He also fully described polyominoes in 1953. He specialized in problems of combinatorial analysis, number theory, coding theory, and communications. Pentomino boardgames, based on his work, would go on to inspire Tetris.

<span class="mw-page-title-main">Heptomino</span> Geometric shape formed from seven squares

A heptomino is a polyomino of order 7; that is, a polygon in the plane made of 7 equal-sized squares connected edge to edge. The name of this type of figure is formed with the prefix hept(a)-. When rotations and reflections are not considered to be distinct shapes, there are 108 different free heptominoes. When reflections are considered distinct, there are 196 one-sided heptominoes. When rotations are also considered distinct, there are 760 fixed heptominoes.

<span class="mw-page-title-main">Nonomino</span> Geometric shape formed from nine squares

A nonomino is a polyomino of order 9; that is, a polygon in the plane made of 9 equal-sized squares connected edge to edge. The name of this type of figure is formed with the prefix non(a)-. When rotations and reflections are not considered to be distinct shapes, there are 1,285 different free nonominoes. When reflections are considered distinct, there are 2,500 one-sided nonominoes. When rotations are also considered distinct, there are 9,910 fixed nonominoes.

<span class="mw-page-title-main">Octomino</span> Geometric shape formed from eight squares

An octomino is a polyomino of order 8; that is, a polygon in the plane made of 8 equal-sized squares connected edge to edge. When rotations and reflections are not considered to be distinct shapes, there are 369 different free octominoes. When reflections are considered distinct, there are 704 one-sided octominoes. When rotations are also considered distinct, there are 2,725 fixed octominoes.

<span class="mw-page-title-main">Mutilated chessboard problem</span> On domino tiling after removing two corners

The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks:

Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?

<span class="mw-page-title-main">Domino tiling</span> Geometric construct

In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.

In mathematics, a domino is a polyomino of order 2, that is, a polygon in the plane made of two equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there is only one free domino.

<span class="mw-page-title-main">Rep-tile</span> Shape subdivided into copies of itself

In the geometry of tessellations, a rep-tile or reptile is a shape that can be dissected into smaller copies of the same shape. The term was coined as a pun on animal reptiles by recreational mathematician Solomon W. Golomb and popularized by Martin Gardner in his "Mathematical Games" column in the May 1963 issue of Scientific American. In 2012 a generalization of rep-tiles called self-tiling tile sets was introduced by Lee Sallows in Mathematics Magazine.

A decomino, or 10-omino, is a polyomino of order 10; that is, a polygon in the plane made of 10 equal-sized squares connected edge to edge. When rotations and reflections are not considered to be distinct shapes, there are 4,655 different free decominoes. When reflections are considered distinct, there are 9,189 one-sided decominoes. When rotations are also considered distinct, there are 36,446 fixed decominoes.

David Anthony Klarner was an American mathematician, author, and educator. He is known for his work in combinatorial enumeration, polyominoes, and box-packing.

References

  1. 1 2 3 Martin, George E. (1995), "Review of Polyominoes (2nd ed.)", Mathematical Reviews, MR   1291821
  2. ↑ "Polyominoes", MAA Reviews, retrieved 2020-06-19
  3. 1 2 3 4 5 6 7 Sutcliffe, Alan (November 1965), "Review of Polyominoes (1st ed.)", Mathematics Magazine, 38 (5): 313–314, doi:10.2307/2687945, JSTOR   2687945
  4. 1 2 3 4 Greenblatt, M. H. (September 1965), "Review of Polyominoes (1st ed.)", American Scientist, 53 (3): 356A–357A, JSTOR   27836143
  5. 1 2 3 Liebeck, Pamela (October 1968), "Review of Polyominoes (1st ed.)", The Mathematical Gazette, 52 (381): 306, doi:10.2307/3614210, JSTOR   3614210
  6. ↑ Stefanescu, M., "Review of Polyominoes (Russian ed.)", zbMATH, Zbl   0326.05025
  7. 1 2 3 Senger, Elizabeth (January 1997), "Review of Polyominoes (2nd ed.)", The Mathematics Teacher, 90 (1): 72, JSTOR   27970078
  8. ↑ De Clerck, Frank, "Review of Polyominoes (2nd ed.)", zbMATH, Zbl   0831.05020
  9. ↑ Hale, Elaine M. (September 1995), The Mathematics Teacher, 88 (6): 524, JSTOR   27969460 {{citation}}: CS1 maint: untitled periodical (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.