A complete solution to the Maximum Density Still Life Problem

Abstract

The Maximum Density Still Life Problem (CSPLib prob032) is to find the maximum number of live cells that can fit in an n×n region of an infinite board, so that the board is stable under the rules of Conway's Game of Life. It is considered a very difficult problem and has a raw search space of O(2n2). Previous state of the art methods could only solve up to n=20. We give a powerful reformulation of the problem into one of minimizing "wastage" instead of maximizing the number of live cells. This reformulation allows us to compute very strong upper bounds on the number of live cells, which dramatically reduces the search space. It also gives us significant insights into the nature of the proble..