Starting from:
$24.99
PROJECT 1: MAZE SOLVER
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 0Your 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 specificationInput 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
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 0Your 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 specificationInput 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
1 file (361.2KB)
