Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

POLYOMINOS, ETC.

Previous Up Next

ITEM 108:

See the PROPOSED COMPUTER PROGRAMS section for counts of polyominos of orders < 19.

ITEM 109 (Schroeppel):

Tessellating the plane with polyominos:

Through all hexominos, the plane can be tessellated with each piece (without even flipping any over). All but the four heptominos below can tessellate the plane, again without being flipped over. Thus, flipping does not buy you anything through order 7. (There are 108 heptominos). 

H   H   HHH     H      H 
HHHHH   H H   HHHH   HHHH
         HH     H       H
                H       H

ITEM 110 (Schroeppel):

PROBLEM: What rectangles are coverable by various polyominos? For example, 
XX      can cover rectangles which are 3N x M,
X       except if N = 1, then M must be even.
YYYY    can be shown by coloring to cover only rectangles
        having at least one side divisible by four.

ITEM 111 (Schroeppel):

PROBLEM: Find a necessary and sufficient condition for an arbitrary shape in the plane to be domino coverable.

ITEM 112 (Beeler):

"Iamonds" are made of equilateral triangles, like diamonds.

"(Poly-)ominos" are made of squares, like dominos.

"Hexafrobs" are made of hexagons.

"Soma-like" pieces are made of cubes.

See also "Polyiamonds", Math. Games, Sci. Am., December 1964. Left and right 3-dimensional forms are counted as distinct. 

ORDER   IAMONDS OMINOS  HEXA'S  SOMA-LIKE
 1        1      1       1       1
 2        1      1       1       1
 3        1      2       3       2
 4        3      5       7       8
 5        4     12      22      29
 6       12     35
 7       24
 8       66
 9      160
10      448
Polyominos of order 1, 2 and 3 cannot form a rectangle. Orders 4 and 6 can be shown to form no rectangles by a checkerboard coloring. Order 5 has several boards and its solutions are documented (Communications of the ACM, October 1965): 
BOARD   DISTINCT SOLUTIONS
3 X 20     2
4 X 15   368
5 X 12  1010
6 X 10  2339 (verified)
two 5 x 6 -- 2
8 x 8 with 2 x 2 hole in center -- 65
CONJECTURE (Schroeppel): If the ominos of a given order form rectangles of different shapes, the rectangle which is more nearly square will have more solutions.

Order-4 hexafrob boards and solution counts:

Order-6 iamond boards and solution counts (see illustration): With Soma-like pieces, orders 1, 2 and 3 do not have interesting boxes. Order 4 has 1390 distinct solutions for a 2 x 4 x 4 box. 1124 of these have the four-in-a-row on an edge; the remaining 266 have that piece internal. 320 solutions are due to variations of ten distinct solutions decomposable into two 2 x 2 x 4 boxes. A soma-like 2 x 4 x 4 solution: 
AAAA    BBHH
BCCC    BHHC
DDDE    FGGE
FDGE    FFGE
The commercial Soma has 240 distinct solutions; the booklet which comes with it say this was found years ago on a 7094. Verified by both Beeler and Clements.

Previous Up Next