From: reid@durban.berkeley.edu (michael reid)
Newsgroups: sci.math
Subject: Re: polyomino classification
Keywords: polyomino
Date: 14 Apr 92 11:43:48 GMT
Distribution: world
Organization: University of California, Berkeley
NNTP-Posting-Host: durban.berkeley.edu

In article <3007@cvbnetPrime.COM> dwilson@cvbnet.prime.com (David Wilson x5694
4-1600) writes:

>    I was wondering about the ability to tile certain figures with
>    polyominoes.  The figures I am interested in, with cartesian
>    descriptions, are:

>    rectangle (r)		[0, a] X [0, b]
>    halfstrip (hs)		R+ X [0, b]
>    strip (s)			R X [0, b]
>    angled strip (as)		([0, a] X R+) U (R+ X [0, b])
>    quadrant (q)		R+ X R+
>    halfplane (hp)		R X R+
>    three-quarter plane (tp)	(tp)(R X R+) U (R+ X R)
>    plane (p)			R X R

you should read the following article:

 solomon golomb, tiling with polyominoes, journal of combinatorial
    theory, volume 1, (1966), pages 280-296.

he considers all the above possibilities (except for the three-quarter
plane), as well as the possibility that the polyomino tiles a larger
copy of itself.  from his examples, it's clear that he allows the use
of mirror images; however, the implications do not change under this
interpretation.  here's the diagram of implications he gives:


                            rectangle

                          /     |
                         /      |
                        /       v
                       /
                      /     half strip
                     /
                    /           |
                   /            |
                  /             v
                 /
               \/_          bent strip

            itself              |
                                |
              \                 v
               \
                \           quadrant & strip
                 \
                  \        /              \
                   \      /                \
                   _\/  \/_                _\/

                   quadrant                 strip
                 
                          \               /
                           \             /
                           _\/         \/_

                              half plane

                                  |
                                  |
                                  v

                                plane

                                  |
                                  |
                                  v

                               nothing

most of the implications are immediate (e.g. quadrant ==> half plane,
since the half plane may be tiled with two quadrants).  the only
non-obvious implications are:     itself ==> quadrant,  and
                              bent strip ==> (quadrant &) strip.
i will leave these to the reader to prove.

if we add the "three-quarter plane" we have the implications:

          quadrant  ==>  three-quarter plane  ==>  plane

the first implication is immediate, but i need the axiom of choice
to deduce the second.  (if anyone can prove the second without the
axiom of choice, please let me and sci.math know.)  as a hint,
try to prove that if a polyomino can cover an N-by-N square for all N
(no overlap, and pieces may hang over the edges of the square), then
it tiles the plane.  i don't know if the implication 

              three-quarter plane  ==??==>  half plane 

is valid, but there are a number of potential implications that
haven't yet been ruled out, even though there's no apparent reason
they should hold.  (e.g.  itself  ==??==> rectangle)

[many lines deleted for brevity]

>    I have been unable to find polyominoes in sets other than these
>    five, or to fill in the ? in the above table.  There may be general

golomb classifies all (except the infamous y hexomino) polyominoes of
order <= 6, and finds that many of these sets are unrepresented.

>    implications I have not worked out (e.g., does a polyomino tiling
>    the half strip necessarily tile a rectangle?).  It would make an
>    interesting study.

indeed.