“Completability is a key aspect of procedural level generation. In this work, we present a constraint-based approach to level generation for 2D tile-based games that simultaneously generates a level and an example playthrough of the level demonstrating its completability. … The mechanics are represented as constraints in the same problem along with the constraints used to generate the level itself. … We demonstrate the flexibilty of the system and of tile rewrite rules in several applications, including lock-and-key dungeons, platformers, puzzles and match-three style games.”