2013/08/09 by C. Hartman, Marijn J. H. Heule, Kees Kwekkeboom +1 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Engineering · Mathematics · #Cellular Automata and Applications #DNA and Biological Computing #Modular Robots and Swarm Intelligence #Bounding overwatch #Mathematics #Combinatorics #Context (archaeology) #Satisfiability #Cellular automaton #Grid #Focus (optics) #Symmetry (geometry) #Space (punctuation) #Discrete mathematics #Theoretical computer science #Computer science #Algorithm #Artificial intelligence #Geography #Archaeology
paper · pdf · doi:10.37236/2611
openalex publication_date 2013/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.