Realizing still life constraints as a planar tiling

For general discussion about Conway's Game of Life.
User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Realizing still life constraints as a planar tiling

Post by pcallahan » May 4th, 2016, 7:26 pm

A question that has been in the back of my mind for years is whether there is a "nice" set of tiles such that planar tilings from this set correspond 1-1 to still life patterns. The issue that caused me the most trouble was handling the diagonal adjacency of the Moore neighborhood, though it really should not have (there are known results for representing the Moore neighborhood with tiles).

After playing around with this, I came up with an approach that is fairly simple and allows for flip symmetry and octagonal rotations. The picture (attached) should make this self-explanatory.
Screen Shot 2016-05-06 at 4.13.07 PM.png
Screen Shot 2016-05-06 at 4.13.07 PM.png (95 KiB) Viewed 27046 times
Live cells are represented as blue tiles with 2 or 3 teeth. Empty cells are represented as white tiles with 0, 1, 2, 4, 5, or 6 teeth (note that no still life can have a cell with 7 or 8 neighbors because of internal overcrowding). Diagonal neighborhood constraints are propagated by a set of six distinct tiles that fill in the space between blue and white tiles. Empty sections of the grid are simply the truncated square tiling (white octagons and gray squares). I haven't counted the distinct tiles. There are quite a few 4-5-6 white tiles, but these (I believe) can be decomposed into half tiles with either 2 or 3 neighbors.

I am not 100% certain that only valid tilings are possible. That is, I haven't proved it, and a rigorous proof looks like it would require a case analysis. I don't see how to cover the plane without the diagonal parts, and as long as they are there, neighbor relations are preserved. It would also be possible to make some of the boundaries more distinctive (while preserving symmetry) and that would at least make the proof easier.

This solution turned out to be so simple that I now wonder if it is original. Does anyone know of similar tilings?
Last edited by pcallahan on May 6th, 2016, 7:24 pm, edited 2 times in total.

NotLiving
Posts: 19
Joined: May 3rd, 2016, 3:47 pm

Re: Realizing still life constraints as a planar tiling

Post by NotLiving » May 5th, 2016, 9:25 am

Bravo.

One obvious issue is that your "no-neighbors" corner piece (the diamond) tiles the plane on its own - but that's simple to fix.

I suspect that you can actually go for a straight "square" tiling from this. My thought process:

