Conway's Game of Life has inspired enthusiasts to search for a wide range of patterns for this classic cellular automaton. One important challenge in this context is finding the smallest Garden of Eden (GoE), a state without a predecessor. We take up this challenge by applying two techniques. First, we focus on GoEs that contain a symmetry. This significantly reduces the size of the search space for interesting sizes of the grid. Second, we implement the search using incremental satisfiability solving to check thousands of states per second. By combining these techniques, we broke several records regarding GoEs: the fewest defined cells, the smallest bounding box, and the lowest living density. Furthermore, we established a new lower bound for the smallest GoE.
@article{10_37236_2611,
author = {Christiaan Hartman and Marijn J. H. Heule and Kees Kwekkeboom and Alain Noels},
title = {Symmetry in {Gardens} of {Eden}},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/2611},
zbl = {1295.68164},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2611/}
}
TY - JOUR
AU - Christiaan Hartman
AU - Marijn J. H. Heule
AU - Kees Kwekkeboom
AU - Alain Noels
TI - Symmetry in Gardens of Eden
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/2611/
DO - 10.37236/2611
ID - 10_37236_2611
ER -
%0 Journal Article
%A Christiaan Hartman
%A Marijn J. H. Heule
%A Kees Kwekkeboom
%A Alain Noels
%T Symmetry in Gardens of Eden
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2611/
%R 10.37236/2611
%F 10_37236_2611
Christiaan Hartman; Marijn J. H. Heule; Kees Kwekkeboom; Alain Noels. Symmetry in Gardens of Eden. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/2611
