Symmetry in gardens of Eden

Title

Symmetry in gardens of Eden

 Author

Hartman, C.
Heule, M.J.H.
Kwekkeboom, K.
Noels, A.

Faculty

Electrical Engineering, Mathematics and Computer Science

 Department

Software Technology

 Date

2013-12-31

 Abstract

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.

 To reference this document use:

http://resolver.tudelft.nl/uuid:6968942b-88c3-4a06-9315-7c12e578dbf9

 ISSN

1077-8926

 Source

The Electronic Journal of Combinatorics, 20(3)2013

 Part of collection

Institutional Repository

 Document type

journal article

 Rights

(c)2013 The Authors
Files
PDF 296856.pdf 429.11 KB
Close viewer