Connected Maximum-density Still Life

Problem Description

A still life is a set of connected live cells from a grid that is fixed under the transition function of John Horton Conway 1970's Game of Life: 1. Any cell with 3 neighbours becomes a live cell. 2. Any live cell with 2-3 live neighbours lives on. 3. Any live cell with <2 or >3 live neighbours dies. The Connected Maximum-density Still Life problem is the task of fitting a grid with a maximally dense still life, i.e., a maximum number of live cells. (Most work has only looked at pseudo still lifes where the connectedness criterion is dropped.) We here consider square shaped grids. The size n of the grid is provided by an instance of the predicate size/1. Cells connect horizontally, vertically, and diagonally.

If a still life exists, a witness containing live cells encoded in the predicate lives/2 has to be provided. lives(X,Y) means the grid cell with the unsigned integer coordinates X,Y (=< n) is a live cell.

Predicates

• Input: size/1

• Output: lives/2

Input format

Output format

Example(s)

Problem Peculiarities

Type: Optimization Competition: Both Complexity: NP

Notes and Updates

Author(s)

• Author: Christian Drescher
  • Affiliation: NICTA, University of New South Wales, Australia