There is a certain class of puzzle games like SpaceChem, Opus Magnum and Molek Syntez, all by Zachtronics, where the objective is to create and program an automaton that performs a certain function under the games rules. The solutions to the puzzles can be thought of as initial states to a big cellular automaton with the games rules being the propagation rules. Beyond simple amusement these give rise to structures of incredible complexity, indeed the first two have even been shown to be Turing-complete! Nonetheless there either exist no programs to automatically find solutions at all or they don’t even rival casual human performance. It would therefore be both an exciting challenge and potentially interesting research endeavour to construct such a program for at least the following reasons:
*These puzzles occupy an unexplored middle ground between simple cellular automata like Conway’s game of life and complex real world problems.
*Nonetheless, precisely because of their gamefied nature, they can be visualised very well and make use of intuitive 2D geometric structure.
*This problem can be seen as one of program synthesis where in many ways a similar challenge is faced and some insights might be transferable.
The objective of this thesis would therefore be to model one of the games (or parts of it) in a way that makes it possible to apply existing problem solving tools, like SAT solvers or Constraint Programming solvers. Furthermore experiments on the performance of these approaches should be performed as well as a rough review of the relevant literature.