Polyominoes: Theme and Variations

Preface
General principle
Variations of the theme: polyforms
Boxes filled with solid pentominoes
References

Warning: the cryptic anchors in this document ("#zzpart..") are generated dynamically. It is unwise to use them in bookmark URLs.
Click on a section title to return to Contents

1. Preface

The purpose of this Web page is to provide information about filling rectangles, other polygons, boxes, etc., with dominoes, trominoes, tetrominoes, pentominoes, solid pentominoes, hexiamonds, and whatever else people have invented as variations of a theme.
Several instances of these problems have been commercially available, sold as so-called `computer puzzles'.

Such information can also be collected while leafing through a couple of compilations of Martin Gardner's Scientific American articles, and looking up references to publications by Golomb, Klarner, or Bouwkamp; one will find nice problems and solutions galore. I do not intend to double everything, but wish to point to a world of interesting problems having a common denominator.

2. General principle

A domino is formed from two squares. Putting three squares together (the squares connect only by complete sides) can be done in two different ways. Five squares can be put together in twelve different ways (apart from rotation and reflection): a piece is called pentomino and the common problem is then to fill an area of size 60 unit squares with all twelve pieces.
12 pieces

One can, for example, fill the 3*20 (2 solutions), 4*15 (368 solutions), 5*12 (1010 solutions) and 6*10 rectangles (2339 solutions), or an 8*8 square (the chess board) with a 2*2 central square excepted (65 solutions).
Pieces can be `solidized' by giving them the thickness of the length unit (i.e., the side of a basic square); the problem then is to fill a box. Alternative problems are to fill an area with identical n-ominoes only, e.g., fill a 5*5*5 cube with 25 (solid) Y-pentominoes (or N or L) (ref. Bouwkamp and Klarner, 1970).
Note that I use the following names for the pieces:

ITUVWX ZFLNPY

which I adopted from Van Wijngaarden (also in agreement with Golomb (1994)).

Truly 3-D pentominoes (called pentacubes) are obtained by putting five cubes together, with full contact of the faces. The number of ways to do this is not a nice number such that a box can be filled with all different ones, irrespective of whether pairs of mirror images are counted as one or two pieces. To my collection belongs a 2*2*8 box containing (the) eight 3-D tetracubes.
The Soma cube, designer Piet Hein (1905-1996), does not use all tetracubes but only the non-convex ones, together with the only non-convex tricube (see Jay Jenicek's Soma Cube Page (apologies, the link I had is now out of date) ).
For further reading see ref. Gardner (1986).

3. Variations of the theme: polyforms

Two equilateral triangles form a diamond. Six equilateral triangles can form twelve different pieces: hexiamonds. According to BCG (this stands for Berlekamp, Conway & Guy) the names like triamond, hexiamond and polyiamond were coined by T.H. O'Beirne (see New Scientist, 1961).

I bought the 12-hexiamond `computer puzzle' (`in the late sixties' (I quote Gardner)) in a box called `wavy rectangle', but large diamonds and hexagons can be filled as well. Below I render four solutions made with a Matlab program (I found 290 solutions, and 156 for the 6*6 diamond):

Here the `rectangle' has four acute angles, but the `sister' puzzle with four obtuse angles is also solvable and solutions fit in the same rectangular box.
Three equilateral triangles form a triamond (in one way only). Two triamonds can be used to form a hexiamond in nine different ways. So only three hexiamonds stay out of this collection. The nine pieces, which I would name 'bi-triamonds', have the area of a regular hexagon of side 3.
Chris Zaal has made a table containing the puzzle of putting the nine bi-triamonds together in such a hexagon; the table has been shown on successive CWI Open House days.

I have found nine solutions
When the reflections of the seven hexiamonds that do not have reflection symmetry are counted as different pieces, there are nineteen pieces all and a symmetric hexagon-like area (with wavy edges) can be filled. Marc Paulhus made a complete Hexiamond HomePage about this puzzle, its history, and all solutions (the ucalgary hyperlink is not valid anymore).
BCG ask for which values of n the n times enlarged (n-larged?) A-hexiamond (the piece touching the middle of the left boundary in the above solutions) can be packed with n*n copies of the A-hexiamond.
Another basic component is the hexagon. Four hexagons, put together in all possible ways, form 7 pieces (called tetrahex). On its 40th anniversary my employer (CWI) produced this puzzle with the 7 pieces in a sort of 4*7 rectangle (see ref. Te Riele and Winter).
I recall having seen a variant where the basic form is a circle extended with one or more 'ears'; an ear means: the shape of space between three tangent circles; around the circle there is room for at most six ears, placed at the regular positions of k*pi/3 (= multiples of 60 degrees); together with the bare circle there are 13 different pieces, which may then fill a sort of hexagonal area.
Related to the latter is the DISCON puzzle (author Jost Hänny).
Discs (flat circular cylinders of equal height) have one to six round vertical holes on a fixed distance of the axis, again at the regular positions of k*pi/3, so there are 12 discs (there is no use for the full disc). Moreover, there are 13 small cylinders that fit in the holes, with height three times the height of a disc. The discs must be placed on top of each other, with the small cylinders filling all holes completely.
filigree: units are now unit segments only, they connect at end points forming angles of 2*pi/3 (120 degrees), staying in the plane. Sets of pieces can be used to cover a part of a beehive pattern.
Another way of looking at this design is, to make pieces with the (60, 120 degrees) diamond as the basic component.
Rubik's Tangle (see also Conway's 1968 Christmas card (BCG)) is another variation.
Take four cubes to form a 2*2*1 block. Two blocks can be joined to one piece (the only allowed connection is by full contact of complete unit-square faces) in ten ways, including two pairs of stereo images. They serve to fill a 4*4*5 box. One might omit one piece of each of the pairs of stereo images, but the attempt to fill a 4*4*4 cube with the eight remaining pieces will fail.
The Binary Square: Van Delft & Botermans (1978) write that it was designed by Bouwkamp. Unit squares have one of two colours: 0 and 1, or black and white, for example. A piece is a square formed by four units in all possible ways, rotation is not allowed. There are 16 possibilities, mappings of the binary representations of 0 - 15: 0000, 0001, 0010, ..., 1111.
The puzzle consists of filling a larger square, size 4*4 pieces, such that the colours of the contacting sides in adjacent pieces agree (rotation of the pieces is still not allowed).
MacMahon's coloured cubes and square tiles
Rouse Ball and Coxeter (see refs.) refer to an article by (major) P.A. MacMahon for the definition of a coloured cubes problem; the cubes are also described on the web, see my bookmarks. The 2-D variant was communicated by Odette De Meulemeester.
- Coloured cubes
  Paint the faces of a cube each with a different colour from a set of six colours. This can be done in essentially 30 different ways (bar rotation).
  One puzzle with the set of 30 different cubes is: take a cube, find eight cubes from the remaining 29 cubes and construct a 2*2*2 copy of the example cube: the colouring of the doubled cube agrees with the example, and on the inside the small cubes may only touch each other with faces of the same colour (here 'touching' means: touching with complete faces)
