Learning Outcomes

Students will be able to (1) explain and use backtracking in Java applications, (2) read data from files using standard input redirection, (3) read data from files using a file name supplied as a command line argument, (4) gain experience in using listeners in Java.

Reading

Read the Wikipedia article on Backtracking.

Read my old course notes on Backtracking.

Activities

As a lover of rats, you’ve adopted a few as pets from the shelter. You take great care of your little friends, making sure they have lots of time to forage and participate in enrichment activities. You notice they’re really good at mazes; in particular, you’ve discovered that once they backtrack after a dead end, they’re smart enough not to needlessly revisit those paths they know aren’t right. How do they do that, you wonder? Because you are also interested in science, neuroscience, artificial intelligence, and (most importantly) computer science, you set out to build a maze-solving program. Can you do better than the rats?

Initialize a repository

As in the previous labs, go to GitHub, select Import Repository. Then:

For Your old repository’s clone URL

Enter https://github.com/rtoal/cmsi-186-lab-7-starter-code

For Your new repository details

Enter the repository name cmsi-186-lab-7.

The import might take a few minutes. When done, clone the repo and get ready to work.

Implement the Maze class

Complete the Maze class which is stubbed out in the starter code. The starter code has extensive comments telling you what is expected.

Make sure the maze tests pass before moving on.

$ javac MazeTest.java && java MazeTest

Implement the BacktrackingMazeSolver class

Complete the BacktrackingMazeSolver class which is stubbed out in the starter code. The starter code has extensive comments telling you what is expected.

The backtracking algorithm you should employ is:

Initialize path to an empty stack
Set current to the initial rat position

while True:
    Place the rat at current
    Notify the listener

    If the rat has reached the cheese:
        Return True

    // If you can, move to an adjacent cell and leave a breadcrumb
    If the cell above the current cell can be moved to:
        Push the current cell on path
        Mark the current cell as being on the path
        Move to the cell above (by updating the value of current)
    Else if the cell to the right of the current cell can be moved to:
        Push the current cell on path
        Mark the current cell as being on the path
        Move to the cell to the right (by updating the value of current)
    Else if the cell below the current cell can be moved to:
        Push the current cell on path
        Mark the current cell as being on the path
        Move to the cell below (by updating the value of current)
    Else if the cell to the left of the current cell can be moved to:
        Push the current cell on path
        Mark the current cell as being on the path
        Move to the cell to the left (by updating the value of current))
    Else:
        // There was no place to go from here! This is a dead end!
        Mark the current cell as a dead end
        “Back up” by popping from the path stack into current, but:
            if the stack is empty (i.e., nowhere to backup to): return False

Study the ConsoleBacktrackingMazeSolver class

The ConsoleBacktrackingMazeSolver class has a main method so the application can be run from the command line. If the program is given no command line arguments, it reads a maze description form standard input (we’ll cover standard input redirection in class). If given a single argument, the argument should be the description of maze. Any errors in the number or form of arguments should cause a message to be written to standard error.

If a valid maze is obtained, the application will animate the backtracking solution in the terminal window. All the “graphics” are done in the starter code, so you won’t have to write any graphics code. However, you will need to read and understand the way the animation is unobtrusively wired into the maze solver. (One of the lab report questions below asks you to explain the architecture.)

The starter code contains a couple of sample maze files, called testmaze-small and testmaze-medium. Try them out!

Stretch Challenge (Optional)

Replace the textual rendering of the maze to something pretty and colorful. As usual, there is no expectation to you work on challenge problems, and no extra credit is awarded for doing them.

What to turn in

Online:

• Your repo, cmsi-186-lab-7, should have each of the starter Java classes completed, as well as the test files from the starter code unchanged. Please make sure the code is beautiful, with well-chosen names, perfect formatting, and appropriate comments (if called for). Don’t forget to update the README.

On hardcopy or email:

1. Does your (or anyone’s) code work for a 1x1 maze? Why or why not?
2. Write a few sentences explaining the concept of listeners to a novice programmer.
3. Write a paragraph explaining how we were able to make a maze solver (e.g., BacktrackingMazeSolver) that knows nothing at all about graphics, and yet, was able to be animated while it ran.
4. Why did we not embed the maze solving algorithm as a method within the Maze class?
5. Give a maze of at least size 5x5 that does the maximal amount of backtracking. In other words, as many cells as possible should be explored and backtracked over. Commit this file with the name testmaze-5x5-maximal.
6. Generate a maze with 80 columns and 40 rows that has a lot of walls and requires the rat to travel large distances and explore a lot of dead ends before reaching the cheese. Commit your maze with the name testmaze-large.