Project 1: Maze solver

Due: Sunday, 9/4/2022, by 12:00pm noon

You will receive 100% for turning this project in and passing the functionality test and style check before the deadline. After the deadline is 25% off.

Total points: 50

Before you start this project, you should have read the project submission guidelines and the coding style rules.

After that, get started on the project immediately! You will submit your solution to Upload Site.

Project Description

The goals of this project are to:
  • Practice the use of data abstraction,
  • Practice the invocation of methods and passing of parameters,
  • Use input output functions (cin/cout), which is used a lot in this class
  • Test your program in the command line environment with input/output redirection and diff utilities, and
  • Get used to how this course uses Upload Site for submissions.
Write a program that searches through a maze to find a path from the beginning to the end. The maze will be a two-dimensional grid of locations, numbered by row and column. We could draw out a maze like this: 
   0 1 2 3  
 0 X X X X
 1 E   X
 2 X   S

A maze is described by 3 things: the valid locations (places where it's okay to walk, indicated as an X in the figure above), the start location (indicated by S), and the end location (indicated by E). Your program should first read the number of valid locations in the maze, and the row and column of each valid location. It should then read the starting location and the ending location. For the maze pictured above, the input would be: 
8

0 0
0 1
0 2
0 3
1 0
1 2
2 0
2 2

2 2
1 0

If a path can be found, the program prints a solution in the following format: 
Solution found:
2 2
1 2
0 2
0 1
0 0
1 0

Your program should be iterative, not recursive. We will use a stack to simulate recursion. The stack forms a natural data structure for storing what has been visited in the past, and the stack makes it easy to go back to a previous decision and try a different location. This type of search is common in computer science, and is called depth-first search (DFS).

The driver will contain the logic to solve the puzzle. It should start at the starting location, and is only allowed to visit locations that are valid (according to the input). At each stage, the solver should either move forward in some direction (right, down, left, or up) and push that new location on the stack, or it should back up one location by popping the current location off the stack. This continues until the solver has either reached the end location or it has become empty (indicating that there is no path from the start to the end).

The stack should keep track of the locations that have been visited from the start until the current location (the current location should be the one on the top of the stack). Each step should look at the current location and use that location to produce a "neighbor" location. A neighbor location is a location (possibly invalid) which is one step away from the original location. For example, 2 2 is a neighbor of 1 2. If the neighbor is both a valid location, and is not currently on the path that has been traversed (on the stack), then it will be added to the stack for further exploration. If all the neighbors of the current location (on the top of the stack) have been visited, then that location is removed from the stack (this is called backtracking).

The Location class contains both the coordinates of the location and the functionality for an iterator. A Location object is able to iterate over all of its neighbor locations. Please read the comments in the location-proj1.h file for more details of how the iteration should work. Because the stack will contain Location objects, and each Location object is an iterator over its own neighbors, each Location object on the stack will know which of its neighbors is next.

Here is a pattern you should consider using in your driver when searching the maze. The top of the stack represents the current location. To get its next neighbor, you will need to call nextNeighbor() on that object. However, the top of the stack is required to be constant (by the stack) and nextNeighbor() is a non-const method (it should modify its own nextDirection -- only). Therefore to get the next neighbor and also update the nextDirection of top of the stack, you should do the following:

  • make a modifiable copy (call it m) of the top of the stack
  • pop the top of the stack
  • call m.nextNeighbor() (giving you its neighbor)
  • push m back on the stack (now the top of the stack has the same current location, but pointing in another direction)

Input specification

Input will consist of a positive integer, which is the number of valid locations. This will be followed by that many Locations, which form the list of valid Locations. After that will come the start and the end locations. The start location and the end location are guaranteed to be valid.

Output specification

If no solution to the maze exists, then the program prints: 
No solution found

Otherwise, the program prints a solution in the following format: 
Solution found:
2 2
1 2
0 2
0 1
0 0
1 0

Note that the program should report only the first solution it finds, not every solution there may be. The solution the program finds is heavily dependent upon whether the Location class iterates properly over its neighbors.

Sample input files

Use these sample input files to compare the output of your solution to the correct output. You can get the correct output by running the input through one of the sample executables. Download the files (don't cut and paste), use file redirection, etc.

Sample executables

Here are sample executables for you which correctly solve this problem. When you design test cases, you can judge your output against the output from the correct solution. These are the same correct solution compiled for various operating systems: If you give a command-line argument to these executables, they will print extra information about how it is solving the problem. For example, this will execute the program like normal, redirecting input from a file called my_input.txt: 
% project1_solution_dos.exe < my_input.txt

But here is the mode of operation that will cause the program to print out what it is doing in more detail: 
% project1_solution_dos.exe printMore < my_input.txt
The command-line argument doesn't have to be the word "printMore," it can be anything.

Provided code

You must use the .h files provided here: Do not alter these files; use them as I have provided them. The files have comments describing the purpose of each class and member function. We'll also talk about these in class.

Project testing and milestones

This is a larger project, so it's best to write your code in stages and test each stage as you go. This is a generally good strategy for solving problems: break them down into smaller parts, and solve each part, testing each solution as you go. This means testing each method individually with driver programs written just for testing.

Since this is a large project, it helps to have a plan of attack. The following milestones should be done before our class meeting on the due date so that we can flush out any issues. For each milestone you should create a test driver that tests what you have written; in general this should be "driver-projX.cpp" file for project numbered X (even though the test driver is not what you will ultimately use for the project). You need not upload milestones. Milestones are not graded.

Milestones represent the minimum progress required to finishing the project on time. However, if at each milestone you completely test and debug your code, you should have no problems finishing the project in time.

Step Finish by Milestone
1. Tuesday, a.p. WRITE and TEST all the methods of the Location class. Also develop 10 test mazes that you will use later to test your project. Make them high quality! Include these in your milestone (as text files).
2. Friday, a.p. WRITE and TEST all the Stack and Maze methods.
3. Monday, w.a.p. WRITE and TEST the driver. Use your own test inputs and make sure your program produces correct outputs.

Discussion

Remember that one of the most important concepts in this exercise is data abstraction. Note, for instance, that the public interface for the Location class does not mention rows/columns, or any of the data members required for iteration. The Maze class also makes no mention of rows/columns.

There is no limit on the number of valid Locations. Note that if you use a very large number of valid Locations, your program may run for a very, very long time. My computer will test with reasonably-sized inputs that your program should be able to solve quickly.

Final notes

Remember when writing this program to adhere to the coding style guidelines. This is an individual project, so you must work alone. No credit will be given for a solution which does not pass the functionality test. For more detailed instructions, read the project submission guidelines.