Pentomino
Encyclopedia
Polyomino
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling with a connected interior....
composed of five (Ancient Greek
Ancient Greek
Ancient Greek is the stage of the Greek language in the periods spanning the times c. 9th–6th centuries BC, , c. 5th–4th centuries BC , and the c. 3rd century BC – 6th century AD of ancient Greece and the ancient world; being predated in the 2nd millennium BC by Mycenaean Greek...
/ pénte) congruent
Congruence (geometry)
In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
squares, connected along their edges (which sometimes is said to be an orthogonal
Orthogonality
Orthogonality occurs when two things can vary independently, they are uncorrelated, or they are perpendicular.-Mathematics:In mathematics, two vectors are orthogonal if they are perpendicular, i.e., they form a right angle...
connection).
There are 12 different free pentominoes, often named after the letters of the Latin alphabet
Latin alphabet
The Latin alphabet, also called the Roman alphabet, is the most recognized alphabet used in the world today. It evolved from a western variety of the Greek alphabet called the Cumaean alphabet, which was adopted and modified by the Etruscans who ruled early Rome...
that they vaguely resemble. Ordinarily, the pentomino obtained by reflection
Reflection symmetry
Reflection symmetry, reflectional symmetry, line symmetry, mirror symmetry, mirror-image symmetry, or bilateral symmetry is symmetry with respect to reflection. That is, a figure which does not change upon undergoing a reflection has reflectional symmetry.In 2D there is a line of symmetry, in 3D a...
or rotation of a pentomino does not count as a different pentomino.
The F, L, N, P, Y, and Z pentominoes are chiral
Chirality (mathematics)
In geometry, a figure is chiral if it is not identical to its mirror image, or, more precisely, if it cannot be mapped to its mirror image by rotations and translations alone. For example, a right shoe is different from a left shoe, and clockwise is different from counterclockwise.A chiral object...
in two dimensions; adding their reflections (F', J, N', Q, Y', S) brings the number of one-sided pentominoes to 18. The others, lettered I, T, U, V, W, and X, are equivalent to some rotation of their mirror images. This matters in some computer games, where mirror image moves are not allowed, such as Tetris
Tetris
Tetris is a puzzle video game originally designed and programmed by Alexey Pajitnov in the Soviet Union. It was released on June 6, 1984, while he was working for the Dorodnicyn Computing Centre of the Academy of Science of the USSR in Moscow, Russian Soviet Federative Socialist Republic...
-clones and Rampart.
Each of the twelve pentominoes can be tiled
Tessellation
A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
to fill the plane
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
. In addition, each chiral pentomino can be tiled without using its reflection.
John Horton Conway
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
proposed an alternate labeling scheme. He uses O instead of I, Q instead of L, R instead of F, and S instead of N. The resemblance to the letters is a bit more strained (most notably that the "O," a straight line, bears no resemblance to an actual letter O), but this scheme has the advantage that it uses 12 consecutive letters of the alphabet. This scheme is used in connection with Conway's Game of Life
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
, so it talks about the R-pentomino instead of the F-pentomino.
Symmetry
Considering rotations of multiples of 90 degrees only, there are the following symmetrySymmetry
Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...
categories:
- L, N, P, F and Y can be oriented in 8 ways: 4 by rotation, and 4 more for the mirror image. Their symmetry groupSymmetry groupThe symmetry group of an object is the group of all isometries under which it is invariant with composition as the operation...
consists only of the identity mappingIdentity functionIn mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...
. - T, and U can be oriented in 4 ways by rotation. They have an axis of reflection symmetryReflection symmetryReflection symmetry, reflectional symmetry, line symmetry, mirror symmetry, mirror-image symmetry, or bilateral symmetry is symmetry with respect to reflection. That is, a figure which does not change upon undergoing a reflection has reflectional symmetry.In 2D there is a line of symmetry, in 3D a...
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 symmetryRotational symmetryGenerally speaking, an object with rotational symmetry is an object that looks the same after a certain amount of rotation. An object may have more than one rotational symmetry; for instance, if reflections or turning it over are not counted, the triskelion appearing on the Isle of Man's flag has...
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 groupDihedral groupIn mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
of order 2, also known as the Klein four-groupKlein four-groupIn mathematics, the Klein four-group is the group Z2 × Z2, the direct product of two copies of the cyclic group of order 2...
. - 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.
If reflections of a pentomino are considered distinct, as they are with one-sided pentominoes, then the first and fourth categories above double in size, resulting in an extra 6 pentominoes for a total of 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.
For example, the eight possible orientations of the L, F, N, P, and Y pentominoes are as follows:
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 heptominoHeptominoA heptomino is a polyomino of order 7, that is, a polygon in the plane made of 7 equal-sized squares connected edge-to-edge. The name of this type of figure is formed with the prefix hept-. When rotations and reflections are not considered to be distinct shapes, there are 108 different free...
. - Being orientable in 2 ways, which are each other's mirror images, for example a swastikaSwastikaThe swastika is an equilateral cross with its arms bent at right angles, in either right-facing form in counter clock motion or its mirrored left-facing form in clock motion. Earliest archaeological evidence of swastika-shaped ornaments dates back to the Indus Valley Civilization of Ancient...
. This type of symmetry requires at least an octominoOctominoAn octomino is a polyomino of order 8, that is, a polygon in the plane made of 8 equal-sized squares connected edge-to-edge. The name of this type of figure is formed with the prefix oct-. When rotations and reflections are not considered to be distinct shapes, there are 369 different free...
.
Tiling rectangles
A standard pentomino puzzle is to tileTessellation
A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
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 puzzle
Puzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...
r can probably solve these problems by hand within a few hours. A more challenging task, typically requiring a computer search
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
, is to count the total number of solutions in each case.
The 6×10 case was first solved in 1960 by Colin Brian
C. Brian Haselgrove
Colin Brian Haselgrove was an English mathematician who is best known for his disproof of the Pólya conjecture in 1958....
and Jenifer Haselgrove
Jenifer Haselgrove
Jenifer Haselgrove is a British physicist and computer scientist. She is most noted for her formulation of ray tracing equations in a cold magneto-plasma, now widely known in the radio science community as Haselgrove's Equations.-Haselgrove's Equations:Haselgrove developed her equations at...
. 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 (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
Dana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
as far back as 1958. There are 65 solutions. Scott's algorithm was one of the first applications of a backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
computer program. Variations of this puzzle allow the four holes to be placed in any position. One of the external links uses this rule. 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.
Efficient algorithms have been described to solve such problems, for instance by Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
. Running on modern hardware
Personal computer
A personal computer is any general-purpose computer whose size, capabilities, and original sales price make it useful for individuals, and which is intended to be operated directly by an end-user with no intervening computer operator...
, these pentomino puzzles can now be solved in mere seconds.
Filling boxes
A pentacube is a polycubePolycube
thumb|200px|right|The seven free tetracubesthumb|200px|right|A [[Chirality |chiral]] pentacubethumb|200px|right|Puzzle with a unique solution...
of five cubes. Twelve of the 29 pentacubes 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 these 1-layer pentacubes, i.e. cover it without overlap and without gaps. Each of the 12 pentacubes consists of 5 unit cubes, and are like 2D pentominoes but with unit thickness. Clearly the box must have a volume of 60 units. Possible sizes are 2×3×10, 2×5×6 and 3×4×5. Following are several solutions.
Alternatively one could also consider combinations of five cubes which are themselves 3D, i.e., are not part of one layer of cubes. However, in addition to the 12 extruded pentominoes, 6 sets of chiral pairs and 5 pieces make total 29 pieces, resulting 145 cubes, which will not make a 3D box.
Board game
There are board gameBoard game
A board game is a game which involves counters or pieces being moved on a pre-marked surface or "board", according to a set of rules. Games may be based on pure strategy, chance or a mixture of the two, and usually have a goal which a player aims to achieve...
s of skill based entirely on pentominoes, 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.
The two-player version has been weakly solved in 1996 by Hilarie Orman. It was proved to be a first-player win by examining around 22 billion board positions
Pentominoes, and similar shapes, are also the basis of a number of other tiling games, patterns and puzzles. For example, a French board game called Blokus
Blokus
Blokus is an abstract strategy board game for two to four players, invented by Bernard Tavitian and first released in 2000 by Sekkoïa, a French company. It has won several awards, including the Mensa Select award and the 2004 Teacher's Choice Award....
is played with 4 opposing color sets of polyominoes. In Blokus, each color begins with every pentomino (12), as well as every tetromino (5), every triomino (2), every domino (1) , and every 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 very last move. The player with the fewest blocks remaining wins.
The Cathedral game
Cathedral (board game)
Cathedral is a two-player abstract strategy board game based around a conflict between two factions for territorial supremacy within the bounds of a mediæval city. The game is produced by Chrisbo I.P...
is also based on polyominoes (see for the packed layout.)
Parker Brothers
Parker Brothers
Parker Brothers is a toy and game manufacturer and brand. Since 1883, the company has published more than 1,800 games; among their best known products are Monopoly, Cluedo , Sorry, Risk, Trivial Pursuit, Ouija, Aggravation, and Probe...
released a multi-player pentomino board game called Universe in 1966. Its theme is based on an outtake from the movie 2001: A Space Odyssey
2001: A Space Odyssey (film)
2001: A Space Odyssey is a 1968 epic science fiction film produced and directed by Stanley Kubrick, and co-written by Kubrick and Arthur C. Clarke, partially inspired by Clarke's short story The Sentinel...
in which the astronaut (seen playing chess in the final version) is playing a two-player pentomino game against a computer. 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 4 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 5) on each side for more than two players.
The second manufacturer of a Pentomino based game is Lonpos
Lonpos
*Lonpos is a logic puzzle game in which the player must fit a fixed number of beaded game pieces of various shapes, to fill a set area such as a rectangle or pyramid. The shapes used in Lonpos puzzles are similar to the shapes known as pentominoes...
.
Lonpos has a number of games that uses the same Pentominoes, but on different game planes. The so-called 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).
Literature
Pentominoes were featured in a prominent subplot of Arthur C. ClarkeArthur C. Clarke
Sir Arthur Charles Clarke, CBE, FRAS was a British science fiction author, inventor, and futurist, famous for his short stories and novels, among them 2001: A Space Odyssey, and as a host and commentator in the British television series Mysterious World. For many years, Robert A. Heinlein,...
's novel Imperial Earth
Imperial Earth
Imperial Earth is a novel written by Arthur C. Clarke, and published in time for the U.S. bicentennial in 1976 by Ballantine Books. The plot follows the protagonist, Duncan Makenzie, on a trip to Earth from his home on Titan, ostensibly for a diplomatic visit to the U.S...
, published in 1975. They were also featured in Blue Balliett
Blue Balliett
Blue Balliett is an American author, best known for her award-winning novel for children, Chasing Vermeer.Chasing Vermeer, released by Scholastic Press in 2004, is her best known and most highly praised book. Illustrated by Brett Helquist, it concerns the fictitious theft of a painting by...
's Chasing Vermeer
Chasing Vermeer
Chasing Vermeer is a 2004 children's art mystery novel written by Blue Balliett and illustrated by Brett Helquist. Set in Hyde Park, Chicago near the University of Chicago, the novel follows two children, Calder Pillay and Petra Andalee...
, which was published in 2003 and illustrated by Brett Helquist
Brett Helquist
Brett L. Helquist is an American illustrator best known for his work in the children's books A Series of Unfortunate Events. As such, his illustrations for that series have appeared in multiple media, including the books, the audiobook covers, the calendars, and so on.- Background :According to...
, as well as its sequels, The Wright 3
The Wright 3
The Wright 3 is a 2006 children's mystery novel written by Blue Balliett and illustrated by Brett Helquist. It was released in Spring 2006 and is the sequel to the children's novel Chasing Vermeer. It chronicles how Calder, Petra, and Tommy strive to save the Robie House in their neighborhood, Hyde...
and The Calder Game
The Calder Game
The Calder Game is a children's novel written by Blue Balliett and illustrated by Brett Helquist, published in 2008. It is the sequel to The Wright 3...
.
Video games
- Lojix on the ZX SpectrumZX SpectrumThe ZX Spectrum is an 8-bit personal home computer released in the United Kingdom in 1982 by Sinclair Research Ltd...
is clearly derived from pentomino, though it uses a non-standard set of 20 blocks and a 10*10 box. Released in late 1983, the game was marketed via the announcement of a cash prize for the first person to solve the puzzle. - TetrisTetrisTetris is a puzzle video game originally designed and programmed by Alexey Pajitnov in the Soviet Union. It was released on June 6, 1984, while he was working for the Dorodnicyn Computing Centre of the Academy of Science of the USSR in Moscow, Russian Soviet Federative Socialist Republic...
was inspired by pentomino puzzles, although it uses four-block tetrominoes. Some Tetris clones and variants, like the games/5s of Plan 9 from Bell LabsPlan 9 from Bell LabsPlan 9 from Bell Labs is a distributed operating system. It was developed primarily for research purposes as the successor to Unix by the Computing Sciences Research Center at Bell Labs between the mid-1980s and 2002...
, and Magical Tetris ChallengeMagical Tetris ChallengeMagical Tetris Challenge, known in Japan as Magical Tetris Challenge Featuring Mickey, is a puzzle game for the Nintendo 64, Game Boy Color and PlayStation . It was released on January 14, 1999. It is a version of Tetris featuring Disney characters. It was also released in the arcades on the Seta's...
, do use pentominoes. - Daedalian OpusDaedalian Opuswas a puzzle game for the Game Boy released in June of 1990. It was one of the few games produced by the little-known software company Vic Tokai.Cover illustration by Lawrence Fletcher.-Gameplay:...
uses pentomino puzzles throughout the game. - Yohoho! Puzzle PiratesYohoho! Puzzle PiratesYohoho! Puzzle Pirates is a massively multiplayer online role-playing game developed by Three Rings Design. The player takes the role of a pirate, adventuring on the high seas and pillaging money from roaming enemy ships . The mechanics of Puzzle Pirates are driven by puzzles...
carpentry minigame is based on pentomino puzzles. - ChimeChime (video game)Chime is a 2010 music/puzzle video game developed by Zoë Mode, released initially on the Xbox Live Arcade service, and later for Windows. An extended version of the game, called Chime Super Deluxe, was released on the PlayStation Network in March 29, 2011...
uses pentominoes for its pieces. - TwinflixTwinflixTwinflix is an Indie game developed by Franco Mellerio,-Gameplay:Twinflix is a twin fight block game concept having two different game modes, both based on Pentomino.- Classical :...
a free game for iPhoneIPhoneThe iPhone is a line of Internet and multimedia-enabled smartphones marketed by Apple Inc. The first iPhone was unveiled by Steve Jobs, then CEO of Apple, on January 9, 2007, and released on June 29, 2007...
and iPadIPadThe iPad is a line of tablet computers designed, developed and marketed by Apple Inc., primarily as a platform for audio-visual media including books, periodicals, movies, music, games, and web content. The iPad was introduced on January 27, 2010 by Apple's then-CEO Steve Jobs. Its size and...
uses pentomino as well for its gameplay.
See also
- LonposLonpos*Lonpos is a logic puzzle game in which the player must fit a fixed number of beaded game pieces of various shapes, to fill a set area such as a rectangle or pyramid. The shapes used in Lonpos puzzles are similar to the shapes known as pentominoes...
- Tiling puzzleTessellationA tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
- Cathedral (board game)Cathedral (board game)Cathedral is a two-player abstract strategy board game based around a conflict between two factions for territorial supremacy within the bounds of a mediæval city. The game is produced by Chrisbo I.P...
External links
- Pentomino configurations and solutions An exhaustive listing of solutions to many of the classic problems showing how each solution relates to the others.
- Pentomino app The Pentomino game for one player as facebook application. Try it and find more solutions than your facebook friends.
- Pentomino app Pentomino based puzzle games. Drag, rotate and flip pentomino tiles to put together pictures or solve numbers puzzle and more.
- Pentomino solver Program (with C++ source code) to compute the 16146 solutions (provided) for covering the checkerboard with 12 pentominoes and a tetromino.
- Polycube solver Program (with Lua source code) to fill boxes with polycubes using Algorithm X.
- Intriguing rpentomino flash puzzle Puzzle related to the intriguing IP 205.186.183.229.
- BANJEN Pentamino Freeware pentamino based puzzle.