title: Number of Legal Previous Moves in the Game of Life
body: <p>Given the current tick of the game in Conway's game of life (or any other cellular automation game), how can one find the number of legal previous ticks that could have been evaluated into the tick provided?</p>
  
  <p>For example, assuming the game of life can be represented as:</p>
  
  <pre><code>0 0 0 0 0 ...
  X 0 X 0 0 ...
  0 X 0 0 0 ...
  0 0 0 0 X ...
  ...
  </code></pre>
  
  <p>where <code>X</code> is "alive/on/true" and <code>0</code> is "dead/off/false", or more simply as a <code>boolean[][]</code>, how can one work out the following:</p>
  
  <pre><code>public static int numberOfValidPreviousTicks(boolean[][] current) {
      return -1; // return answer
  }
  </code></pre>
  
  <p>It is clear that one could find <em>every</em> possible previous game state from the grid size and determine if that would evaluate into the current state using the normal rules.</p>
  
  <p>However, there must be some obvious ways to speed up this process so that it is not <code>O(2^n)</code> (where n is the total number of cells in the grid).</p>
  
  <p>Caching of course could help in places but where exactly would it fit in?</p>
  
  <p>Any help would be appreciated</p>