CS 142 Project 4: Corn-Free Maze

Starter code
Introduction to backtracking
Warmup: exact change
The corn-free maze
Demo
Concepts you will use in this program
Implementing the project
Sample output
Final reminders
Coding style and citations
Getting help: humans vs. AI
What to turn in
Reminders
Challenges

Starter code

Make a new IntelliJ project, then download and unzip the following starter code.
Then copy or drag-and-drop the files into the src folder of the new project you just created.

Link to download starter code: cornmaze-starter.zip

Introduction to backtracking

In this project, we will explore a particular type of recursion called backtracking. Backtracking is used to solve problems where the solution corresponds to a sequence of choices to be made. Backtracking is a particularly elegant way to solve these kinds of problems, especially because this kind of problem cannot be solved (easily) with standard loops.

In your starter code, open DoubleOrAdd.java and follow along with this introduction to backtracking.

Warmup: exact change

To get a feel for how backtracking works, we will solve a simple problem together first. Open ExactChange.java and follow these instructions.

Do not move on to the corn-free maze until you have completed the exact change problem and the concepts make sense to you.

The corn-free maze

Every year, Farmer Phil creates a corn maze for the local Memphians to navigate through. This year, however, so many people are apparently allergic to corn that Farmer Phil decided to bulldoze his crop and create a maze in the open field with no walls at all. Instead of using corn as obstacles, each row and column in the maze has a number that specifies how many cells in that row or column must be filled in the maze solution.

For example, suppose you have this maze:

The green circle indicates the starting location, the red circle indicates the ending location, and the numbers along the sides indicate how many squares in that particular row or column must be filled as the person solves the maze.

Here is the solution:

Notice how the numbers along the sides of the maze match the number of cells filled in that particular row or column. Any other path between the green and red cells would have a different number of cells in some row or column, and so would not be a solution to this particular maze.

In this project, you will write a program to open a text file containing a maze description, use a recursive backtracking algorithm to find the path through the maze, and display the solution along with some statistics.

Demo

Concepts you will use in this program

Maze text files

Each text file describing a maze is organized into lines, as follows:

The first line contains the number of rows and number of columns in the maze.
The second line contains the (row, col) of the starting point.
The third line contains the (row, col) of the ending point.
The fourth line contains a sequence of integers, one per row, specifying how many cells must be part of the solution path for that row.
The fifth line contains the same as the fourth line, but for columns.

Here is an example file (maze2.txt):

This file describes a 5-row, 5-column maze.

Restrictions on the maze solution path

Because this maze has no walls, we must place certain restrictions on the solution path.

The path can only go up, down, left, or right, not diagonally.
The path can use each square at most once (so the path cannot cross itself).
The path cannot turn in such a way that two sections of it are next to each other. For example, the following path is illegal because it is impossible to tell in the bottom right corner (the section of 4 stars in a square) what the true path is.
```
* * * *
. . . *
. . * *
. . * *
```
This path is also illegal:
```
. * * *
* * . *
. . * *
. . * .
```
because of the diagonal adjacency in the middle.

Marking squares

The maze is represented by a two-dimensional char array. This array initially contains all periods ('.'). We mark squares with asterisks ('*') when we arrive at a square, indicating it is part of the current path. When evaluating which directions to recurse on, we must never recurse on a square that is already marked. This prevents the path from going in circles.

An asterisk is placed in a square at the beginning of each recursive call. It is only removed if we need to backtrack. Therefore, when the algorithm finds the ending location, there will be a single trail of asterisks from start to finish. If the recursion fails in all four directions, the asterisk is turned back into a period.

Determining if a step is legal

When considering adding a new square to the path, the new square must be open (unmarked). However, there are five additional squares that must be checked relative to the new square. See the following diagram:

This picture shows a possible path from the green circle. For this example, ignore the row/col counts. Suppose we are considering adding the cell with the question mark to the end of the path. We must verify that the five cells with X marks are either open or off the board. Those five cells are the adjacent and diagonally-adjacent cells to the question mark (excluding the cell we just came from, which is already marked).

This works even when the path turns; see this diagram:

To help you implement this, the starter code has functions to fill in called isOpen and isOpenOrOffBoard. Each takes a (row, col) coordinate:

isOpen should return true if the (row, col) is an unmarked square on the board, and false in all other cases (including if the (row, col) is off the board).
isOpenOrOffBoard should return true if the (row, col) is an unmarked square on the board, or if the (row, col) is off the board.

