Evaluation of a Modified Trémaux's Maze Solving Algorithm

Kryzsko Commons Ballroom, Winona, Minnesota

A maze-solving algorithm is a series of steps a computer can follow to find a path through a maze. Some of these algorithms require knowledge of the maze's entire layout. Others, such as Trémaux's algorithm, do not use any prior knowledge of the maze. Maze algorithms which are designed to use only partial knowledge of the maze's layout are not well-researched. I compared the performance of Trémaux's algorithm to a modified version that uses the maze's exit location. Compared to Trémaux's algorithm, the modified algorithm found the maze's exit in 53.1% fewer total steps on average when the maze connectivity was 100, 57.9% fewer total steps on average when the maze connectivity was 60, 81.8% fewer total steps on average when the maze connectivity was 30, and 95.2% fewer total steps on average when the maze connectivity was 0. This shows that an algorithm which uses partial maze information can perform better than Trémaux's algorithm, especially on mazes whose walls are less connected.