Recursive Algorithm for 2D maze?

Question

(This is not a duplicate) We have a 2D maze surrounded by X on all 4 sides and there are inner blocks too.
All these characters of the maze is stored in 2D array. The program must find the path from start 'S' to goal 'G'. For this, a boolean method called 'solve(int row, int col) is uses and is initialized with row and column index of 'S'. The algorithm must be recursive. It should return true if its able to find the path to 'G' and false other wise. Here's how I tried to approach this problem which shows "partial correct result".

public boolean solve(int row, int col) {
  char right = this.theMaze[row][col + 1];
  char left = this.theMaze[row][col - 1];
  char up = this.theMaze[row - 1][col];
  char down = this.theMaze[row + 1][col];
  if (right == 'G' || left == 'G' || up == 'G' || down == 'G') {
    return true;
  }
  System.out.println("position=>"+"("+row + ":" + col+")");
  if (right == ' ') {
    return solve(row,col+1);
  }
  if (down == ' ') {
    return solve(row+1,col);
  }
  if (left == ' ') {
    return solve(row,col-1);
  }
  if (up == ' ') {
    return solve(row-1,col);
  }
  return false;
}

Here is the output it solved :

   0 1 2 3 4 5 6 7 8 9 10 
0  X X X X X X X X X X X 
1  X X S X X X X X   X X 
2  X X   X X X X X   X X 
3  X X   X X X X X   X X 
4  X X   X X X X X   X X 
5  X X   X X X X X   X X 
6  X X   X X X X X   X X 
7  X X   X X X X X G X X 
8  X X               X X 
9  X X X X X X X X X X X 

position=>(1:2)
position=>(2:2)
position=>(3:2)
position=>(4:2)
position=>(5:2)
position=>(6:2)
position=>(7:2)
position=>(8:2)
position=>(8:3)
position=>(8:4)
position=>(8:5)
position=>(8:6)
position=>(8:7)
true

But when I place 'G' one step up (at 6,8). It shows stackOverflow error. The reason is because the recursion occurs between 2 points at this state (somehow just like indirect recursion).

How can I solve this problem. Is there anyway to tell the program to move up instead of down? Changing the position of conditional statements wont work though. And think a position that has more than one path to go but only one leads to 'G'. How to come back to initial position and try anther path ? Thanks in advance.

Update:

Here is a Github Repo link to the complete solution of this problem by me.

Solution 1

You could fill in an alternate symbol in the spaces you stepped through already so your program will know that it was there already.

Solution 2

In your present code there is a possibility that you return out false without looking at other connected positions.

You should look through other possibilities before returning out from the if condition.
Also, you should check whether the position has been visited to avoid infinite recursion.

Change your code to:

bool solved = false;
visited[row][col] = true;

if (right == ' ' && !visited[row][col+1]) {
    solved = solve(row,col+1);
}
if (down == ' ' && !solved && !visited[row+1][col]) {
    solved = solve(row+1,col);
}
if (left == ' ' && !solved && !visited[row][col-1]) {
    solved = solve(row,col-1);
}
if (up == ' ' && !solved !visited[row-1][col]) {
    solved = solve(row-1,col);
}
return solved;

Solution 3

You can use a DFS or BFS. The DFS is the easiest one. You simply make a recursion, navigate in all 4/8-directions and mark that place (X,Y) as visited. If it's you destiny 'G', return true otherwise continue.

Tips:

• Don't use the same matrix to read the map and mark it as visited, KISS
• You have to constantly check if you have discovered G. You can make this by return always FALSE or TRUE, or you can use a global variable.

If you have trouble implementing it try to google for some source code about this problems: http://en.wikipedia.org/wiki/Flood_fill

http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/