Solving the maze with backtracking

We will write two recursive functions to solve the maze, following the same two patterns you used in the exact change warmup:

Boolean version (canSolve): determines whether the maze can be solved. Returns true on success, false on failure.
Directional version (directionalSolve): determines how the maze is solved. Returns a string of directions (N, S, E, W) ending in "!" on success, or "X" on failure.

Both versions use the same backtracking idea. At each step, the person in the maze considers moving in each of the four cardinal directions (north, south, east, west, in that order). For each direction that is legal, the function makes a recursive call from the new position. If the recursive call succeeds, the current call also succeeds. If none of the four directions leads to a solution, the function backtracks — it unmarks the current square, restores the row/col counts, and reports failure.

The base case is when the person is at the ending location and all row/col counts are zero. At that point, the maze is solved. Note that reaching the ending location alone is not enough — the counts must also all be zero.

The structure of both functions follows the same pattern you saw in DoubleOrAdd and ExactChange. The boolean version returns true/false; the directional version returns a string or "X". Converting from one to the other is the same mechanical process you practiced in the warmup.

Implementing the project

For this project, I will provide guidance in terms of a suggested order, but you will have to make more design decisions about what functions and variables to use. There may be times when you want to adjust methods or add parameters.

Begin by getting acquainted with the code. This project uses two main classes (plus SimpleCanvas):

Maze.java: represents the current state of the maze. It includes methods to load a maze from a text file, print the maze in text form, draw the maze on a canvas, and solve the maze in two different ways.
RunMazeSolver.java: a driver class for the Maze. It exists to get the project started from a main() method and also contains testing functions that you will fill in.

Also take a look at the text files you are provided. Each maze is solvable except badmaze.txt, which is purposefully unsolvable.

Step 1: Reading a maze from a text file

The first piece to get working is reading the maze from a text file. Read through Maze.java and make sure you understand the purpose of all the instance variables.

There is a function called loadMaze() in Maze.java that takes a string — the name of a text file — as a parameter. The constructor calls loadMaze() for you. There are comments in the function to help you along, but the idea is to read the text file and store its contents into the appropriate instance variables.
- Stop and test. Write the testFileReading() function in RunMazeSolver. Create a new Maze object with one of the sample text files, then call printMaze(). Use print statements in loadMaze() as needed to verify everything is being read correctly.
Write the printMaze() function in Maze. This function is mostly used for debugging, but it is important to be able to see the contents of the maze textually.
- Stop and test. Add a call to printMaze() in your test function and verify the output looks correct.

Step 2: Drawing the maze

Next, focus on drawMaze() in Maze.

The Maze constructor opens a SimpleCanvas, with width and height calculated from the maze dimensions. There is a constant called SQUARE_SIZE in Maze.java that controls how big the squares are drawn.
Fill in the code for drawMaze(). Most of the drawing code is written for you. You need to draw the green and red circles for the start and end locations, and then draw small circles to represent the current path (squares marked with '*'). You will not see a path until the solver is working.
- Stop and test. Write the testDrawing() function in RunMazeSolver. Read in a maze file and call drawMaze() to verify the maze appears on the canvas.
Note: if you cannot get the drawing code to work, you can still proceed to the following steps using printMaze() instead of drawMaze().

Step 3: Get the boolean solver working

In this step, we will write the first recursive formulation, which determines if the maze can be solved. This is done by implementing canSolve() and canSolve(int currRow, int currCol). The first is the public wrapper function that you will call from RunMazeSolver; the actual recursion happens in the second, private function.

Begin by writing isOpen and isOpenOrOffBoard. Then use those two functions to fill in canMoveNorth, canMoveSouth, canMoveEast, and canMoveWest. Each of these functions checks if a certain cell is open, if five surrounding cells are open or off the board, and if the relevant row and column counts are still positive.

Then write the no-argument canSolve(). This wrapper should draw the maze, wait for a click, and then call the two-argument canSolve() from the starting location.

Stop and test. Fill in testBooleanSolver() in RunMazeSolver. Load a maze and call canSolve(). Have canSolve(int, int) print the current location when it is called. Verify the starting location is correct.
- Then write the two-argument version of canSolve. This is the trickiest part of the assignment, because this is where the recursion and backtracking happen. Use print statements and the debugger to get this working. You must print the location when the person arrives at a square and when the person backtracks — these messages are critical for debugging.

See the demo video above for reference.

