maze solve algorithm
hi guys,
i have a maze program that reads coordinates in from a file which is the path and then puts the walls up as well. this is all done through a 2d array. i now need a recursive solution to solve the maze.
at the moment i have this
staticvoid solve(int x ,int y)
{
while(currentX != goalX || currentY != goalY)
//not that currentX and currentY are the current postions of x and y
//goalX and goalY are where the goal postions are on the map
solve(currentX-1, currentY);
currentX = x; currentY = y;
solve(x-1, y);
solve(x+1, y);
solve(x, y-1);
solve(x, y+1);
}
what this does is to move eithier the x or y coordinate up down left or right.
please not i cannot move south-east or anything like that for example.
when i try to run it i get a stackoverflow exception.
i am a little unsure of how i am to make sure this exception is not thrown and how to finish this algorithm.
5
5
1 1
start
1 2
1 3
2 3
3 3
goal
this is the path of the maze which is stored in a standard txt file.
anyhelp more than welcome
Solving maze is one of best ways to understand the concept of recursion.The code is given below. Let's give a try now. If you can not figure out the recursion, please use a debugger to step through the program:
//===========================================================
// Attempts to recursively traverse the maze. It inserts
// special characters indicating locations that have been
// tried and that eventually become part of the solution.
//===========================================================
public boolean solve (int row, int column) {
boolean done = false;
if (valid (row, column)) {
grid[row][column] = 3; // cell has been tried
if (row == grid.length-1 && column == grid[0].length-1)
done = true; // maze is solved
else {
done = solve (row+1, column); // down
if (!done)
done = solve (row, column+1); // right
if (!done)
done = solve (row-1, column); // up
if (!done)
done = solve (row, column-1); // left
}
if (done) // part of the final path
grid[row][column] = 7;
}
return done;
} // method solve
//===========================================================
// Determines if a specific location is valid.
//===========================================================
private boolean valid (int row, int column) {
boolean result = false;
// check if cell is in the bounds of the matrix
if (row >= 0 && row < grid.length &&
column >= 0 && column < grid[0].length)
// check if cell is not blocked and not previously tried
if (grid[row][column] == 1)
result = true;
return result;
} // method valid
Sample Input:
int[][] grid = {{1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
Output:
1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111
Maze solved! <<buteForce>>
7770110001111
3077707771001
0000707070300
7770777070333
7070000773003
7077777703333
7000000000000
7777777777777
Press any key to continue...
==================Output Ends Here==================
Good Luck!
Regards
<<buteForce>>
