Still Life

The maximum density still life problem aims to fill a given grid with live and dead cells with the maximum number of live cells which is stable under Conways game of Life, that is each live cell has 2 or 3 live neighbours, and each dead cell does not have exactly 3 live neighbours. See e.g. Neil Yorke-Smith's page on this

Our method is reported here.

The results here were obtained using a strong mathematical proof of maximum density, and some very sophisticated lookahead search.

An optimal 69x69 maximal density still life

Note that the raw search space for 69x69 is 2^4761 or

Newer Results

We have now shown that all maximum-density still life problems can be solved in constant time. This requires strong upper bounds, and a very powerful search construction, that allows us to find periodic solutions to the problem. This is a fairly surprising result given when we started this the best known solution was size 20 which required days of computer time to determine. Zip file contains optimal solutions for sizes up to 246 and a C++ file to verify them. The largest solution for each size mod 54 is periodic. The results are reported here: