title: Solving a maze using stacks
body: <p>I created two stacks. One for the path the other for spots I already searched. Ideally I would check to see if the searched path contains the next spot in a direction. If it does it checks another direction.</p>
  
  <p>Sample maze</p>
  
  <p>0 1 0 1 0</p>
  
  <p>0 0 0 1 0</p>
  
  <p>0 1 0 0 0</p>
  
  <p>0 1 0 1 1</p>
  
  <p>0 1 0 0 0</p>
  
  <p>My algorithm seems to get stuck between 2,3 and 2,4. Never explores 1,4 or 0,4. I see it keep bouncing between 2,3 and 2,4 in an infinite loop. So it seems my searched.contains() is not functioning properly. Any suggestion to fix my searched stack? Ideally, when I run my code. I want it to check East, South, west then North has already been searched or not. If all points have been checked it will pop the last position from my path stack using current= path.pop inside the while loop and repeat.</p>
  
  <p>Position is a custom class. I have considered adding a previous position variable to the constructor in the position class but seems to not to be needed if I can get my path stack to work. If I am wrong on this please let me know.</p>
  
  <pre><code>class Position{
  
  
  public int i;     //row
  public int j;     //column
  public char val;  //1, 0, or 'X'
  
  
  // reference to the previous position (parent) that leads to this position on a path
  Position parent;
  
  Position(int x, int y, char v){
      i=x; j = y; val=v;
  }
  
  Position(int x, int y, char v, Position p){
      i=x; j = y; val=v;
      parent=p;
  }
  
  @Override
  public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + i;
      result = prime * result + j;
      result = prime * result + ((parent == null) ? 0 : parent.hashCode());
      result = prime * result + val;
      return result;
  }
  
  @Override
  public boolean equals(Object obj) {
      if (this == obj)
          return true;
      if (obj == null)
          return false;
      if (getClass() != obj.getClass())
          return false;
      Position other = (Position) obj;
      if (i != other.i)
          return false;
      if (j != other.j)
          return false;
      if (parent == null) {
          if (other.parent != null)
              return false;
      } else if (!parent.equals(other.parent))
          return false;
      if (val != other.val)
          return false;
      return true;
  }   
  </code></pre>
  
  <p>}</p>
  
  <pre><code>public static Position [] stackSearch(char [] [] maze){
  //todo: your path finding algorithm here using the stack to manage search list
  //your algorithm should modify maze to mark positions on the path, and also
  //return array of Position objects coressponding to path, or null if no path found
   ArrayDeque &lt;Position&gt; path = new ArrayDeque&lt;Position&gt;();
   ArrayDeque &lt;Position&gt; searched = new ArrayDeque&lt;Position&gt;();
  
  
      //creates position object
      Position start = new Position(0,0,'0');
      Position current;
      Position north,south, east, west;
  
      int i = 0; int j = 0;
      //push (0,0) onto stack
      path.push(start);
      searched.push(start);
      while(!path.isEmpty()){
          current=path.pop();
          i=current.i;
          j=current.j;
          if(i==maze.length-1 &amp;&amp; j==maze.length-1 &amp;&amp;  maze[i][j]=='0'){
               Position[] trail= new Position [path.size()];
              while(!path.isEmpty()){
                  for(int k=0; k&lt;path.size();k++){
                  trail[k]=path.pop();
              }
                  return trail;
          }
      }
          System.out.println(i +"," +j);
  
          //check east.
          east= new Position(i,j+1,'0');
          south= new Position(i+1,j,'0');
          west= new Position(i,j-1,'0');
          north= new Position(i-1,j,'0');
          if (j+1 &gt;= 0 &amp;&amp; j+1 &lt; maze.length  &amp;&amp; maze[i][j+1] == '0' &amp;&amp; searched.contains(east)==false)
          {
  
  
                  searched.push(east);
                  path.push(current);
                  path.push(east);
  
  
  
  
          }
          //check south, add its position to the list.
  
          else if (i+1 &gt;= 0 &amp;&amp; i+1 &lt; maze.length &amp;&amp;  maze[i+1][j] == '0' &amp;&amp; searched.contains(south)==false)
          {
  
  
                  searched.push(south);
                  path.push(current);
                  path.push(south);
  
  
          }
        //check west.
  
           else if (j-1 &gt;= 0 &amp;&amp; j-1 &lt; maze.length  &amp;&amp; maze[i][j-1] == '0' &amp;&amp; searched.contains(west)==false)
          {
  
  
                  searched.push(west);
  
  
                  path.push(current);
                  path.push(west);
  
          }              
          //check north
  
           else if (i-1 &gt;= 0 &amp;&amp; i-1 &lt; maze.length &amp;&amp;  maze[i-1][j] == '0' &amp;&amp; searched.contains(north)==false)
          {
  
  
                  searched.push(north);
                  path.push(current);
                  path.push(north);
  
  
          }
  
     }
  return null;
  </code></pre>
  
  <p>}</p>