Unified Logic Maze Generation Using Network Science

Solving maze puzzles is a recreational activity with longstanding roots in human civilization dating back several thousands of years. This paper considers the problem of automated maze generation for a more recent class of maze puzzles, the logic maze, popularized by Abbott in 1990. Although there are several distinct types of logic mazes, we present a single unified generation strategy based on a state graph representation. We capture desirable features of a maze in an objective function that consists of several network science metrics on the state graph and the original maze. We then optimize this objective function through the use of local state space search and obtain high-quality results.