.. -*- coding: utf-8 -*- ================================ An Introduction to Polyominoes ================================ :Author: David Goodger :Date: $Date: 2015-02-24 14:21:02 -0600 (Tue, 24 Feb 2015) $ :Revision: $Revision: 600 $ :Web site: http://puzzler.sourceforge.net/ :Copyright: |c| 1998-2015 by David J. Goodger :License: `GPL 2 <../COPYING.html>`__ .. image:: images/puzzler.png :align: center .. sidebar:: Also see: * `Polyominoes: Puzzles & Solutions `_ * `Pentominoes: Puzzles & Solutions `_ * `Hexominoes: Puzzles & Solutions `_ * `Solid Pentominoes: Puzzles & Solutions `_ * `Notes on Polyominoes `_ * `Polyform Puzzler: Puzzles & Solutions `_ * `Polyform Puzzler FAQ `_ (`polyform details `__, `numbers of polyforms `__, `interpreting solution files `__) .. contents:: **Polyominoes** are polyforms constructed from unit squares joined edge-to-edge on a regular two-dimensional Cartesian plane. The name comes from dominoes; one domino is composed of two ("d-", short for "di-") unit squares ("-omino"). Here is a puzzle containing all the polyominoes of order 1 through 5: .. image:: images/ominoes/polyominoes-12345-cross-1.png See `Polyominoes: Puzzles & Solutions`_, `Pentominoes: Puzzles & Solutions`_, and `Hexominoes: Puzzles & Solutions`_ for many more puzzles. Polyominoes were named and studied by Solomon Golomb and popularized by Martin Gardner in `Scientific American` magazine in the 1950s. Pentominoes may have been first featured in a puzzle in 1907 (Dudeney's `The Canterbury Puzzles`), although the history of polyforms may go back much further. The tetrominoes are well known from the video game "Tetris". `Kadon Enterprises`__, vendors of quality polyform puzzles in wood and acrylic, have `an excellent introduction to polyominoes on their site`__. __ http://www.gamepuzzles.com __ http://www.gamepuzzles.com/polyintr.htm When the polyominoes are formed from unit cubes intead of flat squares, they are called "solid polyominoes" or "planar polycubes". See `An Introduction to Polycubes `_ for background, and `Polyominoes: Puzzles & Solutions`_ for many puzzles. Polyforms ========= The number and names of the various orders of polyominoes are as follows: ===== =========== ============= ============= Order | Polyform | Free | One-Sided | Name | Polyominoes | Polyominoes ===== =========== ============= ============= 1 monomino 1 1 2 domino 1 1 3 trominoes 2 2 4 tetrominoes 5 7 5 pentominoes 12 18 6 hexominoes 35 60 ===== =========== ============= ============= The numbers of polyominoes can also be found in the following sequences from `The On-Line Encyclopedia of Integer Sequences `_: A000105_ (free) and A000988_ (one-sided). .. _A000105: http://oeis.org/A000105 .. _A000988: http://oeis.org/A000988 Examples of the polyominoes from order 1 (monomino) to order 6 (hexominoes) are given in the tables below. The polyominoes are named with letters (like the pentomino "X") or a letter-number scheme (like the "I3" tromino or the "X06" hexomino). The traditional names for the pentominoes are used by Polyform Puzzler, without a number suffix. The names of the hexominoes_ below roughly correspond to the Kadon `naming system for hexominoes`__. The rest of the polyomino names correspond loosely to Kadon's names for their `Poly-4 Supplement`_ set (exceptions noted in the tables below). __ http://www.gamepuzzles.com/sxnames.htm The initial letter of each name is the letter of the alphabet that the polyomino most closely resembles, or an initial. In some cases, that resemblance is weak, and the letters are arbitrary. The final digit of the number represents the polyform order (how many unit squares are in the polyomino). For the hexominoes, some letters are used for multiple pieces (there are more pieces than letters in the alphabet), so a middle index digit is used to differentiate (e.g. "X06" and "X16"). .. _table legend: In the tables below, "Aspects" refers to the number of unique orientations that a polyform may take (different rotations, flipped or not). This varies with the symmetry of the polyform. The "One-Sided" column identifies polyforms that are asymmetrical in reflection. Treating the flipped and unflipped versions of asymmetrical polyominoes as distinct polyforms (and disallowing further reflection or "flipping"), results in "one-sided" polyominoes and puzzles. Alternate names and name origins are noted in the "Name" column. Monomino -------- There is only one monomino (order-1 polyomino): .. list-table:: :widths: 20 20 20 20 :header-rows: 1 * - Name - Image - Aspects - One-Sided * - | O1 | ("M", from "Monomino") - .. image:: images/pieces/polyominoes/O1.png - 1 - Domino ------ There is only one domino (order-2 polyomino): .. list-table:: :widths: 20 20 20 20 :header-rows: 1 * - Name - Image - Aspects - One-Sided * - | I2 | ("D", from "Domino") - .. image:: images/pieces/polyominoes/I2.png - 2 - Tromino ------- Sometimes called "triominoes", there are 2 trominoes (order-3 polyominoes): .. list-table:: :widths: 20 20 20 20 :header-rows: 1 * - Name - Image - Aspects - One-Sided * - I3 - .. image:: images/pieces/polyominoes/I3.png - 2 - * - V3 - .. image:: images/pieces/polyominoes/V3.png - 4 - Tetromino --------- There are 5 free tetrominoes (order-4 polyominoes) and 7 one-sided tetrominoes: .. list-table:: :widths: 20 20 20 20 :header-rows: 1 * - Name - Image - Aspects - One-Sided * - I4 - .. image:: images/pieces/polyominoes/I4.png - 2 - * - L4 - .. image:: images/pieces/polyominoes/L4.png - 8 - yes * - O4 - .. image:: images/pieces/polyominoes/O4.png - 1 - * - T4 - .. image:: images/pieces/polyominoes/T4.png - 4 - * - | Z4 | ("S4") - .. image:: images/pieces/polyominoes/Z4.png - 4 - yes Pentominoes ----------- There are 12 free pentominoes (order-5 polyominoes) and 18 one-sided pentominoes: .. list-table:: :widths: 20 20 20 20 :header-rows: 1 * - Name - Image - Aspects - One-Sided * - F - .. image:: images/pieces/polyominoes/F.png - 8 - yes * - I - .. image:: images/pieces/polyominoes/I.png - 2 - * - L - .. image:: images/pieces/polyominoes/L.png - 8 - yes * - N - .. image:: images/pieces/polyominoes/N.png - 8 - yes * - P - .. image:: images/pieces/polyominoes/P.png - 8 - yes * - T - .. image:: images/pieces/polyominoes/T.png - 4 - * - U - .. image:: images/pieces/polyominoes/U.png - 4 - * - V - .. image:: images/pieces/polyominoes/V.png - 4 - * - W - .. image:: images/pieces/polyominoes/W.png - 4 - * - X - .. image:: images/pieces/polyominoes/X.png - 1 - * - Y - .. image:: images/pieces/polyominoes/Y.png - 8 - yes * - Z - .. image:: images/pieces/polyominoes/Z.png - 4 - yes Hexominoes ---------- There are 35 free hexominoes (order-6 polyominoes) and 60 one-sided hexominoes: .. list-table:: :widths: 20 20 20 20 :header-rows: 1 * - Name - Image - Aspects - One-Sided * - | A06 | (Kadon's "A") - .. image:: images/pieces/polyominoes/A06.png - 4 - * - C06 - .. image:: images/pieces/polyominoes/C06.png - 4 - * - D06 - .. image:: images/pieces/polyominoes/D06.png - 4 - * - E06 - .. image:: images/pieces/polyominoes/E06.png - 4 - * - | F06 | ("hi F") - .. image:: images/pieces/polyominoes/F06.png - 8 - yes * - | F16 | ("low F") - .. image:: images/pieces/polyominoes/F16.png - 8 - yes * - | F26 | ("hi 4") - .. image:: images/pieces/polyominoes/F26.png - 8 - yes * - | F36 | ("low 4") - .. image:: images/pieces/polyominoes/F36.png - 8 - yes * - G06 - .. image:: images/pieces/polyominoes/G06.png - 8 - yes * - H06 - .. image:: images/pieces/polyominoes/H06.png - 8 - yes * - I06 - .. image:: images/pieces/polyominoes/I06.png - 2 - * - J06 - .. image:: images/pieces/polyominoes/J06.png - 8 - yes * - K06 - .. image:: images/pieces/polyominoes/K06.png - 4 - * - L06 - .. image:: images/pieces/polyominoes/L06.png - 8 - yes * - M06 - .. image:: images/pieces/polyominoes/M06.png - 8 - yes * - | N06 [*]_ | ("short N") - .. image:: images/pieces/polyominoes/N06.png - 4 - yes * - | N16 | ("long N") - .. image:: images/pieces/polyominoes/N16.png - 8 - yes * - O06 - .. image:: images/pieces/polyominoes/O06.png - 2 - * - P06 - .. image:: images/pieces/polyominoes/P06.png - 8 - yes * - Q06 - .. image:: images/pieces/polyominoes/Q06.png - 8 - yes * - R06 - .. image:: images/pieces/polyominoes/R06.png - 8 - yes * - | S06 | ("long S") - .. image:: images/pieces/polyominoes/S06.png - 4 - yes * - | T06 | ("long T") - .. image:: images/pieces/polyominoes/T06.png - 4 - * - | T16 | ("short T") - .. image:: images/pieces/polyominoes/T16.png - 8 - yes * - U06 - .. image:: images/pieces/polyominoes/U06.png - 8 - yes * - V06 - .. image:: images/pieces/polyominoes/V06.png - 8 - yes * - | W06 | ("Wa") - .. image:: images/pieces/polyominoes/W06.png - 8 - yes * - | W16 | ("Wb") - .. image:: images/pieces/polyominoes/W16.png - 4 - yes * - | W26 | ("Wc") - .. image:: images/pieces/polyominoes/W26.png - 8 - yes * - X06 - .. image:: images/pieces/polyominoes/X06.png - 4 - * - | X16 | ("italic X") - .. image:: images/pieces/polyominoes/X16.png - 4 - yes * - | Y06 | ("hi Y") - .. image:: images/pieces/polyominoes/Y06.png - 8 - yes * - | Y16 | ("low Y") - .. image:: images/pieces/polyominoes/Y16.png - 4 - * - | Z06 | ("long Z") - .. image:: images/pieces/polyominoes/Z06.png - 4 - yes * - | Z16 | ("short Z") - .. image:: images/pieces/polyominoes/Z16.png - 8 - yes .. [*] Kadon's `Sextillions`_ set includes a second copy of N06 called "short S", also adopted by Polyform Puzzler's `Hexominoes Plus`_ as "S16". .. _Sextillions: http://gamepuzzles.com/polycub2.htm#SX .. _Hexominoes Plus: hexominoes.html#hexominoes-plus Coordinate System ================= Polyominoes use a standard 2-dimensional *(x,y)* Cartesian coordinate system. Each unit square has 4 immediate neighbors. The neighbors of the square at coordinates *(x, y)* are: *{(x+1, y), (x-1, y), (x, y+1), (x, y-1)}* `See the FAQ for more details. `__ .. _Poly-4 Supplement: http://www.gamepuzzles.com/poly4.htm .. |c| unicode:: U+00A9 .. copyright sign