The simultaneous maze solving problems

Abstract

A grid maze is a binary matrix where fields containing a 0 are accessible while fields containing a 1 are blocked. In such a maze there are four possible movements: up, down, left, and right. We call a sequence of such movements a Solving Sequence if we visit the lower-right corner starting in the upper-left corner. Finding a Solving Sequence for a grid maze is a problem that has been thoroughly considered. However, finding a single sequence such that all grid mazes in a given set are solved has not drawn great attention. Especially the formulation as a minimization problem - i.e., finding a shortest Solving Sequence for a set of mazes - is a challenging problem. We call this minimization problem the Simultaneous Maze Solving Problem (SIMASOP). Beside this general formulation, we also focus on a special case of SIMASOP called the All Simultaneous Maze Solving Problem (ASIMASOP). Given n and m, this problem requires us to find a shortest Solving Sequence for the set of all solvable grid mazes of size n x m. In this thesis we analyze both problems theoretically as well as practically. Among other theoretical results, we prove that SIMASOP is NP-complete, that ASIMASOP is in PSPACE, and give a cubic upper bound for the length of a shortest Solving Sequence for ASIMASOP. On the practical side, we present algorithms to compute shortest and approximately shortest Solving Sequences. Additionally, we provide a non-naive algorithm for finding an unsolved maze given a non-Solving Sequence and ways to compute instance-based lower bounds. Finally, we evaluate the algorithms and compare the results of the different approaches as well as provide lower bounds. Surprisingly, for ASIMASOP with size 4 x 4, for which there exist 3828 solvable mazes, it is already difficult to find a shortest Solving Sequence. We are able to compute a Solving Sequence of length 29 and a lower bound of 26 for this instance.