|
|
|
Toni Mancini, Davide Micaletto, Fabio Patrizi, Marco Cadoli
Dipartimento di Informatica e Sistemistica
Università di Roma "La Sapienza"
via Salaria 113, I-00198 Roma, Italy
Appeared in
Constraints, 13(4), pages 407-436, 2008.
Web appendix
[CSPLib #] Go to the CSPLib page for this problem Life is played on a squared board, considered
to extend to infinity in all directions. Each square of the board is a cell, which at any time during the game is either alive or dead. A cell has eight neighbours. The configuration of live and dead cells at time t leads to a new configuration
at time t + 1 according to the rules of the game:
- If a cell has exactly three living neighbours at time t, it is alive at time t + 1;
- If a cell has exactly two living neighbours at time t, it is in the same state at time t + 1 as it was at time t;
- Otherwise, the cell is dead at time t + 1.
A stable pattern, or still-life, is not changed by these rules. Hence, every cell that has exactly three live neighbours is alive, and every cell that has fewer than two or more than three live neighbours is dead. (An empty board is a still-life, for instance.) Given a positive integer n, the problem amounts to find the densest possible still-life pattern, i.e. the pattern with the largest number of live cells, that can be fitted into an n by n section of the board, with all the rest of the board dead.
- n, the size of the board section where the still-pattern appears
The set of all possible assignments of 0s (dead) and 1s (live) to the cells of the board section.
However, to be able to easily express constraints on "boundary" cells, we take as search space the set of 0/1 boards of size n+4 by n+4: the actual stable pattern appears in the sub-board defined by ignoring the first/last two rows/columns.Maximize the number of live cells in the sub-board defined by ignoring the first/last two rows/columns- C1: Cells in the first/last two rows/columns are all 0 (dead)
- C2: Each cell of the board (except those of the first/last row/column) that has exactly three live neighbors is alive.
Together with constraint C1, this implies that cells in the second/last-but-one row/column cannot have three live neighbors. - C3: Each live cell must have 2 or 3 live neighbors (cells of the first/last row/column may be ignored by this constraint)
Problem specifications
| Specification | OPL | DLV | LPARSE |
|---|
Warning: Undefined array key "DLV" in /var/www/html/research/webappendices/csplib2x/problemDetails.part on line 69
Warning: Undefined array key "LPARSE" in /var/www/html/research/webappendices/csplib2x/problemDetails.part on line 69
| BASE: Base specification |
| -- | -- |
| SBSO: Symmetry-breaking by selective ordering |
| -- | -- |
| SBSB: Symmetry-breaking by size-based ordering |
| -- | -- |
| AUX: Addition of auxiliary predicates |
| -- | -- |
| AUX-SBSO: Addition of auxiliary predicates plus Symmetry-breaking by selective ordering |
| -- | -- |
| AUX-SBSB: Addition of auxiliary predicates plus Symmetry-breaking by size-based ordering |
| -- | -- |
Return to the problem list
|
[This web site could never be realised without the sophisticated features of a pure text editor and the extreme power of 220V]
|
Home page