CSC 212

CSC 212 Assignment 7: Recursive Maze Solving

Smith College > CS Dept > CSC 212 > Assignments > Recursion

Course Links

• Home
• Syllabus
• Calendar
• Texts
• Office Hours
• FAQ

Exercises

• Assignments
• Labs
• Style Guidelines
• How to Submit

Resources

• Lecture Links
• Tutorials
• Videos
• General
• Java
• Past Exams

External

• C.S. Dept.
• Smith College
• Moodle Page
• Slack

Overview

For this assignment, you will write a GUI-based program for solving mazes using recursion. The path from the start to the current location will be stored implicitly in the call stack, allowing for easy backtracking. This assignment pulls together many pieces that we have learned separately into a closely interacting whole.

At a minimum, your program should display the maze itself and two buttons: Solve and Reset. These will (respectively) display the solution to the maze and return it to its unsolved state. When solving the maze, your program should also print a list of the steps taken to solve the maze, or if the maze is insoluble it should print a message to that effect. As an optional but fun addition, you can also make your program display its progress as the recursion proceeds.

As with most GUI-based assignments, this one may take a bit longer than some. Therefore you should start it early if possible. I will give you some pieces of code to help control the amount of work you must do.

At this point in the semester, you should have developed the ability to plan the structure of a program mostly on your own. Therefore, this assignment will define the problem to be solved and give a few suggestions, but most of the actual planning and development will be left up to you. One exception is the recursive behavior, which will be examined in more detail because it is a new subject.

Input Format

Your program should be able to read maps in the following format, without prompting. A valid input file should contain a character grid representing the maze. In this grid, a # represents a wall, and a . represents a passageway. The symbols S and F, respectively, represent the start and finish of the maze, and should appear exactly once. Here is an example of a simple 6x9 maze file:

#########
#S..#...#
#.#.#.#.#
#.###.#.#
#.....#F#
#########

Note that although this example shows walls completely surrounding the outer perimeter, your program should not assume this will always be the case. Don't wander off the edge of the maze! One way to accomplish this is to make an accessor for the maze contents that returns a wall for any coordinates outside the maze.

To start the development of your program, you might decide to begin with a fixed maze coded within the program itself. However, for full credit your program should be designed to read in the maze information in two possible ways:

• The maze data may be given directly as input via input redirection: java MazeSolver < MyMaze. In this case, your program should read the maze from the standard input. (See the tutorial on input redirection.)
• A file name can be given on the command line: java MazeSolver MyMaze. In this case, your program should read the maze data from the file MyMaze. (See the tutorial on external files.) Depending on whether we have time to go over this topic in class Tuesday, this part may be considered optional/extra credit.

You can distingish the two cases by looking at the length of the args argument in main(). Although the two methods differ slightly, try to make them use the same code as much as possible.

Recursion

As stated above, the main part of your program should be recursive. Here are the details:

Problem Statement

exitReachable: Given a map (showing areas that have been already explored), and a location, determine whether the exit can be reached by moving through adjacent squares without passing through a wall or previously visited square.

Starting Condition

To begin searching for a solution, the map of the maze should show every open square as unexplored, and the location will be the starting point.

Stop Criterion

There are two possibilities, one for success, and one for failure.

• If the current location is the finish of the maze then report success (return true).
• If the current location is already visited or a wall then report failure (return false).

Simplification Step (Express the result in terms of a simplified problem)

Mark the current square as visited, thus simplifying the problem. The exit is reachable from the current location iff it is reachable through the square adjacent to the north, or the south, or the east, or the west. Practically speaking, this will take up to four recursive calls to determine, combining the results using a || operator (logical or). Because the || operator uses "short-circuiting" logic, if any one of these calls returns true the remainder will not be evaluated.

Starter Files

To prevent your spending too long on some of the more mundane details of this assignment, here are some files to get you started. You may feel free to modify anything in these files as you wish, and you will submit all files (modified or not) with your assignment. If you use these files, the main thing remaining to create is class Maze, which includes (among other things) a solve() method and a method to read in the maze from some input. Two of the files below make use of enumerated types, which we saw in lab but have not covered in class. Fortunately, you will not need to implement any enumerated types, but will use ones that have already been written.

• MazeContents.java
• MazeCoordinate.java
• MazeDirection.java
• MazeSolver.java (older version here)

Further Hints

• On the recursion.
• On the animation.
• On the class design.
• On reading the input data.

To Submit

• Maze.java
• testdata containing mazes you used to test your program. (Note that a normal input file will only have one maze, but for grading purposes you should include several here, testing a range of conditions.)
• readme.txt
• typescript showing compilation and output from one run of the program
• All other files needed to compile your program

Quick Start

• Read through the starter files supplied, and plan out your Maze class
• Begin with a default constructor that creates a fixed test maze
• Write the methods required for the maze to display itself as a JComponent
• Write the recursive solving method and the reset method
• Write new Maze constructors that will read in a text version of the maze and convert it to an internal data structure
• Develop a comprehensive set of test mazes and test your program thoroughly

Extra Credit

As another optional extension, you could include a JTextField box in the GUI, and load in a new maze file if the user types its name into the box. You will need to add a TextListener so that your program will be alerted when the user types a file name. (See the JavaDoc for TextListener) Only try this if you have completed everything else in the assignment.