- Square tiles
  By its diagonals a square can be divided into 4 triangles. Using three colours (red, yellow, blue) for painting the triangles, there are 24 different ways to paint the squares (bar rotation).
  In the same way as for the Rubik's tangle and Binary Square puzzles, the task is to tile a given shape of area 24, for example a 6 * 4 rectangle. Touching sides must have the same colour. An extra constraint can be that one of the colours may not touch the outside border

This account can never be exhaustive. I welcome comments on what further information to provide here. I conclude by treating one subject in more detail.

4. Boxes filled with solid pentominoes

In the early days of automatic computing pentomino problems have been quite popular with computer users, employing their computers (well ..., the computers of their employers) to do an exhaustive search for all solutions of a particular problem. Gardner mentions Dana Scott (1958) for solving the chess board problem, the name Haselgrove (C.B. and J.) is connected to the 6*10 rectangle solution.
In the sixties, Bouwkamp solved the solid pentominoes problem for all possible boxes. Obviously, height-one boxes is not different from the 2-D problems, for 3-D the possibilities are the 2*3*10, 2*5*6, and 3*4*5 boxes. As solutions exist for the 2-D problems 5*12 and 6*10 which consist of two 5*6 rectangles (see the solution rendered above), these trivially solve the 2*5*6 box problem as well, but more solutions (essentially 3-D) exist. For the 3*4*5 box all (3940) solutions are essentially 3-D (see Bouwkamp, 1967).

One solution in common notation is:

 i i i i i    x f n l l    y y y y t
 x v v v t    x f n l t    x f y z t
 u f n v p    x f n l p    u z z z t
 u w n v p    u w w l p    u z w w p

As an example of additional constraints on solutions I mention that Bouwkamp also looked for solutions of the 3*4*5 box with one piece completely inside. This is only possible with the P and U pieces, as these fit in a 1*2*3 box. For both pentominoes such solutions exist indeed.
A solution I found very peculiar myself, for the reason that it beat my test for excluding identical solutions (bar rotation or reflection), is the following: only four pieces cover the four pairs of vertex cubes.

 v v v u u    v l y u f    v l x u u
 i i i i i    t l y y f    w x x x f
 n n z z f    t l y z f    w w x z z
 t n n n p    t l y p p    t w w p p

5. References

BCG: Berlekamp, Conway, Guy: Winning ways for your mathematical plays. Vol. 2, Chapter 24.
C.J. Bouwkamp: Catalogue of solutions of the rectangular 3*4*5 solid pentomino problem. 1967, 310 p., Technische Hogeschool Eindhoven.
C.J. Bouwkamp: An old pentomino problem revisited. Pp. 87-96, in: E.H.L. Aarts, H.M.M. ten Eikelder, C. Hemerik, M. Rem: Simplex Sigillum Veri. Een Liber Amicorum voor prof.dr. F.E.J. Kruseman Aretz, TU Eindhoven, 1995.
C.J. Bouwkamp, D.A. Klarner: Packing a box with y-pentacubes. Journal of recreational mathematics, v.3.1 (1970) pp. 10-26.
P. van Delft, J. Botermans: Spelen met puzzels. De Bezige Bij, 1978.
Several translations exist (I know of English (Creative puzzles of the world) and German versions).
Martin Gardner: Mathematical puzzles and diversions. My copy is a Pelican Book, Penguin, 1964.
Martin Gardner: Martin's Gardner's sixth book of mathematical games from Scientific American. Freeman, San Francisco, 1971. Ch. 18 on polyiamonds and Ch. 24 on tiling with polyominoes.
Martin Gardner: Knotted doughnuts and other mathematical entertainments. Freeman, 1986. Ch. 3 on polycubes, Ch. 6 mentions the pentomino fence problem.
S.W. Golomb: Polyominoes. C. Scribner's, 1965.
Revised and expanded 2nd edition, Princeton University Press, 1994.
H.J.J. te Riele, D.T. Winter: The tetrahexes puzzle. CWI Newsletter, March 1986.
W.W. Rouse Ball, H.S.M. Coxeter: Mathematical recreations and essays. Dover, 1987 (13th ed.)

My (irregularly changing) page of Polyform Bookmarks

To Jan Kok 's HoPa.

Document /~jankok/etc/Polyomino.html , last modified: Nov 4 14:58