Conference Proceedings
Using relaxations in maximum density still life
G Chu, PJ Stuckey, MG De La Banda
Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics | SPRINGER-VERLAG BERLIN | Published : 2009
Abstract
The Maximum Density Sill-Life Problem is to fill an n ×n board of cells with the maximum number of live cells so that the board is stable under the rules of Conway's Game of Life. We reformulate the problem into one of minimising "wastage" rather than maximising the number of live cells. This reformulation allows us to compute strong upper bounds on the number of live cells. By combining this reformulation with several relaxation techniques, as well as exploiting symmetries via caching, we are able to find close to optimal solutions up to size n∈=∈100, and optimal solutions for instances as large as n∈=∈69. The best previous method could only find optimal solutions up to n∈=∈20. © 2009 Sprin..
View full abstractGrants
Funding Acknowledgements
We would like to thank Michael Wybrow for helping us generate the still life pictures used in this paper. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council.