MAZES Jessica Pearlman, Melissa Ackley, and Kate Stansfield What is a maze? • A maze is an intricate network of paths, usually designed as a puzzle. Thus, a maze has branches. • In order to learn how to solve a maze we need to learn how to graph a maze. • A junction is where two or more paths meet. When graphing mazes you label all junctions and dead ends with letters. Transforming a Maze into a Graph MAZE GRAPH http://fds.oup.com/www.oup.co.uk/pdf/0-19-850770-4.pdf The Wall Follower Algorithm • If a maze is simple it can be solved using the wall follower algorithm. • The goal may be achieved by following a wall • As you enter the maze, place your left hand on the left wall and march forward. When you reach a junction follow the most leftward path. (Left Hand Rule) • The Right Hand Rule can also be used. Simply use your right hand to follow the right wall. The Wall Follow Algorithm Continued… • The wall follower algorithm cannot be used in a cyclic maze. - You will arrive back at your original position and continue to walk in a circle • The algorithm will always work in a acyclic maze Tarry’s Algorithm http://cs.uvm.edu/~snapp/teaching/cs32/lectures/tremaux.pdf Proving Tarry’s Algorithm Rule 1: Send the token towards any neighbor exactly once. Rule 2: If Rule 1 cannot be used to send the token, then send the token to its parent. When the token returns to the root, the entire graph has been traversed. http://www.divms.uiowa.edu/~ghosh/graph.pdf Proving Tarry’s Algorithm Continued… Lemma: The token has a valid move until it returns to the root. Proof (by induction): (Basis) When the token is at the root, Rule 1 is applicable. (Inductive case) Assume that the token is at a node i that is not the root. If Rule 1 does not apply, then Rule 2 must be applicable since the path from i to its parent remains to be traversed. It is not feasible for the token to stay at i if that path is already traversed. So, the token has a valid move. Conclusion of Proof • If you follow these rules, you’re guaranteed to walk each path once in each direction and never twice in the same direction • That guarantees that you’ve visited every place in the maze and therefore must have reached the destination References Biggs, Norman L., E. Keith Lloyd, and Robin J. Wilson. Graph Theory 1736 - 1936. Walton Street: Oxford UP, 1976. Print. Robert R. Snapp. 5. Threading Mazes. Department of Computer Science, University of Vermont. 19 September, 2011. http://cs.uvm.edu/~snapp/teaching/cs32/lectures/tremaux.pdf Graphs and Mazes. Durham Gifted and Talented Summer School, Durham University, August 2009. http://maths.dur.ac.uk/~dma0vk/Outreach/GTschoolAug09/gr aphsmazes.pdf Graph Algorithms. Ghosh: Distributed Systems. University of Iowa. http://www.divms.uiowa.edu/~ghosh/graph.pdf And thanks to Professor Archdeacon for being a great mentor! The End Any Questions?