Normally, to find the rule that is suitable to our need, we have to generate all possible rules and apply each rule on a seed and check whether a rule produces a desired pattern. This method is exhaustive and computationaly intensive.

Is there a way to derive the rule that would generate the desired pattern?

  • 2
    $\begingroup$ With "pattern" do you mean a (single) configuration or an entire time-state diagram? $\endgroup$
    – dkaeae
    Commented Feb 6, 2019 at 10:06
  • $\begingroup$ I mean entire time state diagram after applying the rule, 'n' times. $\endgroup$
    – Miner
    Commented Feb 7, 2019 at 18:09

1 Answer 1


One way to achieve what you describe would be to encode your problem as a SAT instance, with clauses decribing the desired initial and final pattern and the state transitions under the (fully or partly unknown) evolution rule, and then let a generic SAT solver look for a solution.

In fact, at least for certain classes of rules (specifically, two-state isotropic rules on the Moore neighborhood, a class that includes e.g. Conway's Game of Life), you won't even need to implement this yourself, since there is an existing program called LLS that can do exactly that. While a full tutorial on how to use LLS is beyond the scope of this answer, one of the things it can do is take a partial rule string (i.e. a description of the state transition rule, with some transitions left unspecified) and a list of grids fully or partially describing the evolution of a pattern over several generations, and search for a solution that fills in the unspecified bits of the transition rule and/or the pattern.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.