First, shift from using the octagons for the cells and the diamonds for the adjacencies to vice versa. In particular, have each octagonal adjacency completely ignore the adjacent adjacencies, but propagate out to adjacent cells the number of adjacent live cells. So each diagonal has 3 teeth that can be present or not present - one for if the adjacent cell is live, and 2 indicating the live count of the 3 adjacent cells, with the opposite one counted for 2. (You're double-counting the diagonally adjacent cells, so you need to double-count the straight-out one as well.)

Then the cell tiles just have all possible (even, as odd isn't possible) sums of 0-16 "adjacent half-cells", with the tile broadcasting dead or alive as appropriate.

Then just rotate the entire thing 45 degrees.

Amusingly, this can be then expressed as Wang tiles:

(Wang tiles: a set of square tiles that can be translated but not reflected and rotated, and must be placed together such that adjacent tiles must match colors - or rather, "colors", as you can also express the constraints purely geometrically.)

Code: Select all

Name | N S E W colors
Adj 0 0 0 0 | A a A a
Adj 0 0 0 1 | B b C e
Adj 0 0 1 0 | B b E c
Adj 0 0 1 1 | C c G g
Adj 0 1 0 0 | C e B b
Adj 0 1 0 1 | D f D f
Adj 0 1 1 0 | D f F d
Adj 0 1 1 1 | E g H h
Adj 1 0 0 0 | E c B b
Adj 1 0 0 1 | F d D f
Adj 1 0 1 0 | F d F d
Adj 1 0 1 1 | G e H h
Adj 1 1 0 0 | G g C c
Adj 1 1 0 1 | H h E g
Adj 1 1 1 0 | H h G e
Adj 1 1 1 1 | I i I i
Dead 0 | a A a A
Dead 1 | a A a C
Dead 1 | a A b B
Dead 1 | a A c A
Dead 1 | a B b A
Dead 1 | a C a A
Dead 1 | b A a B
Dead 1 | b B a A
Dead 1 | c A a A
Dead 2 | a A a E
Dead 2 | a A b D
Dead 2 | a A c C
Dead 2 | a A d B
Dead 2 | a A e A
Dead 2 | a B b C
Dead 2 | a B c B
Dead 2 | a B d A
Dead 2 | a C a C
Dead 2 | a C b B
Dead 2 | a C c A
Dead 2 | a D b A
Dead 2 | a E a A
Dead 2 | b A a D
Dead 2 | b A b C
Dead 2 | b A c B
Dead 2 | b B a C
Dead 2 | b B b B
Dead 2 | b B c A
Dead 2 | b C a B
Dead 2 | b C b A
Dead 2 | b D a A
Dead 2 | c A a C
Dead 2 | c A b B
Dead 2 | c A c A
Dead 2 | c B a B
Dead 2 | c B b A
Dead 2 | c C a A
Dead 2 | d A a B
Dead 2 | d B a A
Dead 2 | e A a A
Dead 4 | a A e E
Dead 4 | a B d E
Dead 4 | a B e D
Dead 4 | a C c E
Dead 4 | a C d D
Dead 4 | a C e C
Dead 4 | a D b E
Dead 4 | a D c D
Dead 4 | a D d C
Dead 4 | a D e B
Dead 4 | a E a E
Dead 4 | a E b D
Dead 4 | a E c C
Dead 4 | a E d B
Dead 4 | a E e A
Dead 4 | b A d E
Dead 4 | b A e D
Dead 4 | b B c E
Dead 4 | b B d D
Dead 4 | b B e C
Dead 4 | b C b E
Dead 4 | b C c D
Dead 4 | b C d C
Dead 4 | b C e B
Dead 4 | b D a E
Dead 4 | b D b D
Dead 4 | b D c C
Dead 4 | b D d B
Dead 4 | b D e A
Dead 4 | b E a D
Dead 4 | b E b C
Dead 4 | b E c B
Dead 4 | b E d A
Dead 4 | c A c E
Dead 4 | c A d D
Dead 4 | c A e C
Dead 4 | c B b E
Dead 4 | c B c D
Dead 4 | c B d C
Dead 4 | c B e B
Dead 4 | c C a E
Dead 4 | c C b D
Dead 4 | c C c C
Dead 4 | c C d B
Dead 4 | c C e A
Dead 4 | c D a D
Dead 4 | c D b C
Dead 4 | c D c B
Dead 4 | c D d A
Dead 4 | c E a C
Dead 4 | c E b B
Dead 4 | c E c A
Dead 4 | d A b E
Dead 4 | d A c D
Dead 4 | d A d C
Dead 4 | d A e B
Dead 4 | d B a E
Dead 4 | d B b D
Dead 4 | d B c C
Dead 4 | d B d B
Dead 4 | d B e A
Dead 4 | d C a D
Dead 4 | d C b C
Dead 4 | d C c B
Dead 4 | d C d A
Dead 4 | d D a C
Dead 4 | d D b B
Dead 4 | d D c A
Dead 4 | d E a B
Dead 4 | d E b A
Dead 4 | e A a E
Dead 4 | e A b D
Dead 4 | e A c C
Dead 4 | e A d B
Dead 4 | e A e A
Dead 4 | e B a D
Dead 4 | e B b C
Dead 4 | e B c B
Dead 4 | e B d A
Dead 4 | e C a C
Dead 4 | e C b B
Dead 4 | e C c A
Dead 4 | e D a B
Dead 4 | e D b A
Dead 4 | e E a A
Dead 5 | a C e E
Dead 5 | a D d E
Dead 5 | a D e D
Dead 5 | a E c E
Dead 5 | a E d D
Dead 5 | a E e C
Dead 5 | b B e E
Dead 5 | b C d E
Dead 5 | b C e D
Dead 5 | b D c E
Dead 5 | b D d D
Dead 5 | b D e C
Dead 5 | b E b E
Dead 5 | b E c D
Dead 5 | b E d C
Dead 5 | b E e B
Dead 5 | c A e E
Dead 5 | c B d E
Dead 5 | c B e D
Dead 5 | c C c E
Dead 5 | c C d D
Dead 5 | c C e C
Dead 5 | c D b E
Dead 5 | c D c D
Dead 5 | c D d C
Dead 5 | c D e B
Dead 5 | c E a E
Dead 5 | c E b D
Dead 5 | c E c C
Dead 5 | c E d B
Dead 5 | c E e A
Dead 5 | d A d E
Dead 5 | d A e D
Dead 5 | d B c E
Dead 5 | d B d D
Dead 5 | d B e C
Dead 5 | d C b E
Dead 5 | d C c D
Dead 5 | d C d C
Dead 5 | d C e B
Dead 5 | d D a E
Dead 5 | d D b D
Dead 5 | d D c C
Dead 5 | d D d B
Dead 5 | d D e A
Dead 5 | d E a D
Dead 5 | d E b C
Dead 5 | d E c B
Dead 5 | d E d A
Dead 5 | e A c E
Dead 5 | e A d D
Dead 5 | e A e C
Dead 5 | e B b E
Dead 5 | e B c D
Dead 5 | e B d C
Dead 5 | e B e B
Dead 5 | e C a E
Dead 5 | e C b D
Dead 5 | e C c C
Dead 5 | e C d B
Dead 5 | e C e A
Dead 5 | e D a D
Dead 5 | e D b C
Dead 5 | e D c B
Dead 5 | e D d A
Dead 5 | e E a C
Dead 5 | e E b B
Dead 5 | e E c A
Dead 6 | a E e E
Dead 6 | b D e E
Dead 6 | b E d E
Dead 6 | b E e D
Dead 6 | c C e E
Dead 6 | c D d E
Dead 6 | c D e D
Dead 6 | c E c E
Dead 6 | c E d D
Dead 6 | c E e C
Dead 6 | d B e E
Dead 6 | d C d E
Dead 6 | d C e D
Dead 6 | d D c E
Dead 6 | d D d D
Dead 6 | d D e C
Dead 6 | d E b E
Dead 6 | d E c D
Dead 6 | d E d C
Dead 6 | d E e B
Dead 6 | e A e E
Dead 6 | e B d E
Dead 6 | e B e D
Dead 6 | e C c E
Dead 6 | e C d D
Dead 6 | e C e C
Dead 6 | e D b E
Dead 6 | e D c D
Dead 6 | e D d C
Dead 6 | e D e B
Dead 6 | e E a E
Dead 6 | e E b D
Dead 6 | e E c C
Dead 6 | e E d B
Dead 6 | e E e A
Dead 7 | c E e E
Dead 7 | d D e E
Dead 7 | d E d E
Dead 7 | d E e D
Dead 7 | e C e E
Dead 7 | e D d E
Dead 7 | e D e D
Dead 7 | e E c E
Dead 7 | e E d D
Dead 7 | e E e C
Dead 8 | e E e E
Live 2 | e E e I
Live 2 | e E f H
Live 2 | e E g G
Live 2 | e E h F
Live 2 | e E i E
Live 2 | e F f G
Live 2 | e F g F
Live 2 | e F h E
Live 2 | e G e G
Live 2 | e G f F
Live 2 | e G g E
Live 2 | e H f E
Live 2 | e I e E
Live 2 | f E e H
Live 2 | f E f G
Live 2 | f E g F
Live 2 | f F e G
Live 2 | f F f F
Live 2 | f F g E
Live 2 | f G e F
Live 2 | f G f E
Live 2 | f H e E
Live 2 | g E e G
Live 2 | g E f F
Live 2 | g E g E
Live 2 | g F e F
Live 2 | g F f E
Live 2 | g G e E
Live 2 | h E e F
Live 2 | h F e E
Live 2 | i E e E
Live 3 | e E g I
Live 3 | e E h H
Live 3 | e E i G
Live 3 | e F f I
Live 3 | e F g H
Live 3 | e F h G
Live 3 | e F i F
Live 3 | e G e I
Live 3 | e G f H
Live 3 | e G g G
Live 3 | e G h F
Live 3 | e G i E
Live 3 | e H f G
Live 3 | e H g F
Live 3 | e H h E
Live 3 | e I e G
Live 3 | e I f F
Live 3 | e I g E
Live 3 | f E f I
Live 3 | f E g H
Live 3 | f E h G
Live 3 | f E i F
Live 3 | f F e I
Live 3 | f F f H
Live 3 | f F g G
Live 3 | f F h F
Live 3 | f F i E
Live 3 | f G e H
Live 3 | f G f G
Live 3 | f G g F
Live 3 | f G h E
Live 3 | f H e G
Live 3 | f H f F
Live 3 | f H g E
Live 3 | f I e F
Live 3 | f I f E
Live 3 | g E e I
Live 3 | g E f H
Live 3 | g E g G
Live 3 | g E h F
Live 3 | g E i E
Live 3 | g F e H
Live 3 | g F f G
Live 3 | g F g F
Live 3 | g F h E
Live 3 | g G e G
Live 3 | g G f F
Live 3 | g G g E
Live 3 | g H e F
Live 3 | g H f E
Live 3 | g I e E
Live 3 | h E e H
Live 3 | h E f G
Live 3 | h E g F
Live 3 | h F e G
Live 3 | h F f F
Live 3 | h F g E
Live 3 | h G e F
Live 3 | h G f E
Live 3 | h H e E
Live 3 | i E e G
Live 3 | i E f F
Live 3 | i E g E
Live 3 | i F e F
Live 3 | i F f E
Live 3 | i G e E
Well... Assuming I didn't mess up, anyways.

You can easily see here the trivial no-cells-live tiling, as well as a bunch of other tilings. A diagonal row of cells, for instance is represented by "Adj 1 1 0 0 | G c C c" alternating with "Live 2 | g G e E", with "Dead 1 | a A a C", "Dead 1 | a A c A", "Adj 0 0 0 1 | B b C e", and "Adj 0 0 1 0 | B b E c" filling out the two adjacent rows (and different Dead 1s in the diagonal-opposite cells too) to return to the no-cells-live tiling otherwise.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 5th, 2016, 9:54 am

Yeah, I overlooked the fact that the square tiles would tile the plane on their own. You could add a slight convexity/concavity to matching sides, though I am reluctant to make the tiles any more complex. I am more inclined just to rule out a degenerate case by fiat. (I have also thought about making the live tiles toothed circles instead of 16-gons, but then the white teeth would need a slight curvature to match.)

I will look at your solution carefully, but I agree there should be some Wang tile formulation. My interest in making this geometrical was with the thought of cutting them out if I ever get a chance. I was very excited when I realized that neighborhoods could be given octagonal symmetry. If I have enumerated this correctly, there are just 32 neighborhood tiles (excluding 7 and 8 neighbors) up to symmetry. The 4, 5, 6- tiles can be decomposed further by splitting into halves with 2 or 3 teeth.

Code: Select all

index center #neighbors #neighborhood
 1 0 0 0-0-0-0-0-0-0-0
 2 0 1 0-0-0-0-0-0-0-1
 3 0 2 0-0-0-0-0-0-1-1
 4 0 2 0-0-0-0-0-1-0-1
 5 0 2 0-0-0-0-1-0-0-1
 6 0 2 0-0-0-1-0-0-0-1
 7 0 4 0-0-0-0-1-1-1-1
 8 0 4 0-0-0-1-0-1-1-1
 9 0 4 0-0-0-1-1-0-1-1
10 0 4 0-0-1-0-0-1-1-1
11 0 4 0-0-1-0-1-0-1-1
12 0 4 0-0-1-0-1-1-0-1
13 0 4 0-0-1-1-0-0-1-1
14 0 4 0-1-0-1-0-1-0-1
15 0 5 0-0-0-1-1-1-1-1
16 0 5 0-0-1-0-1-1-1-1
17 0 5 0-0-1-1-0-1-1-1
18 0 5 0-1-0-1-0-1-1-1
19 0 5 0-1-0-1-1-0-1-1
20 0 6 0-0-1-1-1-1-1-1
21 0 6 0-1-0-1-1-1-1-1
22 0 6 0-1-1-0-1-1-1-1
23 0 6 0-1-1-1-0-1-1-1
24 1 2 0-0-0-0-0-0-1-1
25 1 2 0-0-0-0-0-1-0-1
26 1 2 0-0-0-0-1-0-0-1
27 1 2 0-0-0-1-0-0-0-1
28 1 3 0-0-0-0-0-1-1-1
29 1 3 0-0-0-0-1-0-1-1
30 1 3 0-0-0-1-0-0-1-1
31 1 3 0-0-0-1-0-1-0-1
32 1 3 0-0-1-0-0-1-0-1

NotLiving
Posts: 19
Joined: May 3rd, 2016, 3:47 pm

Re: Realizing still life constraints as a planar tiling

Post by NotLiving » May 5th, 2016, 10:47 am

Also there's only 6 corner tiles, which is nice. (0 live, 1 live, 2 adjacent live, 2 diagonal live, 3 live, 4 live).

So yeah, you should be able to do it with <= 38 unique tiles.

As you say, splitting the 4 / 5 / 6 into 2/3 half tiles would reduce it further:

Code: Select all

index center #neighbors #neighborhood
1 0 0 0-0-0-0-0-0-0-0
2 0 1 0-0-0-0-0-0-0-1
3 0 2 0-0-0-0-0-0-1-1
4 0 2 0-0-0-0-0-1-0-1
5 0 2 0-0-0-0-1-0-0-1
6 0 2 0-0-0-1-0-0-0-1
7 1 2 0-0-0-0-0-0-1-1
8 1 2 0-0-0-0-0-1-0-1
9 1 2 0-0-0-0-1-0-0-1
10 1 2 0-0-0-1-0-0-0-1
11 1 3 0-0-0-0-0-1-1-1
12 1 3 0-0-0-0-1-0-1-1
13 1 3 0-0-0-1-0-0-1-1
14 1 3 0-0-0-1-0-1-0-1
15 1 3 0-0-1-0-0-1-0-1
+ 5 half tiles of 2 and 3, I think.

So overall "only" 26 tiles, including the corner ones.

You may be able to split the 2-living and 2-dead cases into 2 subtiles as well - 0010 and 0001, cutting it down to 22 tiles. Need to additionally make sure that none of those split cases work with any other tiles than the ones they are supposed to, though.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 5th, 2016, 12:49 pm

I think you need all four 2-neighbor half-tiles with flip symmetry: 0011, 1001, 0110, 0101.
Then there are two 3-neighbor half tiles as you probably noticed. 0111 and 1011.

I assumed a linear boundary of the right length would suffice to match up just these, but I can't rule out shenanigans in my head (like tiling a half plane with one linear boundary and reflecting it over--I don't think so though).

So that is 6 for a total of 27.

NotLiving
Posts: 19
Joined: May 3rd, 2016, 3:47 pm

Re: Realizing still life constraints as a planar tiling

Post by NotLiving » May 6th, 2016, 12:32 pm

Whoops, you're right.

And you'll have to be careful to ensure that the corner tiles ensure the mirrored configuration cannot happen. I think that's true as-is, though.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 6th, 2016, 3:28 pm

Another problem in my attempt to keep the shapes as simple as possible. If a white tooth meets a blue tile as I have here, then it could also be a blue tooth meeting a white tile.
Screen Shot 2016-05-06 at 12.20.40 PM.png
Screen Shot 2016-05-06 at 12.20.40 PM.png (5.89 KiB) Viewed 27061 times
This is a problem if the blue tile really only has one blue tile as a neighbor but can be placed as if it had two by touching the face of a white tile.

This is fixable by making sure the contour of a blue-white coupling is different from a blue-blue coupling, since gray tiles enforce the contours. Originally I had something like this and mistakenly believed I could simplify it away. So it's a work in progress, but I believe the basic idea is correct.

Update: I fixed the original image by making the blue teeth wider. This address the specific issue. Let me know if anyone sees other potential for tilings that aren't still lifes (explicitly ruling out the tiling by all gray squares).

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 12th, 2016, 2:24 am

After some experimentation, I realized that overcrowded neighborhoods (4 or more around an empty cell) can be reduced to 3 tiles allowing for flips. Two are quarter-octagons that have one or two teeth (so you are guaranteed to have at least 4 teeth total) and the other is a half-octagon with two adjacent teeth to one side, to handle some cases in which there is no way to cover the octagon without a gap of two teeth. This gives 24 tiles:
Screen Shot 2016-05-11 at 11.05.16 PM.png
Screen Shot 2016-05-11 at 11.05.16 PM.png (54.27 KiB) Viewed 27006 times
I ran lifesrc to enumerate still life patterns until I found one that illustrated all the tiles. Here it is:
Screen Shot 2016-05-11 at 11.02.45 PM.png
Screen Shot 2016-05-11 at 11.02.45 PM.png (170.9 KiB) Viewed 27006 times
Of course, I am not really sure there are no tilings besides ones that represent still life patterns and the degenerate case of all gray squares. The quarter and half octagons can be placed adjacent in many wrong ways, but I don't see a way to fill the gaps. I am guessing that any problems are fixable. I am also fairly certain you can split up some of the other neighborhoods into smaller tile sets, but there isn't as much benefit as with >=4 neighbors.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing still life constraints as a planar tiling

Post by calcyman » May 13th, 2016, 6:09 am

I don't know about you, but I'm feeling 22:
22-tile reduction of Paul Callahan's 24-tile set
22-tile reduction of Paul Callahan's 24-tile set
feeling-22.png (32.5 KiB) Viewed 26970 times
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing still life constraints as a planar tiling

Post by calcyman » May 13th, 2016, 6:37 am

And the blue neighbourhoods can be reduced by another three tiles, yielding a set of 19:
19-tile set imposing still-life constraints
19-tile set imposing still-life constraints
19tiles.png (27.66 KiB) Viewed 26966 times
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 13th, 2016, 9:54 am

Thanks! I will have to take a closer look. I had considered splitting the white tiles between midpoints of edges as you did, but I didn't think through it enough to make any progress.

I believe there is a 4-tile split-up of blue tiles, but it is a little ugly.

Start with two blue half-tiles (split at the line through opposite octagon vertices) with 1000 and 0100 boundaries. These combine into all cases of 2 neighbors. Then add two more blue half tiles with 1100 and 1010 boundaries. The problem is how to keep the later half tiles from combining into neighborhoods of 4. This can be done by adding a gap in the 1-neighbor half tiles that is fillable with another tile and already filled in the 2-neighbor half tiles (so they can't be paired up).

You don't actually need a new tile if you use the small square as the gap filler. Here are some examples:
Screen Shot 2016-05-13 at 6.49.54 AM.png
Screen Shot 2016-05-13 at 6.49.54 AM.png (45.62 KiB) Viewed 26946 times

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 13th, 2016, 2:24 pm

calcyman, is there any reason I'm missing that you cannot reduce your 6 blue tile set to 5 by splitting up the 2-neighborhoods like this?
Screen Shot 2016-05-13 at 11.23.13 AM.png
Screen Shot 2016-05-13 at 11.23.13 AM.png (6.12 KiB) Viewed 26917 times

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: Realizing still life constraints as a planar tiling

Post by Kazyan » May 13th, 2016, 3:11 pm

If I'm not misinterpreting the problem, the white octagonal set could be reduced to two tiles, by dividing up each octagon into wedges like this. One tile would be a toothed wedge and another would be an untoothed wedge.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
biggiemac
Posts: 515
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: Realizing still life constraints as a planar tiling

Post by biggiemac » May 13th, 2016, 3:40 pm

It's necessary that any possible octagon made from the white tiles not be "born" in the next generation if the tiling is viewed as a still life. In pcallahan's original set, the full octagons span the cases with 2 or fewer neighbors, and the smaller wedges are designed to only permit assembly into full octagons with 4 or more neighbors. Simply using wedges would allow 3-neighbored white cells, which would no longer satisfy the problem statement.

It took me a moment to reconcile this with calcyman's reductions. I see now that they are quite clever.
Physics: sophistication from simplicity.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 13th, 2016, 4:31 pm

Kazyan, as biggiemac explained, the problem is two-sided. It must (1) be possible to represent any still life as a planar tiling with your tile set (which your solution would do), and (2)any possible tiling should correspond to a still life. There may be multiple tilings that represent the same still life, because there are multiple ways to construct the same neighborhoods once we start splitting up tiles. However, the tiles should not admit the construction of invalid neighborhoods (empty cells with 3 neighbors or live cells with 0, 1, 4, 5, 6, 7, or 8 neighbors).

To handle the case of tiling the entire plane with the gray square, I would just define that as another representation of the empty still life, rule it out, or require the placement of at least one tile other than the gray square.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 13th, 2016, 4:57 pm

calcyman: there is one problem I see with the axis-parallel splits you used. You can get infinite linear boundaries like this and slide entire sections of the tiling.
Screen Shot 2016-05-13 at 1.52.57 PM.png
Screen Shot 2016-05-13 at 1.52.57 PM.png (7.51 KiB) Viewed 26881 times
I'm divided on whether this is a bug or a feature, because I think you will still get a valid still life as long as you realign the octagons to the nearest boundary.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing still life constraints as a planar tiling

Post by calcyman » May 13th, 2016, 5:43 pm

pcallahan wrote:calcyman: there is one problem I see with the axis-parallel splits you used. You can get infinite linear boundaries like this and slide entire sections of the tiling.
Screen Shot 2016-05-13 at 1.52.57 PM.png
I'm divided on whether this is a bug or a feature, because I think you will still get a valid still life as long as you realign the octagons to the nearest boundary.
I have a 16-tile set without this problem, coming soon...
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 14th, 2016, 9:58 am

calcyman wrote:I have a 16-tile set without this problem, coming soon...
I am eagerly awaiting it.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing still life constraints as a planar tiling

Post by calcyman » May 15th, 2016, 12:59 pm

pcallahan wrote:
calcyman wrote:I have a 16-tile set without this problem, coming soon...
I am eagerly awaiting it.
Here:
16tiles.png
16tiles.png (39.15 KiB) Viewed 26785 times
The colours are chosen so that the blue region is homotopy-equivalent to the still-life it represents.

The population of a still-life is equal to half of the number of tiles from the bottom row.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 15th, 2016, 1:38 pm

Thanks! I like the fact that no whole neighborhoods are needed.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 15th, 2016, 8:53 pm

If I'm not mistaken, the only reason to use the cross-shaped piece and not the square to connect blue neighborhoods is to preserve the color. I guess my preference is to keep the tiles simple and not worry as much about color. Actually, I like your 19-tile set (which I think is really 18 if you split the two neighborhoods as in my previous comment). The sliding boundaries don't change the set of connected still life patterns.

I am still trying to think of a reasonable way to construct these (for real) that has a good tactile feel. Paper would not be fun to work with. If I could laser-cut tinted acrylic tiles, maybe even the very elaborate shapes would be OK. But there might be something low-tech like making cookie-cutters for polymer clay.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 16th, 2016, 1:57 am

Here is an eater constructed with calcyman's tiles. I resisted the urge to reverse engineer the coordinates and just turned them into transparent pngs and pieced it together by hand in Google drive draw.
Screen Shot 2016-05-15 at 10.55.02 PM.png
Screen Shot 2016-05-15 at 10.55.02 PM.png (236.45 KiB) Viewed 26721 times

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing still life constraints as a planar tiling

Post by simsim314 » May 16th, 2016, 4:51 am

Are these relation guarantee a still life? And can any still life be represented this way?

If yes we have very nice puzzle pieces :)

One can use 3d printer or laser cutter - and order those tiles online. 3D printing is perfect for this I think.

For low tek - how about cardboard? Cookie cutter sound good as well.

EDIT Another idea is to have javascript/flash tiling game of this sort.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » May 16th, 2016, 12:43 pm

simsim314 wrote:Are these relation guarantee a still life? And can any still life be represented this way?
I am nearly certain about the second point (any still life can be represented), but the first requires proof. There is one trivial tiling of the plane by square pieces, but ignoring that one, I do not see anything else that works. The proof may take a little work, particularly, since you can build infinite non-conformant sequences of quarter-neighborhood wedges. I would start with single tiles and build neighborhoods around them and see if that takes things in any unexpected directions.

If you limit yourself to tilings that use the neighborhoods and diagonal connectors "as intended" then it is more clear that you can only get still life patterns (barring any egregious mistakes).

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing still life constraints as a planar tiling

Post by simsim314 » May 16th, 2016, 7:22 pm

I was thinking, if we want to make some sort of physical puzzle game out of these tiles - we need to make sure they can be attached properly.

I think most of the "live" cells are pretty curly - and will work well with physical puzzle, as well as the "space fillers". But what about the empty one? Even the 4 attachments are not looking so good but at least they're attached to the space fillers, yet it's a lot of pressure on quite small teeth. Less attachments are even worse, the square in the middle can hold them a bit on the inside - but on the outside they're basically falling apart, or holding on single small tooth. Can some "holding tooth" be added without adding more tiles?

Post Reply