welcome:
location: ConnectedMaximumDensityStillLife

# 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 given region of the 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 regions. The size n of the region 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.

## Cost function

The cost function is given as the number of non-living cells. This value has to be minimized (consequently maximizing the number of living cells).

## Example(s)

The first example encodes the region size three by size(3). The maximum density of a connected still life on a region 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).```

The second example encodes the region size four by size(4). The maximum density of a connected still life on a region with size four is eight live cells. Thus, a sample output is:

```lives(1,3). lives(1,4). lives(2,2). lives(2,4).
lives(3,1). lives(3,3). lives(4,1). lives(4,2).```

On the other hand, the following output does not represent a still life. In fact, this configuration brings cells outside the region to live, e.g., lives(0,2) and lives(2,0).

```lives(1,1). lives(1,2). lives(1,3). lives(1,4).
lives(2,1). lives(2,4). lives(3,1). lives(3,4).
lives(4,1). lives(4,2). lives(4,3).```

## Problem Peculiarities

Type: Optimization Competition: Both Complexity: Beyond NP