Matthew Cook 20 Sep 98

I have finally determined that it does not take exponential time to
distinguish a still-life from a pseudo-still-life, for the standard
definition where the islands must be partitionable into exactly two
stable proper subsets.

It takes only linear time, plus O(n^2) where n is the number of
instances of the following rare type of pathology:

                         . O O . O O .
                         . O O . O O .
                         . . . . . . .
                         O . O O O . O
                         O O . O . O O

                            "Lock"

The algorithm is a bit complicated, though:


1. Find the Islands.

2. Build Infrastructure:  Bridges, Aquaducts, and Locks.

   Build bridges on cells that touch two islands, at least one of
   which at three points:

       A A A     A A .    A . B
       . | .     A \ .    . / .    etc.
       B B B     . . B    . A A

   A bridge cell acts like a land cell, connecting islands as one,
   and separating water cells.

   Build aquaducts on cells having 4 live neighbors, that touch
   3 or 4 islands:

       A . B     A A .    A . A    A . B
       . + .     . + .    . + .    . + .
       C . D     B . C    B . C    C . A

   An aquaduct connects the water on opposite sides of it, without
   connecting the crossing canals to each other, or connecting any
   islands.  (In the second case shown, one of the canals dead-ends
   after passing through the aquaduct.)

   Build locks on cells touching three islands, one of which at
   three points:

       A . B
       .} {. 
       C C C

   A lock consists of two gates, only one of which may be open at
   a time.  A closed gate connects its two islands like a bridge,
   while an open gate connects its two waterways.
   Note how a lock necessarily disconnects the A.C canal from the
   B.C canal (when labeled as shown), since at least one of the
   gates must be closed.

3. Find the Seas.

   A sea is a connected body of water (empty cells), given that the
   infrastructure has been installed, and all locks have both gates
   closed.
   (A sea that borders only one island is really a lake and can be
   ignored.)

   Now we can begin to see what the main idea is for this algorithm:
   If we can find a cycle through the seas, then if we draw this
   cycle, and do an even-odd fill of it, then we can put islands
   from the filled region into one set, and islands from the unfilled
   region into the other set, and both sets will be stable.

   (A lock is not allowed to change its state as you draw the cycle!)

   Furthermore, if there is a partitioning of the islands into two
   stable sets, then we can close lock gates between islands of the
   same set, leaving the rest of the gates open, and we will see
   that if we color seas touching islands from both sets red,
   then there must be a cycle through the red seas (possibly several).

   So the possibility of partitioning the islands into two stable
   sets is equivalent to the possibility of finding a cycle through
   the seas.
   From now on, we will only talk about finding a cycle through the
   seas, leaving talk of sets of islands to the canaries.

   If any sea is not simply connected (this can be determined by
   refusing to make "connections" as one "grows" the sea), then there
   is a trivial cycle within that sea alone, and we are done.
   The one exception is the outermost sea, so one should in effect
   consider all of the outermost sea cells to be like one single sea
   cell when growing that sea.

4. List the locks in terms of their seas.
<<verbose mode off>>

5. Convert to form where each sea touches only two locks.

6. Find a sea that meets both locks at a side, call it X.
   (There must be such a sea by the pigeonhole principle.)

7. Remove X.

8. Find a cut edge (if none, go to step 6), call it Y.

9. Call the two remaining components com1 and com2.
   Put X back in.
   Short-circuit com2 by deleting it and connecting X and Y.

10. Recursion: Is there a cycle in this smaller set of seas?
    If not, any cycle must be in com2 alone:
        Throw out com1 and go to step 6.
    If so, does it use the short-circuit?
    If it doesn't use the short, we are done.

    So we found a cycle through com1 that uses the short.

11. Put com2 back in and delete com1.
    (X and Y are still shorted to each other.)

12. Recursion: Is there a cycle in this smaller set of seas?
    If not, any cycle must be in com1 alone:
        Throw out com2 and go to step 6.
    If so, does it use the short-circuit?
    If it doesn't use the short, we are done.

    So we found a cycle through com2 that uses the short.

13. Merge the cycles found in steps 10 and 12 to make one long
    cycle that doesn't cross the short.

    We are done.