title: Recursive Algorithm for 2D maze?
body: <p>(This is not a duplicate) We have a 2D maze surrounded by X on all 4 sides and there are inner blocks too. <br> 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".</p>
  
  <pre><code>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=&gt;"+"("+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;
  }
  </code></pre>
  
  <p>Here is the output it solved : </p>
  
  <pre><code>   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=&gt;(1:2)
  position=&gt;(2:2)
  position=&gt;(3:2)
  position=&gt;(4:2)
  position=&gt;(5:2)
  position=&gt;(6:2)
  position=&gt;(7:2)
  position=&gt;(8:2)
  position=&gt;(8:3)
  position=&gt;(8:4)
  position=&gt;(8:5)
  position=&gt;(8:6)
  position=&gt;(8:7)
  true
  </code></pre>
  
  <p>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). </p>
  
  <p>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.</p>
  
  <p><strong>Update:</strong></p>
  
  <p><a href="https://github.com/prashantghimire/2D-Maze-Recursive-Solution-using-Java" rel="nofollow noreferrer"><strong>Here is a Github Repo link to the complete solution of this problem by me.</strong></a></p>