Once the boolean solver is working, start building the final version of the program. At this point, write code in main() so that your program:
- Asks the user for which maze file to read.
- Asks the user for the pause time (in milliseconds) for the animation. You will want to add an instance variable for this in Maze.java, along with a method to set it.
- Asks the user whether to run the boolean solver or the directional solver (you can skip this for now if the directional solver is not written yet).
- Runs the solver, displaying the maze textually before and after solving. The graphical display should animate the path as it is constructed and backtracked.
- Prints the total number of recursive calls when done. You will need to add an instance variable in Maze to keep track of this.
Stop and test. Test your solver against the sample output linked below. Verify that the text output and the total number of calls match.

Step 4: Get the directional solver working

In this step, we will write the second recursive formulation, which determines how the maze is solved. This is done by implementing the two versions of directionalSolve(). These work similarly to the two canSolve functions. The only major difference is that instead of returning a boolean, they return a string: a sequence of directions (N, S, E, W) ending in "!" on success, or "X" on failure.

Write these two functions, following the guidance in the code. The conversion from the boolean solver to the directional solver follows the same pattern you used in the exact change warmup: replace true with "!", replace false with "X", and prepend the direction letter to the result as it comes back up.
Stop and test. Test your solver against the sample output linked below. Verify that the text output, the total number of calls, and the solution path all match.

Sample output

maze0: [ Boolean solver ] [ Directional solver ]
maze1: [ Boolean solver ] [ Directional solver ]
maze2: [ Boolean solver ] [ Directional solver ]
maze3: [ Boolean solver ] [ Directional solver ]
badmaze: [ Boolean solver ] [ Directional solver ]

Final reminders

Your code should:

Prompt the user for a filename, pause time, and which solver to use.
Display the maze textually, run the desired solver, and display the maze again afterwards. The second text display should show the final path.
As the solver is running, the graphical display should show the path as it is being constructed and backtracked.
When done, print the total number of calls to the solver. If using the directional solver, also print the solution path and its length.

Coding style and citations

You should use good programming style when writing your program. All other style guidelines, including proper indentation and comments, should be followed.
Projects are intended to have you practice coding concepts covered in class; the goal of completing the project is to demonstrate your understanding and knowledge of the material that we have covered, not to find the shortest path to a working program. For that reason, while I always encourage learning things outside the class and using external resources to help you, you should do your best to stick to using coding techniques learned in class.
If you are unsure whether a particular feature or approach is permitted, ask me before submitting.
If you do use an idea that you got from an outside source (a person, a website, or AI), you should acknowledge that source in a comment in the code, explaining where the idea came from, including the person’s name, complete website URL, or name of the AI. Not doing so is a serious academic violation.

Getting help: humans vs. AI

Why work without AI for now? This project is designed to build your problem-solving muscles. When you struggle with a bug or concept, that struggle is where the learning happens. Here is why human help is better at this stage:

Professor Kirlin and the tutors can meet you where you are. We can ask questions to understand your thought process, not just fix the code.
We help you learn to debug. AI will often just give you corrected code. The tutors and I can teach you how to find bugs yourself, which is a skill you will use forever.
We can explain the “why.” Understanding why a piece of code works the way it does is more valuable than having working code you do not understand.
Office hours are for YOU. Seriously, I love talking through these problems. My general rule of thumb is that if you have been stuck on something for 30 minutes or more, ask for help.

What to turn in

Through Canvas, turn in all your .java files.
Additionally, upload a text file answering the following questions:
- What bugs and conceptual difficulties did you encounter? How did you overcome them? What did you learn?
- Describe any serious problems you encountered while writing the program (larger things than the previous question).
- Describe whatever help (if any) that you received. Do not include readings, lectures, and exercises, but do include any help from other sources, such as websites or people (including classmates and friends) and attribute them by name.
- Did you do any of the challenges (see below)? If so, explain what you did.
- List any other feedback you have. Feel free to provide any feedback on how much you learned from doing the assignment, and whether you enjoyed doing it.

Reminders

Do not forget to comment your code and put a comment at the top with your name and the pledge.

Challenges

You may notice, especially on the larger mazes, that there are paths the solver explores that you can see (as a human) will eventually require backtracking, even if the computer does not immediately realize it. In other words, the recursive maze solver is rather inefficient, and a human would probably avoid exploring as many of those dead-end paths. Change your program so it is more efficient (explores fewer paths that need to be backtracked). Make a copy of Maze.java before you do so, and turn that in along with the original Maze.java (where the output will match the sample output).