A Dual Graph Translation of a Problem in `Life'


Barbara M. Smith.
In Principles and Practice of Constraint Programming - CP 2002, ed. Pascal van Hentenryck, pp. 402-414, Springer-Verlag, LNCS 2470, 2002.

Abstract

Conway's game of Life provides interesting problems in which modelling issues in constraint programming can be explored. The problem of finding a maximum density stable pattern (`still-life') is discussed. A formulation of this problem as a constraint satisfaction problem with 0-1 variables and non-binary constraints is compared with its dual graph translation into a binary CSP. The success of the dual translation is surprising, from previously-reported experience, since it has as many variables as the non-binary CSP and very large domains. An important factor is the identification of many redundant constraints: it is shown that these can safely be removed from a dual graph translation if arc consistency is maintained during search.

Back to "Barbara Smith - Publications on Constraint Programming"