Scorbie wrote:dvgrn wrote:Now, if we're allowed to just stick 3x3 tiles next to each other, we can still build lots of things that aren't still lifes. For example, one parity of a glider can be divided into two Still-Life Compatible 3x3s. It doesn't do any good to go to N>3, because you could still build a glider with two SLC tiles for any size N. So how do we make sure that we can build all still lifes and nothing but still lifes using this set?
Actually, it's really easy to mess up(i.e. build a non-still-life) with only tiling. If you restrict the tiles so that tiling up makes only still lifes,
i) Obviously you'll need to include the blank tile.
ii) If a tile T is in the set, then tile T surrounded by blank tiles should be stable, so tile T should be stable itself.
iii) If a tile T is in the set, then the plane tiled by T should be stable.
ii) and iii) restricts the tiles a LOT. I don't think most of the still lifes can be covered by these tiles at all. i.e. Can you build a Long^n table with sufficiently big n with NxN tiles that satisfy ii) and iii)?
EDIT: And that means you should restrict the neighbor tiles a tile can have.
I missed this posting a month ago. I was trying to address the "restricting the neighbor tiles" point in my
last three paragraphs. Another way of saying it is that every cell in the MxN rectangle containing the still life has to be centered on a 3x3 tile that's in the 51-tile Still Life Compatible set. You have to overlap the tiles as you're choosing which one to place next, so that the center of each new tile is on top of (and consistent with) an edge cell of a previously placed tile.
Offhand I don't see how to simplify the SLC any more. For example, it's clearly not sufficient that every ON cell be centered on a tile from the SLC -- we need to include tiles centered on OFF cells as well, and test OFF cells inside the MxN area as well, at least the inducting ones.
So, does all this allow for an algorithm that enumerates still lifes without going down any blind alleys? I.e., can we recursively take a free choice of tiles from the SLC that match the current set of constraints -- let's say, starting from a central tile and working outward one cell at a time in a spiral pattern until we hit MxM (for M>=N)? Will there always be at least one tile in the set that works, or will we hit contradictions at the corners sometimes and have to backtrack?
Probably this isn't the best way to do still life enumerations, of course.
De Bruijn graphs seem to be a common way to attack the problem, but I'd have to do some more reading to find out exactly how past still-life enumeration projects ensured that they came up with exhaustive lists. Have there been any enumerations done for more than 24 bits?