I need help writing the recursive method to traverse a maze in Java, I really do
ID: 3624194 • Letter: I
Question
I need help writing the recursive method to traverse a maze in Java, I really don't even know where to start I'm pretty terrible at recursion. the Method needs to go through the maze and replace all the open spaces with the number 3 and then when it gets to the bottom right corner replace it with a 7, and then change all the 3's in the correct path to 7's.Here's hows its supposed to work:
1. If the indicated location has not been visited before(doesn't contain 3),is not outside the bounds of the array, or does not contain a wall, we mark the current element as visited.
2. If we are the in the LAST element in the array(row,column),then we are done,and we mark the cell as being part of the solution by storing '7',and finally the method should exit returning true.
3. Else
a. We move down one element
b. If the previous call was not "done" , try to move one element to the left
c. If the previous call was not done, try to move one element up.
d. if not done, try moving one element to the right.
Here's some extra information more detailed about how it works:
Suppose the "maze" is represented as a 15 x 15 element character array.(Can be of any size). Each element in the array will hold either a '1' or a '0'. A "1" indicates an empty pathway in the maze; a "0" indicates a wall.(Also must work for letters). The entry into the maze is through element[0,0], and the exit is through element[14,14] in this example.
Write a recursive method that receives two integer values, a "row/column" pair that represents your current location in the maze. When the method is called for the first time it will receive the pair[0,0]. The traversal is successful when the end of the array is reached, which is when the method receives the pair [14,14]. When the end of the maze is reached, your method should return TRUE. It should return FALSE, if a move runs into a wall, a square that has already been visited, or the row/column pair outside the bounds of the array. As we traverse the maze, we mark each cell visited, by using a '3', finally the correct path through the maze, should be marked by storing a '7' in the array elements.
Once in the maze, we mark the cell as visited, storing a '3'. Next you can only move up,down,left or right, as long as you don't run into a "wall" or outside the boundaries of the array.Once the end of the maze is reached, we want to set every cell in the correct path to 7, to indicate that it is part of the solution. So once the end is reached, as the last step in the recursive function, if it is "done" store 7 in the current element and exit returning true. Each of the active recursive calls will in turn place a 7 in each of the elements pointed to by the tow/column pair they received.
Explanation / Answer
It's hard to help you, since you didn't post any code. All you have to do is to understand the recursion, because this is the hardest part. I would recommend to start with writting methods for moving (just moving) in the maze in any direction(let's call the moveUp(),moveDown(),moveLeft(),moveRight()). Before making the move, remember to check if the move is valid (if there is a wall, or if there is the end of the maze etc.) - that's gonna be another method, let's say isMoveValid(). Once you have that, write the method that will check if the move that you just made is the winning one, let's say isWin(). I would recommend to put isWin method on the end of move() method. Then the recursion method that will solve the maze should look like this:
bool solveMaze(){
if (!isMoveUpValid && isMazeSolved())//in other words, if moving up not is avaiable or the maze is already solved
{ //,then don't do anything in up direction
moveUp();//let's move up
solveMaze();//call the recursion method again
if (isMazeSolved())//this method should return true if the maze was solved
{
return true;
}
goBackFromUp(); //this method will have to do the opposite of moveUp() method (it has to make a move from up to down (you don't have to check if it's a vaild move)
}
//do the same if statement for moving down
//the same if for moving right
//the same for moving left
return false;
}
That's pretty much it. Of course in your solution, remember to implement the numbers that will indicate your current position in maze so each method in above will have to take two integers and will look, for example like this solveMaze(int row,int col);
If you have any futher question, ask. And next time, post the code you already have!
I know it is unorganized, but I hope this help at least a bit.