C S 314 Chapter 8: CS Textbook CH 8
Document Summary
The mouse starts in an open position. The mouse has 4 possible moves at each point: w, n, e or s. We have to keep track of where the mouse has been, or it might wander infinitely in circles. The list prev is a stack of previous states. If the mouse re-visits a position on prev, we want to fail. We need to return an answer: nil for failure, a list of moves that will lead from the current position to the goal; for the goal itself, we will use the sentinel (cheese). As we unwind the recursion, we will push the operator that led to the goal onto the answer list at each step. For some applications, we need to traverse an entire tree, performing some action as we go. Preorder: process the parent node before children. Postorder: process children first, then the parent. Inorder: process one child, then the parent, then the other child.