Virtually everyone solves mazes as a kid, but mazes can go beyond simple path-finding exercises. In a state-based maze, such as the one shown here, you need to keep track of more than just your location in the maze to solve it, and they can be surprisingly challenging!

ins01.gif Three-color maze: In this maze, get from the upper left to the lower right, traveling along edges in the order red, yellow, blue. You must finish on a blue edge to exit the maze!

ins02.gif In-order maze: In this maze, get from the upper left to the lower right, passing through the numbers 1 through 6 in order, but without crossing your path or reusing an intersection.

When you solved these mazes, what algorithm were you running? The algorithms that you used are probably not the same ones that a computer would use. Most people use a form of depth-first search, since it has a low (short-term) memory requirement, however, you can easily lose track of which paths you have already tried. Computers don't have this problem, of course, so a breadth-first search is the usual approach. Of course, humans might use other strategies, such as finding bottlenecks, searching from the end back to the start, or even searching from both directions at once, and we can program these algorithms as well! In all cases, with state-based mazes, the challenge is to make sure you represent your state correctly-a state of the search is not just a vertex of the graph, and the mazes that are easy for people to solve might not be the ones that are easy to program! We've posted sample code solutions at http://www.cs.rit.edu/~pencilpuzzle/docs/backpage/

Author

Zack Butler
Computer Science Department, RIT
102 Lomb Memorial Drive, Rochester, NY 14623
zjb@cs.rit.edu

Copyright held by author.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2016 ACM, Inc.

Contents available in PDF
View Full Citation and Bibliometrics in the ACM DL.

Comments

There are no comments at this time.

 

To comment you must create or log in with your ACM account.