Pentomino
From Exampleproblems
A pentomino is a polyomino composed of five (Greek πέντε / pente) congruent squares, connected orthogonally.
There are twelve different pentominoes, and they are named after letters of the alphabet. (The mirror image of a pentomino does not count as a different pentomino.)
If you allow mirror images to count as different pentominos, this brings the total to 18. The ones lettered T, V, I, X, U, and W have mirror images that are equivalent after rotation. This matters in some computer games, where mirror image moves are not allowed, such as Tetris-clones and Rampart. The F-pentomino is often referred to as the R-pentomino as well, notably in reference to Conway's Game of Life.
Considering rotations of multiples of 90 degrees only, we have the following symmetry categories:
- L, N, P, F and Y can be oriented in 8 ways: 4 by rotation, and 4 more for the mirror image.
- Z can be oriented in 4 ways: 2 by rotation, and 2 more for the mirror image.
- T, V, U and W can be oriented in 4 ways by rotation.
- I can be oriented in 2 ways by rotation.
- X can be oriented in only one way.
For 2D figures in general there is one more category: being orientable in 2 ways, which are each other's mirror image, for example a swastika. There is no pentomino in this category (this type of symmetry requires at least an octomino).
For example, the eight possible orientations of the Y pentomino are as follows:
Contents |
Tiling rectangles
A standard pentomino puzzle is to tile a rectangular box with the pentominoes, i.e. cover it without overlap and without gaps. Each of the 12 pentominoes has an area of 5 unit squares, so the box must have an area of 60 units. Possible sizes are 6×10, 5×12, 4×15 and 3×20. The avid puzzler can probably solve these problems by hand within a few hours. A more challenging task, typically requiring a computer search, is to count the total number of solutions in each case.
The 6×10 case was first solved in 1965 by John Fletcher[1]. There are exactly 2339 solutions, excluding trivial variations obtained by rotation and reflection of the whole rectangle, but including rotation and reflection of a subset of pentominoes (sometimes this is possible and provides in a simple way an additional solution; e.g., with the 3×20 solution shown, the other one is obtained by rotating a set of seven pentominoes, or put differently, by rotating the four leftmost and the rightmost to the other side).
The 5×12 box has 1010 solutions, the 4×15 box has 368 solutions, and the 3×20 box has just 2 solutions.
A somewhat easier (more symmetrical) puzzle, the 8×8 rectangle with a 2×2 hole in the center, was solved by Dana Scott as far back as 1958[2]. There are 65 solutions. Scott's algorithm was one of the first applications of a backtracking computer program ever.
Efficient algorithms have been described to solve such problems, for instance by Donald Knuth[3]. Running on modern hardware, these pentomino puzzles can now be solved in mere seconds.
Trivia
Pentominoes are prominently featured in a subplot of the novel Imperial Earth by Arthur C. Clarke.
"Pentominoes" was registered as a trademark by Solomon W. Golomb (#1008964 USPTO 1975 April 15), but this trademark is no longer in effect as of 1982.
Board game
There is a board game of skill based on pentominoes, called pentominoes.
The game is played on an 8×8 grid by two or three players. Players take turns in placing pentominoes on the board so that they do not overlap with existing tiles and no tile is used more than once. The objective is to be the last player to place a tile on the board.
The two-player version has been weakly solved; it is a first-player win.
Pentominoes, and similar shapes, are also the basis of a number of other tiling patterns and puzzles.
Video game
Tetris was inspired by pentomino puzzles.
See also
- Tiling puzzle
- Sudoku variants
References
- ^ John G. Fletcher (1965). "A program to solve the pentomino problem by the recursive use of macros". Communications of the ACM 8, 621–623.
- ^ Donald E. Knuth. "Dancing links" (Postscript, 1.6 megabytes). Includes a summary of Scott's and Fletcher's articles.
- ^ Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.
External links
- Pentominos Puzzle Solver featuring a Java applet that solves the 8x8 square with 4 holes.
- Fast Pentomino Solver by Bruce Hoyt, written in Forth using generated macros.
- Pentomino Relationships looks at families of pentomino puzzle solutions.
- Pentominoes as the origin of Tetris
- Pentomino.nl, a Shockwave pentomino game (in Dutch and English) with solutions database.de:Pentamino
