#acl EditorsGroup:read,write,admin,delete ChristianDrescher:read,write All:read = 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). }}} 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 == * Feb 8th, 2013 - Problem Description updated == Author(s) == * Author: Christian Drescher * Affiliation: NICTA, University of New South Wales, Australia