= 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.) 


== Predicates ==

 * '''Input''': {{{size/1}}}

 * '''Output''': {{{lives/2}}}

== Input format ==

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.


== Output format ==

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.


== Example(s) ==

The example encodes the grid size three by {{{size(3)}}}. The maximum density of a connected
still life on a grid with size three is six live cells. Thus, a sample output is:
{{{ 
lives(1,2). lives(1,3). lives(2,1). 
lives(2,3). lives(3,1). lives(3,2).
}}}

Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/still_life-sample.zip|download]]

== Problem Peculiarities ==

'''Type''': Optimization
'''Competition''': Both
'''Complexity''': Beyond NP

== Notes and Updates ==



== Author(s) ==
 * Author: Christian Drescher
  * Affiliation: NICTA, University of New South Wales, Australia