These programming projects are an extension of the Mouse in a Maze Project 1.

Mouse-in-a-Maze Project 2: Backtracking Using Stacks

Re-implement the Mouse-in-a-Maze project using a stack. The mouse should no longer move around the maze randomly. Instead, it should try each path systematically, using a technique called backtracking to go back to the last untried path when it is blocked. The suggested algorithm is to put all unvisited neighboring hallways on a stack and then pop one of them to try that path. When you pop a position off the stack, you should double-check that it has not been visited between the time you pushed it on the stack and the time you are popping it off the stack. If it has, pop the next position off the stack.

Note: in the previous implementation, the mouse and the display objects had copies of the maze as private data members. Since the maze never changed, this was OK. Now that you are marking positions as visited, though, that will be a problem. One solution is for the mouse (and display) to have a pointer to the maze, rather than a copy of the maze. Another solution would be for the maze to be a reference data member in Mouse and Display. (Note-within-a-note: reference data members are not part of the AP Subset.)

Mouse-in-a-Maze Project 3: Backtracking Using Recursion

Re-implement the Mouse-in-a-Maze project using recursion to implement backtracking. When you move to a position, you should double-check that it has not been visited between the time you put it in the neighborhood and the time you are moving to it.

^*The Mouse in a Maze assignment is an extension of the Advanced Placement Computer Science Marine Biology Simulation Case Study, available from the College Board. It uses Alyce Brady's graphical version of the case study (which, in turn, uses the CMU Graphics Package available from Mark Stehlik's web site at Carnegie Mellon University), but could be modified to work with other graphical interfaces.