Assignment 5 Solutions
Solution solveMaze.cc code:
/*******************************************************************
* Name: Brenda Student
* Date: 3/24/14
* Course: CSCI 132 Section 01
* Assignment: Assignment 5
* Instructor: Royden
* Program: solveMaze.cc
* Purpose: A program that creates a random acyclic maze and solves it
* recursively.
***************************************************************************/
#include "maze.h"
bool solve(Maze &, int, int);
bool isWallAbove(Maze &, int, int);
bool isWallBelow(Maze &, int, int);
bool isWalltoLeft(Maze &, int, int);
bool isWalltoRight(Maze &, int, int);
int main()
{
int width, height; //width and height of the maze
char answer; //answer to query about creating a new maze
cout << "Do you want me to solve a maze (y/n)? ";
cin >> answer;
while (answer == 'y') {
cout << "Enter number for width of maze: " ;
cin >> width;
cout << "Enter number for height of maze: ";
cin >> height;
Maze myMaze(width, height);
cout << "Maze to be solved: " << endl;
myMaze.print_maze();
if (!solve(myMaze, 0, 0)) {
cout << "Couldn't solve this maze!" << endl;
} // end if
cout << "Do you want me to solve another maze (y/n)? ";
cin >> answer;
} //end while
return 0;
} //end main
/*Recursively find a path through the maze to the end from position (x, y)*/
bool solve(Maze &theMaze, int x, int y) {
/*Pre: theMaze is an acyclic maze and x, y is the current position on a path attempting to solve it.
* Post: If a solution is found it is printed and the value true is returned. Otherwise the value
* false is returned. In both cases the current position stays at x, y. */
bool found_it = false; //records whether a solution was found
int value = theMaze.get_position(x, y);
if (value == 2) {
theMaze.print_maze();
return true;
} else if (value == 1) {
return false;
} else {
theMaze.set_position(x, y, 1);
if (!isWallAbove(theMaze, x, y)) {
found_it = solve(theMaze, x, y-1);
} //end if
if (!isWalltoLeft(theMaze, x, y) && !found_it) {
found_it = solve(theMaze, x-1, y);
} //end if
if(!isWallBelow(theMaze, x, y) && !found_it) {
found_it = solve(theMaze, x, y+1);
} //end if
if (!isWalltoRight(theMaze, x, y) && !found_it) {
found_it = solve(theMaze, x+1, y);
} //end if
theMaze.set_position(x, y, 0);
} //end outer if
return found_it;
} //end solve()
bool isWallAbove(Maze &theMaze, int x, int y) {
/*Post: returns true if there is a wall in theMaze directly above position x, y */
if(theMaze.is_horizontal_wall(x, y))
return true;
else
return false;
} //end isWallAbove()
bool isWallBelow(Maze &theMaze, int x, int y) {
/*Post: returns true if there is a wall in theMaze directly below position x, y */
if(theMaze.is_horizontal_wall(x, y+1))
return true;
else
return false;
} //end isWallBelow
bool isWalltoLeft(Maze &theMaze, int x, int y) {
/*Post: returns true if there is a wall in theMaze directly to the left of position x, y */
if(theMaze.is_vertical_wall(x, y))
return true;
else
return false;
} //end isWalltoLeft
bool isWalltoRight(Maze &theMaze, int x, int y) {
/*Post: returns true if there is a wall in theMaze directly to the right of position x, y */
if(theMaze.is_vertical_wall(x+1, y))
return true;
else
return false;
} //end isWalltoRight