HAKMEM -- POLYOMINOS, ETC. -- DRAFT, NOT YET PROOFED

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:

side 7 triangle -- no solutions

parallelogram, base 7, side 4 -- 9 distinct solutions, e.g., A A A A B C C D E B B C F C D E E B F G G D D E F F G G

Order-6 iamond boards and solution counts (see illustration):

side 9 triangle with inverted side 3 triangle in center removed -- no solutions
trapezoid, side 6, bases 3 and 3+6 -- no solutions
two triangles of side 6 -- no solutions
trapezoid, side 4, bases 7 and 7+4 -- 76 distinct solutions
parallelogram, base 6, side 6 -- 156 distinct solutions
parallelogram, base 4, side 9 -- 37 distinct solutions
parallelogram, base 3, side 12 --- no solutions
triangle of side 9 with triangles of side 1, 2 and 2 removed from its corners (a commercial puzzle) -- 5885 distinct solutions

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