Homework 8: Maze Solver

Assigned

• December 4, 2024

Due

• December 9, 2024 10:30pm

Collaboration

Regular policies for collaboration apply to this homework assignment. Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone else.

Submitting

Submit to Gradescope under the corresponding assignment: all of your files needed for this assignment. This should minimally include those contained in the starter code, plus any other files you create, plus 3 additional mazes as text files. You may submit as many times as you like up until the deadline.

Overview

In this assigment you will write a program that finds a solution to a maze. Your program will build on your stack ADT that you worked on in class. The main difference is that the nodes of your underlying linked-list will be squares corresponding to a maze (as opposed to strings).

A maze here is a puzzle that you may have solved with a paper and pencil before. The maze has a start location and an end location, and the objective is to find a path between these two locations without hitting any walls.

I provide you with a lot of starter code mazeSolver.tar.gz, which I recommend you review thoroughly before trying to add any of your own code.

Specifications

• Your program will read in a file that contains the maze information
• your program will then solve the maze
• Finally, you will print the maze with the solution marked, or if there is no solution, there will be nothing marked.

File input & Maze Format

Your program should use an argument to main to specify the name of the file to read from. Review a past lab if you’ve forgotten how to use command line arguments. Then you will need to open and read the file, review the relevant lab on files if needed.

Here is an example of how to run the program with the starter code:

$ make
$ ./mazeSolver maze1.txt

The first line of a maze file will be the dimensions of the maze: two positive integers, representing the number of rows and number of columns, respectively. The next line contains the location of the start square. That is, two numbers (0-indexed). The next line contains the location of the finish square. Finally, the maze is given, each row on a new line. For each row, there will be a character which describes whether or not the right and top walls exist in that square.

• 7 means that there is a top wall and a right wall
• | (vertical bar) means that there is a right wall
• _ (underscore) means that there is a top wall
• * (asterisk) means there is no top wall or right wall

Here are example contents from a maze file:

2 3
1 1
0 2
__7
*_7

This file has the following interpretation: There are 2 rows and 3 columns. The start position of the maze is at the square (1,1) (bottom middle of the maze). The finish position of the maze is at position (0,2) (upper right of the maze). The first row: (0,0) has a top wall, (0,1) has a top wall, (0,2) has a top and right wall. For the second row: (1,0) has neither top or right walls, (1,1) has a top wall, (1,2) has a top and right wall.

A printed version of this maze with the start and finish squares marked looks like this:

+-----+-----+-----+
|                 |
|              F  |
|                 |
+     +-----+-----+
|                 |
|        S        |
|                 |
+-----+-----+-----+

You may assume that the input file contains the maze information in the correct format.

Solving the maze

If you haven’t already, take a minute to think about why a stack would be a good ADT for the problem of simulating a human solving such a maze.

Using a stack, your solution will have the following outline:

1. Create an empty stack of maze squares.
2. Get the start square.
3. Add the start square to the stack and mark the start square as ‘visited’.
4. While the stack isn’t empty:
   • Check if the top item is the finish square, if it is, you’re done and the stack contains a solution to the maze.
   • Look at each square adjacent to the top item (up, down, right, and left, not diagonals) and look for one that is neither blocked (by a wall) nor already visited. If you find one, mark it as visited and put it on the stack. Go back to step 4. (I recommend you make methods to check in each direction to keep your code more organized.)
   • If there are no squares adjacent to the top item that are neither blocked nor already visited, remove the top item from the stack and go back to step 4. (This is like hitting a dead end in a maze and backtracking.)
5. If the stack becomes empty before you find the finish square, the maze is unsolvable and you should return the empty stack.

Program output

Your program should print the solution to the maze with each square of the maze that is on the solution path marked with an asterisk. The starter code includes utilities for printing.

+-----+-----+-----+
|     	      	  |
| *    	*      *  |
|     	      	  |
+     +-----+-----+
|     	      	  |
| *    	 *     	  |
|     	      	  |
+-----+-----+-----+

If there is no solution to the maze, then your program should print a message to that effect. Also print the (empty) maze, for a visual check that there is no solution.

Note: The included printing functions may not always work perfectly. I didn’t have as much time to test these as I wanted. But, they should be able to approximately show you the solution.

Decomposition and Style

This program will likely be more complex than those we’ve written before. You are required to carefully consider the organization and style of your finished program before turing it in. You should decompose your program into smaller functions for readability and maintainability. You should also carefully group functions based on their use.

1D arrays vs. 2D arrays

In the provided starter code, I create a one-dimensional array to keep track of the squares of the maze, even though we mentally consider it to be two-dimensional. The reason for this is to avoid some extra crazy pointer situations, but nevertheless it introduces a new complexity.

Consider a 1D array of characters:

hello!

In this representation we can think of the 0th spot of the array holding h, while the 1st spot holds e, etc.

“Transforming” this data into a 2D array, we would have this arrangement of data:

hel
lo!

While the 1D array was of dimension 1x6, this new 2D array has dimension 2x3. The thing we want to be able to do, is correspond between index 1 in the 1D array (which remember holds e), and the (row,column) location in the 2D array (0,1). And possibly we might want to think about the reverse: given a (row,column) location, give the index in the 2D array.

When referencing the data of the grid, you will need to use the 1D indexing to access the relevant squares. However, each individual square will hold it’s corresponding row and column in the large maze. So you might already be able to see why we need to be able to quickly move between 1D and 2D.

If you want, you can think about how such functions would work. However, I provided them for you in the starter code.

Other Requirements

You must create 3 additional mazes to test your program on. One should be named unsolvable.txt and there should be no solution. Your others should be named maze2.txt and maze3.txt. These last two mazes should test your program in unique ways (such as requiring that the solution move right or down). You may make more examples, but at least 2 solvable mazes are required.

Your program does not need to find the shortest path, it just needs to find a solution if there is one.

Your submitted files must compile under the command make, and run with command ./mazeSolver maze1.txt.

Grading

Your assignment will be graded on a scale of 0–100 points based on the following criteria:

• Resources used statement at the top of your .c file, similar as in previous homework (0 points)
• Program reads in data from a file properly, stores it correctly, closes the file (15 points)
• All relevant variables are dynamically allocated, freed upon finishing (15 points)
• Stack using linked lists is implemented (20 points)
• Maze is solved using the provided algorithm outlined (25 points)
• Maze solution is printed correctly (10 points)
• Three mazes are uploaded (unsolvable.txt, maze2.txt, and maze3.txt) and have solutions as specificed. (15 points)

Code Quality

There will be potential deductions for any code quality violations. In addition to the requirements about decomposition listed above, there are additional requirements for quality code:

1. Indent the body of all loops and conditionals one level deeper than the code just outside the loop. Be consistent with your indentation style.
2. Use curly braces for every loop or conditional body, regardless of the number of lines.
3. Include comments that explain what your code does. There should be at least one comment by the start of each loop and if–else block that explains what the purpose of that code is. The comment should not simply restate the code; it should add information for a human who reads the code and is confused.
4. Give variables descriptive names that help a reader understand what they will be used for. Likewise, use sensible naming conventions for file names, for matching .h files, etc.
5. Do not read from or display the value of any variable without first initializing it.
6. Your code must compile with no errors and no warnings.
7. Use multifile decomposition where appropriate, include guards in any .h files.

Acknowledgements

This problem is adapted from Anya Vostinar at Carleton College, maze homework.