Subset diagram
A subset diagram is a device used in graph theory to locate possible paths. It is related to the maze running problem wherein the possible routes to an exit are sought. As applied to cellular automata via the de Bruijn diagram, it will reveal the possible ancestors to a prescribed configuration. If there are none, the configuration has to be a Garden of Eden. It can also solve the reset problem, whose requirement is that a chain of link labels be given so that no matter the starting point, a given destination will always be reached. What that would mean for a cellular automaton is that a configuration could be forced to end in a certain way from a similarly specific beginning.
de Bruijn diagram
Shown at right is the de Bruijn diagram for Wolfram's (2,1) Rule 22, which is the one followed by orthogonal ripples in the Game of Life. By that rule, a live ripple can only arise at the empty margin of a previously existing ripple (001 -> 1, 100 -> 1), or persist when surrounded by empty space on both sides (010 -> 1).
In the figure, the nodes are ovals adorned with useful information. Using black and white for live or unlive cells respectively and taking into account that neighborhoods are three cells long, they are broken into two overlapping pieces each two cells long. The four combinations of occupied or unoccupied cells are colored black or white, respectively, and might ordinarily be labelled as though they were binary numbers.
However, they are destined to occupy one each of the four unit classes in the subset diagram, whose nodes are subsets. Giving binary representation of subsets precedence over any internal description of the nodes, the weights 1, 2, 4, 8 are assigned, allowing subsets to be labelled by the total weight of their contents; 0 designating the empty set and 15 the full set. Showing both numbers could be useful, as long as each is kept in its place. The weights could easily be permuted, leading only to relabelling the graphs while keeping their structure.
The links are labeled by the state to which the completed neighborhood evolves, since the sequence of those neighborhoods will be the ancestor of the corresponding chain of links, the presumed object of constructing the diagram. The links have been colored blue for 1 (live), red for 0 (not live), rather than by trying to place letters or numbers next to the links.
subset diagram
Linkage in the subset diagram follows the linkage in its base graph, except that arrows point to all the base nodes reachable by a link of a given color rather than by just one of them. Rather than having a link leading nowhere as a consequence of the lack of a link, the empty set is a surrogate destination. With that convention, the same number of subset links emanates from every node. Given that the de Bruijn diagram for a binary automaton has two outgoing links per node, its subset diagram will have links to the empty set, a singlet base node, or a pair. In all cases, a union of subsets links to a union of their destinations.
The existence of a Garden of Eden now depends on whether there is a path through the subset diagram leading from the full set to the empty set: No matter how the configuration is started, it cannot be finished, no matter how it evolves.
In the diagram for Rule 22, there are multiple routes between 15 and 0, one of the shortest of which is 10010101; the placement of that final 1 is fatal. An equally short path, 10101001 runs along the right edge of the diagram; note that Rule 22 is symmetric by reflection.
The foregoing discussion applies to a one dimensional cellular automaton, settling the existence of Gardens of Eden for ripples. Presumably a similar analysis would apply to a two stage de Bruijn diagram describing a two-dimensional cellular automaton; the greatest impediment is the exponential size of any subset diagram relative to its underlying graph. Another search strategy with its diagram might give better results. After all, examining all the subsets is equivalent to an exhustive search; just more organized.