BACKTRACKING

When faced with a maze, one sure-fire solution is to follow "the left-hand rule." This will always lead to a solution, if the maze has one, although it is often not the shortest. The idea is to follow the wall on the left at every turn; if you find yourself at a dead-end, continue to follow the wall on the left as you reverse course, leave the dead-end, and turn left at the next opportunity. Assuming there is a valid path from the start to the endpoint of the maze, you will eventually find the exit. This works equally well if you follow a "right-hand rule" and always follow the right wall until you reach the exit.

Algorithmically, this is called backtracking because everytime you encounter a dead-end, you backtrack to the last place where there were several directions you could go, and you choose a different option.

In software, we can implement a variation on this with a shortcut using a stack. Everytime we hit a dead-end, we can jump from the dead-end straight back to the last choice we made and choose a different direction.

Pseudo-code:

    At the start, push all possible next locations onto a stack

    while the stack is not empty
        pop a move location off the stack
        move there
        push all possible next locations on the stack

In order not to get stuck bouncing between locations you have already been, it is common to mark the places you have been so that you do not go back to them. The algorithm becomes:

    At the start, push all possible next locations onto a stack

    while the stack is not empty
        pop a move location off the stack
        move there
        mark the location just left
        push all possible next locations on the stack

Project:

In this project, you will implement a simulation of a mouse looking for a piece of cheese in a maze, using this very methodical backtracking strategy.

You will be using the K_Stack interface and K_ALStack class from the Stack Mini-Lab for this project. You can work in the same folder, or create a new folder and copy those files into the new folder. Then download the files below. (If you already have a Mouse in a Maze project from COMP 150, you should still create a new folder and download the files below, as several of them have methods that have been added for backtracking mice.)

• MouseInAMazeApp.java: Contains the main method for the application.
• MouseMazeController.java: Controls the simulation based on user input through the graphical user interface.
• Maze.java: A grid that can contain solid cells representing the walls of a maze, a mouse, and a piece of cheese at the end of the maze. It can also contain "already-been-there" markers, placed as the mouse moves, to prevent the mouse from returning to locations it has already been.
• bigMaze.dat: A data file containing the dimensions and wall locations for a 12x12 maze.
• Marker.java: An object that marks a location the mouse has already visited.
• Mouse.java: A mouse class that could potentially move through the maze. An instance of this class never actually moves. Instances of subclasses could move in various ways.
• BacktrackingMouse.java: A Mouse subclass whose instances use a Stack and a backtracking strategy to move methodically through the maze until finding cheese.
• (Unchanged from COMP 150 Mouse in a Maze Project)
• MouseMazeGUI.java: Provides the graphical user interface.
• MazeFileMenu.java: Provides a File menu in the graphical user interface.
• MazeDataFileHandler.java: Supports reading in a data file containing maze information.
• Cheese.java: Represents a piece of cheese at the end of the maze.
• cheese.gif: An image that can represent a piece of cheese.
• mouse.gif: An image that can represent a piece of cheese.
• mouse.gif: An image that can represent a piece of cheese.
• grid.jar: the Java archive library for the Grid Package. You will have to make sure your project knows where to find this.

  In BlueJ, you can create a +libs folder under the folder containing your other code and put the jar file there, or you can specify its location in the Libraries tab of the Preferences or Properties dialog box (under BlueJ->Preferences, Tools->Preferences or File->Properties, depending on the version of BlueJ you are using).

Implementation

After you download all of the files, you could try compiling and running it to see what it does. (In BlueJ, select -- without opening -- the folder containing your code as a Non-BlueJ Project.)

Read for Understanding

Read the class documentation for the Maze class. Then read the code for the class. You may need to read about some of methods it inherits from BoundedGrid (which is, itself, a subclass of Grid), to understand the code in Maze. Class documentation for all classes in the Grid Package can be found here.

Read the code for the MouseInAMazeApp class to see how the application gets started. It creates a graphical user interface that controls the program with the help of the MouseMazeController. Next read the code for the MouseMazeController and match what you're reading with the behavior you saw in the graphical user interface.

Modify Code

Once you understand what is going on in the Maze and MouseMazeController classes, you are ready to fill in the many missing pieces in the BacktrackingMouse class.

Additional Experiment

Once you have your program working, experiment what would happen if the BacktrackingMouse class used a queue rather than a stack.

Submit your completed program through Kit, under Backtracking Mouse Project.

Have fun! And if you have any questions remember I am available through email, Teams, and my office hours. And don't forget the Collaboration Center, which is a great place to work and ask questions too!