Polyomino

A polyomino (made-up word, derived from domino ) is a surface made up of connected squares . ${\displaystyle n}$

For small ones the terms Monomino ( ), Domino ( ), Tromino ( ), Tetromino ( ), Pentomino ( ), Hexomino ( ), Heptomino ( ), Oktomino ( ), Nonomino or Enneomino ( ), Dekomino ( ), Undekomino ( ), Dodekomino ( ) etc. common. ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n=2}$ ${\displaystyle n=3}$ ${\displaystyle n=4}$ ${\displaystyle n=5}$ ${\displaystyle n=6}$ ${\displaystyle n=7}$ ${\displaystyle n=8}$ ${\displaystyle n=9}$ ${\displaystyle n=10}$ ${\displaystyle n=11}$ ${\displaystyle n=12}$

definition

A polyomino or mino is a figure made up of congruent squares for which applies ${\displaystyle n}$ ${\displaystyle P}$ ${\displaystyle n\geq 1}$

1. every two squares either have no point or a corner or an edge in common,
2. to two different squares each and from there is a sequence of neighboring squares . ${\displaystyle Q_{1}}$ ${\displaystyle Q^{*}}$ ${\displaystyle P}$ ${\displaystyle Q_{1}Q_{2}\ldots Q_{k-1}Q^{*}}$ ${\displaystyle P}$

Two squares are called adjacent if the set of their common points is one side. The following examples therefore do not represent polyominos.

1. invalid

2. invalid

3. invalid

4. invalid

For special applications, the following is also required:

• ${\displaystyle P}$forms a simply connected set of points.

Polyomino with hole

Representation via connection graph

A relationship graph can be assigned to each polyomino by representing each square from as a node and the neighboring two squares as an edge. This is shown below using the 5 tetrominos. ${\displaystyle P}$ ${\displaystyle P}$

construction

the 5 tetrominos

the 12 pentominos

the 35 hexominos

Determination of the numbers

There are different approaches to determining the number of polyominos. Most often, a distinction is only made up to congruence . In practical situations, however, only orientation -preserving movements are often permitted for bringing them into alignment , i.e. only rotations and displacements and no axis mirroring . This is also the case with the game Tetris . Congruent polyominos that have a different orientation are viewed as different

non-orientation preserving movement

non-orientation preserving movement

${\displaystyle A(n)}$describes the number of polyominos that can be formed from squares up to congruence . is the number considering the orientation, i. H. Mirror images of each other (as illustrated above) are considered different. refers to the number taking into account the orientation and all possible positions, even two rotated but otherwise identical polyominos are considered different. Most of all is of interest. ${\displaystyle n}$ ${\displaystyle A'(n)}$ ${\displaystyle A''(n)}$ ${\displaystyle A(n)}$

${\displaystyle n}$	${\displaystyle A(n)}$	${\displaystyle A'(n)}$	${\displaystyle A''(n)}$
1	1	1	1
2	1	1	2
3	2	2	6th
4th	5	7th	19th
5	12	18th	63
6th	35	60	216
7th	108	196	760
8th	369	704	2,725
9	1,285	2,500	9,910
10	4,655	9,189	36,446
11	17,073	33,896	135,268
12	63,600	126,759	505.861
13	238,591	476.270	1,903 890
14th	901.971	1,802,312	7,204,874
15th	3,426,576	6,849,777	27,394,666

If only simply connected polyominos are counted, different numbers result from on. ${\displaystyle n=7}$

Recursive continuation

algorithm

One can easily describe a recursive procedure that allows all -Minos to be obtained from the knowledge of all -Minos . It can first be shown that for a -Mino there is a -Mino and a square such that is. This means that knowledge of the classes of the minos can be assumed. By adding a square, a representative of each class of -Minos is created. In this way the number of classes can also be determined. We do as follows. ${\displaystyle n-1}$ ${\displaystyle (n\geq 2)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle P_{2}}$ ${\displaystyle (n\geq 2)}$ ${\displaystyle n-1}$ ${\displaystyle P_{1}}$ ${\displaystyle Q}$ ${\displaystyle P_{2}=P_{1}\cup Q}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle A(n)}$

We number the classes of the -Minos and begin with a representative of the first class, and systematically consider all positions of a square that can lead to a -Mino at all . These positions are marked with or , depending on whether the corresponding -Mino is congruent to the previous ones or not. Proceed in the same way for the next classes of -Minos. Of course, a -Mino can arise, which is congruent to one of the previous steps. Such are marked with a location box . ${\displaystyle n-1}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle n}$ ${\displaystyle P\cup Q}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle (i=1,2,\ldots )}$

