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.