title: Java backtracking in a maze
body: <p>I'm writing a program that will essentially have an object searching for a "pig" by using java backtracking. As of now, I have the pig moving and searching but it's unable to actually "backtrack".  I'm just completely lost on how to actually go about implementing the code for that segment, but I do know that you would use pathIndex-- to decrease the path length. Any help on how to go about doing this would be extremely helpful.</p>
  
  <pre><code>public class MazeWalker {
      /**
       * The possible states of the current "walk" through a maze.
       */
      public enum WalkerState {
          /**
           * Indicates that the maze walker has reached its assigned destination.
           */
          THERE_ALREADY,
  
          /**
           * Indicates that the maze walker has concluded that it is impossible to
           * reach its destination.
           */
          IMPOSSIBLE_TO_GET_THERE,
  
          /**
           * Indicates that the maze walker would like to move left.
           */
          MOVE_LEFT,
  
          /**
           * Indicates that the maze walker would like to move up.
           */
          MOVE_UP,
  
          /**
           * Indicates that the maze walker would like to move right.
           */
          MOVE_RIGHT,
  
          /**
           * Indicates that the maze walker would like to move down.
           */
          MOVE_DOWN
      }
  
      /**
       * Initializes the MazeWalker, providing it with the maze to use and the
       * walker's destination.
       */
      public MazeWalker(Maze maze, int destinationX, int destinationY) {
          this.maze = maze;
          this.destinationX = destinationX;
          this.destinationY = destinationY;
  
          // The path stack starts out empty.
          path = new WalkerState[this.maze.getMazeWidth() * this.maze.getMazeHeight()];
          pathIndex = -1;
  
          // The "been-there" array starts off completely clear.
          beenThere = new boolean[this.maze.getMazeHeight()][this.maze.getMazeWidth()];
          for (int row = 0; row &lt; beenThere.length; row++) {
              for (int column = 0; column &lt; beenThere[row].length; column++) {
                  beenThere[row][column] = false;
              }
          }
      }
  
      /**
       * Takes a step toward reaching the given destination from the given current
       * location, and returns either the direction of the next step, whether or
       * not that destination has been reached, or whether that destination is
       * impossible to reach.
       */
      public WalkerState areWeThereYet(int currentX, int currentY) {
        ///currentWalkerState =
  
        if ((currentX == destinationX) &amp;&amp; (currentY == destinationY)) {
          return WalkerState.THERE_ALREADY;
  
        } else if (maze.getLocation(currentX, currentY).getRight().isOpen() &amp;&amp; !beenThere[currentY][currentX + 1]) {
  
        ///  currentWalkerState = WalkerState.MOVE_RIGHT;
          pathIndex++;
          path[pathIndex] = WalkerState.MOVE_RIGHT;
          return WalkerState.MOVE_RIGHT;
  
        } else if (maze.getLocation(currentX, currentY).getLeft().isOpen() &amp;&amp; !beenThere[currentY][currentX - 1]) {
  
        ///  currentWalkerState = WalkerState.MOVE_LEFT;
          pathIndex++;
          path[pathIndex] = WalkerState.MOVE_LEFT;
          return WalkerState.MOVE_LEFT;
  
        } else if (maze.getLocation(currentX, currentY).getAbove().isOpen() &amp;&amp; !beenThere[currentY + 1][currentX]) {
  
        ///  currentWalkerState = WalkerState.MOVE_UP;
          pathIndex++;
          path[pathIndex] = WalkerState.MOVE_UP;
          return WalkerState.MOVE_UP;
  
        } else if (maze.getLocation(currentX, currentY).getBelow().isOpen() &amp;&amp; !beenThere[currentY - 1][currentX]) {
  
        ///  currentWalkerState = WalkerState.MOVE_DOWN;
          pathIndex++;
          path[pathIndex] = WalkerState.MOVE_DOWN;
          return WalkerState.MOVE_DOWN;
        }
          ///Returning 6 different values///
          ///MazeWalker is the thing thats moving///
          ///MazeWalker is initialized with a Maze Object with the desired destination coordinates///
          ///Steve's initial location is sx, sy///
          ///Pig's location is px, py///
  
        return WalkerState.IMPOSSIBLE_TO_GET_THERE;
      }
  
      /**
       * Returns a representation of the locations which the walker has visited.
       * The 2D array's dimensions should correspond to those of the walker's
       * assigned maze.
       */
      public boolean[][] getBeenThere() {
          return beenThere;
      }
  
      /**
       * Returns the current path taken by the walker.
       */
      public WalkerState[] getCurrentPath() {
          WalkerState[] currentPath = new WalkerState[pathIndex + 1];
          for (int i = 0; i &lt; pathIndex + 1; i++) {
              currentPath[i] = path[i];
          }
          return currentPath;
      }
  
      /**
       * The data structure for maintaining the current path.
       */
      private WalkerState[] path;
  
      /**
       * The index for the current node in the path.
       */
      private int pathIndex;
  
      /**
       * The data structure for keeping track of "passed" squares.
       */
      private boolean[][] beenThere;
  
      /**
       * The maze that is being walked.
       */
      private Maze maze;
  
      /**
       * The x-coordinate of the walker's destination.
       */
      private int destinationX;
  
      /**
       * The y-coordinate of the walker's destination.
       */
      private int destinationY;
  }
  </code></pre>