Editing Pentomino

{{Short description|Geometric shape formed from five squares}}
[[File:All 18 Pentominoes.svg|thumb|right|upright=1.7|The 12 pentominoes can form 18 different shapes, with 6 of them (the chiral pentominoes) being mirrored.]]

A '''pentomino''' (or '''5-omino''') is a [[polyomino]] of order 5; that is, a [[polygon]] in the [[Plane (geometry)|plane]] made of 5 equal-sized [[square]]s connected edge to edge. The term is derived from the Greek word for '[[5]]' and "[[domino]]". When [[rotation symmetry|rotations]] and [[reflection symmetry|reflections]] are not considered to be distinct shapes, there are 12 different ''[[Free polyomino|free]]'' pentominoes. When reflections are considered distinct, there are 18 ''[[One-sided polyomino|one-sided]]'' pentominoes. When rotations are also considered distinct, there are 63 ''[[Fixed polyomino|fixed]]'' pentominoes.

Pentomino [[tiling puzzle]]s and games are popular in [[recreational mathematics]].<ref name=Harshbarger>{{cite web| url = http://www.ericharshbarger.org/pentominoes/| title = Eric Harshbarger - Pentominoes}}</ref> Usually, [[video game]]s such as ''[[Tetris]]'' imitations and [[Rampart (game)|''Rampart'']] consider mirror reflections to be distinct, and thus use the full set of 18 one-sided pentominoes. (Tetris itself uses 4-square shapes.)

Each of the twelve pentominoes satisfies the [[Conway criterion]]; hence, every pentomino is capable of [[tiling the plane]].<ref>{{cite book |last=Rhoads |first=Glenn C. |title=Planar Tilings and the Search for an Aperiodic Prototile |year=2003 |publisher=PhD dissertation, Rutgers University}}</ref> Each [[Chirality|chiral]] pentomino can tile the plane without being reflected.<ref>{{cite journal |last=Gardner |first=Martin |date=August 1975 |title=More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes |journal=[[Scientific American]] |volume=233 |issue=2 |pages=112–115|doi=10.1038/scientificamerican0775-112 }}</ref>

==History==
[[File:Pentomino Naming Conventions.svg|thumb|upright=1.5|Comparison of labeling schemes for the 12 possible pentomino shapes. The first naming convention is the one used in this article. The second method is Conway's.]]
The earliest puzzle containing a complete set of pentominoes appeared in [[Henry Dudeney]]'s book, [[The Canterbury Puzzles]], published in 1907.<ref>{{Cite web |title=The Project Gutenberg eBook of The Canterbury Puzzles, by Henry Ernest Dudeney |url=https://www.gutenberg.org/files/27635/27635-h/27635-h.htm#p74 |access-date=2022-03-26 |website=www.gutenberg.org}}</ref> The earliest tilings of rectangles with a complete set of pentominoes appeared in [[the Problemist]] Fairy Chess Supplement in 1935, and further tiling problems were explored in the PFCS, and its successor, the [[Fairy Chess Review]].<ref>{{Cite web |title=Dissection Problems in PFCS/FCR: Summary of Results in Date Order |url=https://www.mayhematics.com/d/db.htm |access-date=2022-03-26 |website=www.mayhematics.com}}</ref><ref>{{cite book |url=https://archive.org/details/B-001-004-123/ |title=Hexaflexagons and other mathematical diversions |first=Martin |last=Gardner |author-link=Martin Gardner |publisher=The University of Chicago Press |date=1988 |chapter=13: Polyominoes |pages=124–140 |isbn=0-226-28254-6 |chapter-url=https://archive.org/details/B-001-004-123/page/n131/mode/2up}}</ref>{{rp|127}}

Pentominoes were formally defined by American professor [[Solomon W. Golomb]] starting in 1953 and later in his 1965 book ''[[Polyominoes: Puzzles, Patterns, Problems, and Packings]]''.<ref name=Harshbarger /><ref>{{cite web| url = http://people.rit.edu/mecsma/Professional/Puzzles/Pentominoes/P-Intro.html| title = people.rit.edu - Introduction - polyomino and pentomino}}</ref> They were introduced to the general public by [[Martin Gardner]] in his October 1965 [[Mathematical Games column]] in [[Scientific American]]. Golomb coined the term "pentomino" from the [[Ancient Greek]] {{lang|grc|πέντε}} / ''pénte'', "five", and the -omino of [[domino]], fancifully interpreting the "d-" of "domino" as if it were a form of the Greek prefix "di-" (two). Golomb named the 12 [[Free polyomino|''free'']] pentominoes after letters of the [[Latin alphabet]] that they resemble, using the [[mnemonic]] FILiPiNo along with the end of the alphabet (TUVWXYZ).<ref>{{cite book |url=https://archive.org/details/polyominoes00golo/ |title=Polyominoes |first1=Solomon W. |last1=Golomb |author1-link=Solomon W. Golomb |first2=Warren |last2=Lushbaugh |publisher=Charles Scribner's Sons |location=New York |date=1965 |lccn=64-24805}}</ref>{{rp|23}}

[[John Horton Conway]] proposed an alternate labeling scheme for pentominoes, using O instead of I, Q instead of L, R instead of F, and S instead of N. The resemblance to the letters is more strained, especially for the O pentomino, but this scheme has the advantage of using 12 consecutive letters of the alphabet. It is used by convention in discussing [[Conway's Game of Life]], where, for example, one speaks of the R-pentomino instead of the F-pentomino.

==Symmetry==
* F, L, N, P, and Y can be oriented in 8 ways: 4 by rotation, and 4 more for the mirror image. Their [[symmetry group]] consists only of the [[identity function|identity mapping]].
* T, and U can be oriented in 4 ways by rotation. They have an axis of [[reflection symmetry|reflection]] aligned with the gridlines. Their symmetry group has two elements, the identity and the reflection in a line parallel to the sides of the squares.
* V and W also can be oriented in 4 ways by rotation. They have an axis of reflection symmetry at 45° to the gridlines. Their symmetry group has two elements, the identity and a diagonal reflection.
* Z can be oriented in 4 ways: 2 by rotation, and 2 more for the mirror image. It has point symmetry, also known as [[rotational symmetry]] of order 2. Its symmetry group has two elements, the identity and the 180° rotation.
* I can be oriented in 2 ways by rotation. It has two axes of reflection symmetry, both aligned with the gridlines. Its symmetry group has four elements, the identity, two reflections and the 180° rotation. It is the [[dihedral group]] of order 2, also known as the [[Klein four-group]].
* X can be oriented in only one way. It has four axes of reflection symmetry, aligned with the gridlines and the diagonals, and rotational symmetry of order 4. Its symmetry group, the dihedral group of order 4, has eight elements.

The F, L, N, P, Y, and Z pentominoes are [[Chirality (mathematics)|chiral]]; adding their reflections (F′, J, N′, Q, Y′, S) brings the number of ''one-sided'' pentominoes to 18. If rotations are also considered distinct, then the pentominoes from the first category count eightfold, the ones from the next three categories (T, U, V, W, Z) count fourfold, I counts twice, and X counts only once. This results in 5×8 + 5×4 + 2 + 1 = 63 ''fixed'' pentominoes.

The eight possible orientations of the F, L, N, P, and Y pentominoes, and the four possible orientations of the T, U, V, W, and Z pentominoes are illustrated:

<gallery mode=packed heights=75px widths=150px caption="Eight possible orientations">
File:F-pentomino Symmetry.svg|F-pentomino
File:L-pentomino Symmetry.svg|L-pentomino
File:N-pentomino Symmetry.svg|N-pentomino
File:P-pentomino Symmetry.svg|P-pentomino
File:Y-pentomino Symmetry.svg|Y-pentomino
</gallery>
<gallery mode=packed heights=120px widths=120px caption="Four possible orientations">
File:T-pentomino Symmetry.svg|T-pentomino
File:U-pentomino Symmetry.svg|U-pentomino
File:V-pentomino Symmetry.svg|V-pentomino
File:W-pentomino Symmetry.svg|W-pentomino
File:Z-pentomino Symmetry.svg|Z-pentomino
</gallery>

For 2D figures in general there are two more categories:
* Being orientable in 2 ways by a rotation of 90°, with two axes of reflection symmetry, both aligned with the diagonals. This type of symmetry requires at least a [[heptomino]].
* Being orientable in 2 ways, which are each other's mirror images, for example a [[swastika]]. This type of symmetry requires at least an [[octomino]].

== Games ==
=== Tiling puzzle (2D) ===
[[File:Pentomino Puzzle Solutions.svg|thumb|right|upright=2|Example tilings]]

A standard '''pentomino puzzle''' is to [[tessellation|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 6×10 case was first solved in 1960 by married couple [[C. Brian Haselgrove|Colin Brian Haselgrove]] and [[Jenifer Haselgrove]].<ref>{{cite journal |author=C. B. Haselgrove |author2=Jenifer Haselgrove |date=October 1960 |title=A Computer Program for Pentominoes |journal=[[Eureka (University of Cambridge magazine)|Eureka]] |volume=23 |pages=16–18|url=https://www.archim.org.uk/eureka/archive/Eureka-23.pdf}}</ref> There are exactly 2,339 solutions, excluding trivial variations obtained by rotation and reflection of the whole rectangle but including rotation and reflection of a subset of pentominoes (which sometimes provides an additional solution in a simple way). The 5×12 box has 1010 solutions, the 4×15 box has 368 solutions, and the 3×20 box has just 2 solutions (one is shown in the figure, and the other one can be obtained from the solution shown by rotating, as a whole, the block consisting of the L, N, F, T, W, Y, and Z pentominoes).

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.<ref>Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.</ref> There are 65 solutions. Scott's algorithm was one of the first applications of a [[backtracking]] computer program. Variations of this puzzle allow the four holes to be placed in any position. One of the external links uses this rule.

Efficient algorithms have been described to solve such problems, for instance by [[Donald Knuth]].<ref>Donald E. Knuth. [https://arxiv.org/abs/cs/0011047 "Dancing links"]. Includes a summary of Scott's and Fletcher's articles.</ref> Running on modern [[personal computer|hardware]], these pentomino puzzles can now be solved in mere seconds.

[[File:Pentomino unsolvable.svg|thumb|left|upright=1.5|Unsolvable patterns]]
Most such patterns are solvable, with the exceptions of placing each pair of holes near two corners of the board in such a way that both corners could only be fitted by a P-pentomino, or forcing a T-pentomino or U-pentomino in a corner such that another hole is created.

The pentomino set is the only free [[polyomino]] set that can be packed into a rectangle, with the exception of the trivial [[monomino]] and [[domino (mathematics)|domino]] sets, each of which consists only of a single rectangle.

=== Box filling puzzle (3D) ===
[[File:Pentomino Cube Solutions.svg|thumb|upright=2|Sample solutions to pentacube puzzles of the stated dimensions, drawn one layer at a time.]]
A '''pentacube''' is a [[polycube]] of five cubes. Of the 29 one-sided pentacubes, exactly twelve pentacubes are flat (1-layer) and correspond to the twelve pentominoes extruded to a depth of one square.

A '''pentacube puzzle''' or 3D '''pentomino puzzle''', amounts to filling a 3-dimensional box with the 12 flat pentacubes, i.e. cover it without overlap and without gaps. Since each pentacube has a volume of 5 unit cubes, the box must have a volume of 60 units. Possible sizes are 2×3×10 (12 solutions), 2×5×6 (264 solutions) and 3×4×5 (3940 solutions).<ref>{{cite book |last1=Barequet |first1=Gill |last2=Tal |first2=Shahar |year=2010 |chapter=Solving General Lattice Puzzles |editor1-first=Der-Tsai |editor1-last=Lee |editor2-first=Danny Z. |editor2-last=Chen |editor3-first=Shi |editor3-last=Ying |title=Frontiers in Algorithmics |series=Lecture Notes in Computer Science |volume=6213 |url=https://archive.org/details/frontiersalgorit00leed |url-access=limited |pages=[https://archive.org/details/frontiersalgorit00leed/page/n132 124]–135 |location=Berlin Heidelberg |publisher=[[Springer Science+Business Media]] |doi=10.1007/978-3-642-14553-7_14|isbn=978-3-642-14552-0 }}</ref>

Alternatively one could also consider combinations of five cubes that are themselves 3D, i.e., those which include more than just the 12 "flat" single-layer thick combinations of cubes. However, in addition to the 12 "flat" [[Polycube|pentacubes]] formed by extruding the pentominoes, there are 6 sets of chiral pairs and 5 additional pieces, forming a total of 29 potential [[Polycube|pentacube]] pieces, which gives 145 cubes in total (=29×5); as 145 can only be packed into a box measuring 29×5×1, it cannot be formed by including the non-flat pentominoes.

=== Commercial board games ===

There are [[board game]]s of skill based entirely on pentominoes. Such games are often simply called "Pentominoes".

One of the games 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. This version of Pentominoes is called "Golomb's Game".{{sfnp|Pritchard|1982|p=83}}

The two-player version has been [[solved board games|weakly solved]] in 1996 by Hilarie Orman. It was proved to be a first-player win by examining around 22 billion board positions.<ref>Hilarie K. Orman. [http://www.msri.org/publications/books/Book29/files/orman.pdf Pentominoes: A First Player Win] (Pdf).</ref>

Pentominoes, and similar shapes, are also the basis of a number of other tiling games, patterns and puzzles. For example, the French board game ''[[Blokus]]'' is played with 4 colored sets of [[polyominoes]], each consisting of every pentomino (12), tetromino (5), triomino (2) domino (1) and monomino (1). Like the game ''Pentominoes'', the goal is to use all of your tiles, and a bonus is given if the monomino is played on the last move. The player with the fewest blocks remaining wins.

The game of ''[[Cathedral (board game)|Cathedral]]'' is also based on [[polyominoes]].<ref>{{cite web| url = http://www.cathedral-game.co.nz/hints.htm| title = FAQ}}</ref>

[[Parker Brothers]] released a multi-player pentomino board game called ''Universe'' in 1966. Its theme is based on a deleted scene from the 1968 film ''[[2001: A Space Odyssey (film)|2001: A Space Odyssey]]'' in which an astronaut is playing a two-player pentomino game against the [[HAL 9000|HAL 9000 computer]] ([[Poole versus HAL 9000|a scene with a different astronaut playing chess]] was retained). The front of the board game box features scenes from the movie as well as a caption describing it as the "game of the future". The game comes with four sets of pentominoes in red, yellow, blue, and white. The board has two playable areas: a base 10x10 area for two players with an additional 25 squares (two more rows of 10 and one offset row of five) on each side for more than two players.

Game manufacturer [[Lonpos]] has a number of games that use the same pentominoes, but on different game planes. Their ''101 Game'' has a 5 x 11 plane. By changing the shape of the plane, thousands of puzzles can be played, although only a relatively small selection of these puzzles are available in print.

=== Video games ===
* ''[[Tetris]]'' was inspired by pentomino puzzles, although it uses four-block [[Tetromino|tetrominoes]]. Some Tetris clones and variants, like the game ''5s'' included with [[Plan 9 from Bell Labs]], and ''[[Magical Tetris Challenge]]'', do use pentominoes.
* ''[[Daedalian Opus]]'' uses pentomino puzzles throughout the game.

You can also have a pentomino made out of nine pentominoes. [[File:Triplication of pentaminoes.png]]

== Literature ==
Pentominoes were featured in a prominent subplot of [[Arthur C. Clarke]]'s 1975 novel ''[[Imperial Earth]]''. Clarke also wrote an [[essay]] in which he described the game and how he got hooked on it.<ref>''Could you solve Pentominoes?'' by Arthur C. Clarke, ''Sunday Telegraph Magazine'', September 14, 1975; reprinted in Clarke's ''Ascent to Orbit: A Scientific Autobiography'', New York: John Wiley & Sons, 1984. {{isbn|047187910X}}</ref>

They were also featured in [[Blue Balliett]]'s ''[[Chasing Vermeer]]'', which was published in 2003 and illustrated by [[Brett Helquist]], as well as its sequels, ''[[The Wright 3]]'' and ''[[The Calder Game]]''.<ref>''Chasing Vermeer'', by Blue Balliett, Scholastic Paperbacks, {{isbn|0439372976}}</ref>

In [[The New York Times crossword puzzle|''The New York Times'' crossword puzzle]] for June 27, 2012, the clue for an 11-letter word at 37 across was "Complete set of 12 shapes formed by this puzzle's black squares."<ref>{{Cite web|last=Buckley|first=Mike|date=June 27, 2012|editor-last=Shortz|editor-first=Will|title=The Crossword|url=https://www.nytimes.com/crosswords/game/daily/2012/06/27|archive-url=|archive-date=|access-date=30 July 2020|website=New York Times}}</ref>

==See also==
===Previous and Next orders===
*[[Tetromino]]
*[[Hexomino]]
===Others===
{{commons category|Pentominoes}}
* [[Tiling puzzle]]
* [[Cathedral (board game)|''Cathedral'']] board game
* [[Solomon W. Golomb]]

== Notes ==
{{reflist}}

== References ==
{{refbegin}}
* [http://www.scholastic.com/chasingvermeer Chasing Vermeer], with information about the book Chasing Vermeer and a click-and-drag pentomino board.
* {{cite book
 |last=Pritchard
 |first=D. B.
 |author-link=David Pritchard (chess player)
 |title=Brain Games
 |publisher=[[Penguin Books|Penguin Books Ltd]]
 |year=1982
 |chapter=Golomb's Game
 |pages=83–85
 |isbn=0-14-00-5682-3}}
{{refend}}

==External links==
* [http://isomerdesign.com/Pentomino Pentomino configurations and solutions] An exhaustive listing of solutions to many of the classic problems showing how each solution relates to the others.

{{Polyforms}}

[[Category:Mathematical games]]
[[Category:Polyforms]]
[[Category:Solved games]]