Description
Project description 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.
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 iterationCurrent() on that object, and then call iterationAdvance() on that object. However, the top of the stack is required to be constant (by the stack) and iterationAdvance() 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 • call m.iterationCurrent() and store its result in another Location (this is the neighbor) • pop the top of the stack • call m.iterationAdvance() (changing the nextDirection of m) • 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. • input.1 • input.2 • input.3 • input.4 • input.5 • input.6 • input.7 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:
• DOS executable • Linux (Intel) executable • MacOSX (Universal) executable 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: • location-proj1.h • maze-proj1.h • stack-proj1.h 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 turned in via the upload site before our class meeting on the due date. I will look over your code to make sure you have made appropriate progress on the project for that milestone. For each milestone you should create and upload a test driver that tests what you have written; in general this should be submitted as the “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 things that are not part of the current milestone. Milestones are 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.
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. The upload site will test with reasonablysized inputs that your program should be able to solve quickly.