Genetic algorithms and the art of Zen

The Zen Puzzle Garden (ZPG) [16] is a one-player puzzle game involving a Buddhist monk raking a sand garden. It is inspired by Japanese garden design (for example, the Komyozenji temple garden is shown in Figure 1). One common feature of such gardens is a flat region of sand or small pebbles, which is raked into a pattern. The ZPG is one example of a transport puzzle; these are problems that involve the player moving entities around a given domain (e.g., boxed around a warehouse), starting at some initial configuration, until they attain predefined goal conditions. Entities must move according to the constraints of the puzzle, and may only move between connected positions (that is, an entity may not be "lifted" off the board and replaced at a position perhaps far from its initial location). A graphical representation of the problem may use vertices to represent the set of positions an entity may occupy, with connecting edges determined either from any explicitly named connections, or from those implied by arrangement on the board or within a grid. The rest of the paper is organized as follows: We first describe related work in Section III and give an indepth description of the problem in Section III, before describing two solution methods (genetic algorithm and A*) for the ZPG in Section IV. Experimental results are presented in Section V, before we conclude with a brief discussion of the implications of our findings in terms of broader applicability.