Subject : Problem Solving

Topics: graphs and trees, tree traversal,...

Part A: Traversing a maze Consider the following maze: A|BCDE the goal square is N. The arrows show the directions north(N), west(W), south(S) and east(E). All squares are reachable and there are no loops. STRATEGY The maze is to be traversed in the following manner: Begin on the starting square Start with an empty list While you have not reached the goal square For each square adjacent to your current square (in the order E, S, W, N If the square has not yet been visited and there is no wall in the way, add it to the start of the list. Visit the square at the start of the list and remove that square from the list. Part A: Traversing a maze Consider the following maze: A|BCDE the goal square is N. The arrows show the directions north(N), west(W), south(S) and east(E). All squares are reachable and there are no loops. STRATEGY The maze is to be traversed in the following manner: Begin on the starting square Start with an empty list While you have not reached the goal square For each square adjacent to your current square (in the order E, S, W, N If the square has not yet been visited and there is no wall in the way, add it to the start of the list. Visit the square at the start of the list and remove that square from the list