After a finite number of steps, the process breaks off and it provides a representative for each class of -Minos. ${\displaystyle n}$

example

The recursive algorithm should be used to determine the pentominos from tetrominos.

Computerized

On the basis of this procedure, those with computers can be determined. Polyominos can be described by a matrix with 0 and 1 as in the following example. becomes ${\displaystyle A(n)}$
${\displaystyle {\begin{pmatrix}1&1&1&0\\1&0&1&1\\1&0&0&0\end{pmatrix}}}$

Hexominos

A subgroup of 11 of the 35 hexominos represent, geometrically speaking, the network of a cube, as it is bounded by 6 square surfaces.

use

Packs

What are the necessary and sufficient conditions for the positive integer side lengths of a rectangle so that it can be packed with certain types of polyominos.

Games industry

The games domino and pentomino (term comes from the American mathematician Solomon W. Golomb ) are widespread. Tetrominos are used, among other things, in the computer game Tetris developed by the Russian programmer Alexei Paschitnow in 1985 , whereby more complex versions of this game also make use of other polyominos - possibly poly cubes . A board game that comes close to the computer game Tetris is FITS (2009) by Reiner Knizia . It explicitly took the computer game as its model. Other newer board games are Blokus , published in 2000, and Ubongo (2005), where the various large minos are used as game material. The games Patchwork (2014) and Cottage Garden (2016) by Uwe Rosenberg as well as Die Baumeister von Arkadia (2006) by Rüdiger Dorn , NMBR 9 (2017) by Peter Wichmann and Bärenpark (2017) by Phil Walker-Harding also use these forms as Laying parts. In Ein Fest für Odin (2016) by Uwe Rosenberg, the plates are arranged in a rectangle. This game is also classified as a polyomino game. In 2001 the game Rumis appeared , which uses three-dimensional stones (poly cubes). ${\displaystyle n}$ ${\displaystyle n=1..5}$

pedagogy

The building blocks are used in elementary schools and serve to improve spatial awareness. The aim is to find figures for a given set of building blocks or to break them down into the corresponding building blocks for given figures.

It is not possible to create a 5 × 4 rectangle from all 5 possible Tetronimos. It is also not possible to create a 4 × 4 square from tetrominos without using an elbow multiple times. The figures used are when Tetrominos be used for them, similar to the letter L, T and Z, also LTZ- parquetry called.

Related topics

• Poly cubes (also poly cubes) - the three-dimensional counterpart with cubes

literature

• Solomon W. Golomb : Polyominoes. Puzzles, Patterns, Problems, and Packings . 2nd expanded edition. Princeton University Press, Princeton 1994, ISBN 0-691-08573-0

Web links

Commons : Polyomino  - collection of images, videos and audio files

• Polyominos at Wolfram Mathworld
• Gerard's Universal Polyomino Solver
• Puzzle with 3D polyominos
• Game to fill with polyominos 2D ( Memento from April 20, 2008 in the Internet Archive )
• Plane figures - polygons (application for children) ( Memento from September 28, 2007 in the Internet Archive )

Individual evidence

1. ↑ Follow A000105 in OEIS
2. ↑ Follow A000988 in OEIS
3. ↑ Follow A001168 in OEIS
4. ↑ For example, sequence A000104 in OEIS
5. ↑ Overview of polyomino games at Boardgamegeek
6. ^ Review of Rumis at hall9000.de