Constraint programming to solve maximal density still life

Geoffrey Chu; Karen Elizabeth Petrie; Neil Yorke-Smith

doi:10.1007/978-1-84996-217-9_10

Constraint programming to solve maximal density still life

Geoffrey Chu, Karen Elizabeth Petrie, Neil Yorke-Smith

Research output: Chapter in Book/Report/Conference proceeding › Chapter

2 Citations (Scopus)

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 language	English
Title of host publication	Game of Life Cellular Automata
Editors	Andrew Adamatzky
Place of Publication	London
Publisher	Springer
Pages	167-175
Number of pages	9
ISBN (Electronic)	9781849962179
ISBN (Print)	9781849962162
DOIs	https://doi.org/10.1007/978-1-84996-217-9_10
Publication status	Published - 2010

Access to Document

10.1007/978-1-84996-217-9_10

Cite this

@inbook{fa607cbbb61847fc86aa93df65c81cbd,

title = "Constraint programming to solve maximal density still life",

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.",

author = "Geoffrey Chu and Petrie, {Karen Elizabeth} and Neil Yorke-Smith",

year = "2010",

doi = "10.1007/978-1-84996-217-9_10",

language = "English",

isbn = "9781849962162",

pages = "167--175",

editor = "Andrew Adamatzky",

booktitle = "Game of Life Cellular Automata",

publisher = "Springer ",

}

TY - CHAP

T1 - Constraint programming to solve maximal density still life

AU - Chu, Geoffrey

AU - Petrie, Karen Elizabeth

AU - Yorke-Smith, Neil

PY - 2010

Y1 - 2010

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

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

UR - http://www.scopus.com/inward/record.url?scp=84895261010&partnerID=8YFLogxK

U2 - 10.1007/978-1-84996-217-9_10

DO - 10.1007/978-1-84996-217-9_10

M3 - Chapter

AN - SCOPUS:84895261010

SN - 9781849962162

SP - 167

EP - 175

BT - Game of Life Cellular Automata

A2 - Adamatzky, Andrew

PB - Springer

CY - London

ER -

Constraint programming to solve maximal density still life

Abstract

Access to Document

Other files and links

Fingerprint

Cite this