Given the state of a square Game of Life grid, determine whether it could have evolved from any previous state, or could only have been created. That is, identify whether the state is a "Garden of Eden" state.


A square grid of states, with 1 indicating "alive" and 0 indicating "dead". You may choose any two distinguishable symbols instead of 0 and 1 if you wish.

The side length of the grid will not be zero, but may be any natural number 1 <= N <= 20.

Any or all of the cells outside the input grid may be alive at this generation, and any or all of them may have been alive in the previous generation. The universe to be considered is infinite, so there are no boundary conditions. The edges of the input are not the edges of the universe. Specifically, the grid does not wrap.

The input may be in the form of a row delimited string, or a single string. If you wish, you may take the side length or the area of the grid as an additional input (before or after the grid).

Acceptable input formats:



3 010101010


"Created" if there is no possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.

"Evolved" if there exists at least one possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.

You may use any two distinguishable strings or numbers instead of "Created" and "Evolved" if you wish.

Note that the possible previous state need not be distinct from the input. If a state has itself as the next generation, then it should be considered evolved.

Test cases

010 Evolved

0010111010 Created

The created test case is taken from Achim Flammenkamp's Game of Life Page.


Thanks to trichoplax for writing this challenge and I adopted it from here

  • 6
    \$\begingroup\$ Any complexity limitations? For an input of size m-by-n, if I test all possible 2^(m*n) initial states the program complexity will be large, but it solves the problem by just checking if the result matches the input \$\endgroup\$
    – Luis Mendo
    Mar 28, 2017 at 21:40
  • \$\begingroup\$ @Luis for the input? 20 by 20. For the program? no \$\endgroup\$ Mar 28, 2017 at 21:43
  • 2
    \$\begingroup\$ I can't be arsed to golf it, but here is an efficient implementation using an off-the shelf integer programming solver bundled in SageMath. \$\endgroup\$
    – orlp
    Mar 29, 2017 at 18:35
  • \$\begingroup\$ I assume that it doesn't matter whether or not the previous state (if existent) is a Garden of Eden state? \$\endgroup\$
    – hyper-neutrino
    Apr 16, 2017 at 8:59
  • \$\begingroup\$ @Hyper nope! Only what you get \$\endgroup\$ Apr 16, 2017 at 13:58

1 Answer 1


Java- 1254 bytes- a very poor solution

import java.util.Arrays;
public class z{
static boolean u=1>0,v=0<1;
public static void main(String[] a){
int y=a.length,x=a[0].length();Boolean[][] l=new Boolean[x][y];for(int i=0;i<a.length;i++){l[i]=m(a[i]);}
Boolean[] n=new Boolean[x*y];for(int i=0;i<n.length;i++){n[i]=v;}
while(n.length==x*y){Boolean[][] o=new Boolean[x][y];for(int i=0; i<n.length;i++){o[i%x][i/x]=n[i];}
n=p(n);o=q(o,x,y);int r=0;for(int i=0;i<x*y;i++){if(o[i%x][i/x]&&l[i%x][i/x])r++;}
public static Boolean[][] q(Boolean[][] o,int bx,int by){Boolean[][] s=new Boolean[bx][by];for(int x=0; x<bx; x++){for(int y=0;y<by;y++){
int t=0;for(int tx=-1;tx<2;tx++){for(int ty=-1;ty<2;ty++){if(ty+y<0||ty+y>by-1||tx+x<0||tx+x>bx-1)continue;if(o[tx+x][ty+y]){t++;}}}
if(t>1&&t<4){s[x][y]=u;}else{s[x][y]=v;}}}return s;}
public static Boolean[] p(Boolean[] b){boolean w=u;Boolean[] x=new Boolean[b.length];for(int i=0;i<b.length;i++){if(w&&b[i]){x[i]=u;w=u;}else if(b[i]||w){x[i]=u;w=v;}else{x[i]=v;w=v;}
}if(w){x=Arrays.copyOf(x,x.length+1);x[x.length]=u;}return x;}
public static Boolean[] m(String s){Boolean[] x=new Boolean[s.length()];for(int i=0;i<s.length();i++){x[i]=s.charAt(i)=='1';}return x;}}

It takes input via command line.

What it does

No fancy tricks here, simply a brute force solution. It goes through every possible beginning board of size X,Y and iterates it once thru the Game of Life algorithm and checks it against the input board. This takes a VERY long time, as each board of size x by y has 2^(x*y) possible combinations. It took almost 10 minutes to run a 4x5 board. Stupidly silly for something that is simpler than it is.

If it is possible that it was an evolved board, it prints "evolved.", and if it couldn't have been evolved, it prints "created.".

  • \$\begingroup\$ Nice! I agree that it's very poor for time complexity but hey, it's the only (non-plagarized) one so far so it'll probably get the bounty! Assuming orlp doesn't post the optimized one :) \$\endgroup\$
    – hyper-neutrino
    May 22, 2017 at 18:21
  • 2
    \$\begingroup\$ @HyperNeutrino "You won this round, but I have an ace up my hole." - Phillip J. Fry \$\endgroup\$
    – tuskiomi
    May 22, 2017 at 18:22
  • \$\begingroup\$ Congratulations, this solution takes the bounty! :) \$\endgroup\$
    – hyper-neutrino
    May 23, 2017 at 0:32
  • \$\begingroup\$ @HyperNeutrino I know it isn't clever, and probably not what you're looking for, and I was hoping to inspire other solutions with this easily-beatable one, but I hope it was good enough. \$\endgroup\$
    – tuskiomi
    May 23, 2017 at 1:52
  • 1
    \$\begingroup\$ also -1 not golfed (haha just kidding you got a +1 but still, trivial golfs could be made) ;) \$\endgroup\$
    – hyper-neutrino
    May 30, 2017 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.