Garden of Eden[0] is a related concept where time-reversal comes up. Mentions NFAs, DFAs, backtracking and brute-force analysis. I see no mention of it but the latter was probably doing custom SAT implicitly, even if there was no access to our nice fast modern solvers.

[0]: https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...