welcome: please sign in
location: Diff for "ConnectedMaximumDensityStillLife"
Differences between revisions 2 and 3
⇤ ← Revision 2 as of 2012-11-08 10:47:58 →
Size: 1432
Editor: PatrikSchneider
Comment: Fix
← Revision 3 as of 2012-11-12 10:47:08 → ⇥
Size: 1719
Editor: PatrikSchneider
Comment: Example added
Deletions are marked like this. Additions are marked like this.
Line 15: Line 15:
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.		 criterion is dropped.)
Line 19: Line 17:
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.
Line 31: Line 26:
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.
Line 33: Line 32:

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.
Line 37: Line 40:
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).
}}}

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

Problem Peculiarities

Type: Optimization Competition: Both Complexity: NP

Notes and Updates

Author(s)

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

ASP Competition 2013: ConnectedMaximumDensityStillLife (last edited 2013-03-18 10:32:46 by GiovambattistaIanni)