Constraint programming to solve maximal density still life

Geoffrey Chu, Karen Elizabeth Petrie, Neil Yorke-Smith

    Research output: Chapter in Book/Report/Conference proceedingChapter

    Abstract

    The Maximum Density Still Life problem fills a finite Game of Life board with a stable pattern of cells that has as many live cells as possible. Although simple to state, this problem is computationally challenging for any but the smallest sizes of board. Especially difficult is to prove that the maximum number of live cells has been found. Various approaches have been employed. The most successful are approaches based on Constraint Programming (CP). We describe the Maximum Density Still Life problem, introduce the concept of constraint programming, give an overview on how the problem can be modelled and solved with CP, and report on best-known results for the problem.
    Original languageEnglish
    Title of host publicationGame of Life Cellular Automata
    EditorsAndrew Adamatzky
    Place of PublicationLondon
    PublisherSpringer
    Pages167-175
    Number of pages9
    ISBN (Electronic)9781849962179
    ISBN (Print)9781849962162
    DOIs
    Publication statusPublished - 2010

    Cite this

    Chu, G., Petrie, K. E., & Yorke-Smith, N. (2010). Constraint programming to solve maximal density still life. In A. Adamatzky (Ed.), Game of Life Cellular Automata (pp. 167-175). Springer . https://doi.org/10.1007/978-1-84996-217-9_10