Polyomino
A polyomino (made-up word, derived from domino ) is a surface made up of connected squares .
For small ones the terms Monomino ( ), Domino ( ), Tromino ( ), Tetromino ( ), Pentomino ( ), Hexomino ( ), Heptomino ( ), Oktomino ( ), Nonomino or Enneomino ( ), Dekomino ( ), Undekomino ( ), Dodekomino ( ) etc. common.
definition
A polyomino or mino is a figure made up of congruent squares for which applies
- every two squares either have no point or a corner or an edge in common,
- to two different squares each and from there is a sequence of neighboring squares .
Two squares are called adjacent if the set of their common points is one side. The following examples therefore do not represent polyominos.
For special applications, the following is also required:
- forms a simply connected set of points.
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.
construction
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
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.
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.
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.
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 .
After a finite number of steps, the process breaks off and it provides a representative for each class of -Minos.
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
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).
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
- 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 )