The challenge: Write a program which implements John Conway's Game of Life cellular automaton - in reverse!
The rules of life are explained on the Wiki page, in this question from last month, and will probably be familiar to any person crazy enough to take the challenge.
In this week's challenge, the goal is not to apply the rules of Life to universe state A in order to find the following state B. Instead, the goal, given universe state B, is to calculate a previous universe state A, such that the rules of Life applied to A will reproduce B in one iteration.
As in the August challenge, the input is a grid of 40 rows and 80 columns, with dead cells represented with '.' and live cells represented by 'X'
The program should either:
- terminate with an error, if no previous universe state A may be iterated to produce B
- output one possible previous universe state A which may be iterated to produce B
Warning: I suspect this is computationally intractable, but I'm willing to be proved wrong! I will accept any solution demonstrably terminating in one year or less.