Pentomino

From Wikipedia, the free encyclopedia

Comparison of pentomino labeling schemes. The first naming convention is the one used in this article. The second method is Conway's.

A pentomino is a polyomino composed of five (Ancient Greek πέντε / pénte) congruent squares, connected along their edges (which sometimes is said to be an orthogonal connection).

There are 12 different free pentominoes, often named after the letters of the Latin alphabet that they vaguely resemble. Ordinarily, the pentomino obtained by reflection or rotation of a pentomino does not count as a different pentomino.

The F, L, N, P, Y, and Z pentominoes are chiral 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-clones and Rampart.

Each of the twelve pentominoes can be tiled to fill the plane. In addition, each chiral pentomino can be tiled without using its reflection.

John Horton Conway 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, so it talks about the R-pentomino instead of the F-pentomino.

[edit] Symmetry

Considering rotations of multiples of 90 degrees only, there are 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. Their symmetry group consists only of the identity mapping.
• T, and U can be oriented in 4 ways by rotation. They have an axis of reflection symmetry 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.

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, 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 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.

[edit] 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 1960 by Colin Brian and Jenifer Haselgrove.^[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. 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^[3]. Running on modern hardware, these pentomino puzzles can now be solved in mere seconds.

[edit] Filling boxes

A pentacube is a polycube 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.

[edit] Board game

There are board games 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; it is a first-player win.

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 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.

Parker Brothers 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 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 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).

[edit] Video games

• Lojix on the ZX Spectrum 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.
• Tetris 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 Labs, and Magical Tetris Challenge, do use pentominoes.
• Daedalian Opus uses pentomino puzzles throughout the game.
• Yohoho! Puzzle Pirates carpentry minigame is based on pentomino puzzles.

[edit] See also

• Lonpos
• Tiling puzzle

[edit] Notes

[edit] References

[edit] External links

• Pentamino for Pocket PC is a GPLed implementation of the puzzle with a few fun patterns besides ordinary boxes.
• Pentas a small puzzle game and solver.
• Classic 8x8 and 6x10 Pentomino game a Windows game and solver.
• All about pentominoes
• Online Pentomino Puzzle
• Online Flash Version of Pentominoes
• Online Pentominos Puzzle Solver a Java based solver, including source code.