Reversing Conway's Game of Life

A few days ago the YouTube channel Alpha Phoenix uploaded a video about running Conway's Game of Life backwards. It's a great video, but the solution Alpha Phoenix used was based on using a constraint solver and it inspired me to try implementing my own solver for reverse Game of Life to see how a backtracking search would perform in comparison. So I wrote a backtracking search solution in Julia. It runs pretty quickly on small inputs but gets exponentially slower for larger inputs.

Here is an example of one of my test cases:

The largest test I did so far was a rasterization of the text REVERSE. My implementation only managed to run it 3 steps backwards and got stuck on the 4th step:

The problem with my solutions is that they grow in size, each predecessor state requires searching over more pixels which slows down the search a lot. For the REVERSE example the 3rd step took 15 seconds but the 4th step did not complete: I stopped it after more than 4 hours.

Update: I rewrote and optimized my search function and finally the 4th iteration of the REVERSE example finished without a solution after 15 hours. If my code is correct the 3rd iteration shown above is a so-called Garden of Eden, that is, a game state which has no predecessors.

Julia Code

Anyway here is my Julia code if you want to try it for yourself: life.jl

This script expects a file named big_reverse.txt in the working directory containing a text representation of a Game of Life board where # denotes a living cell (all other non-newline characters are treated as dead). For example:

    ..................................................
    .#####  ###### #    # ###### #####   ####  ######.
    .#    # #      #    # #      #    # #      #     .
    .#    # #####  #    # #####  #    #  ####  ##### .
    .#####  #      #    # #      #####       # #     .
    .#   #  #       #  #  #      #   #  #    # #     .
    .#    # ######   ##   ###### #    #  ####  ######.
    ..................................................

C Code

Link to C version: life.c