title: Java 8-puzzle Depth first search issue with children nodes
body: <p>I am creating a depth first search algorithm which will ultimately be able to solve a simple 8 puzzle. I am able to read in a file and a goal state and set these variables accordingly.</p>
  
  <p>The main issue i am receiving is that when i get the children of the current node being evaluated, i am getting 2 "empty" values in my 8 puzzle, and i am also getting an index out of bounds exception.</p>
  
  <p>In order to get a child node for a given parent, i first must make a valid move then update the state of the child node to reflect the results of the valid move.</p>
  
  <p>In order to perform a move, i check if it is do-able(if i move left will it still be within the bounds of the puzzle), see posted code.</p>
  
  <p>It functions correctly for the first 2 moves, left and down as it correctly print the expected result.</p>
  
  <p>Below is the output of my current codes execution, you can see it correctly moves left and down, then it starts encountering errors.</p>
  
  <pre><code> Start state:
   120
   345
   678
  
   after moving left
   102
   345
   678
  
   Parent: [[C@1b845568
   after moving down
   125
   340
   678
  
   Parent: [[C@d032cf5
   after moving left
   102
   340
   678
  
   Parent: [[C@d032cf5
   after moving down
   125
   348
   670
  
   Parent:
   125
   340
   678
  
   after moving up
   125
   348
   670
  
   Parent: [[C@4b7c8f7f
   after moving left
   125
   304
   670
  
   Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
   at dcs.aber.ac.uk.puzzle.PuzzleBoard.swapValues(PuzzleBoard.java:193)
   at dcs.aber.ac.uk.puzzle.PuzzleBoard.moveUp(PuzzleBoard.java:142)
   at dcs.aber.ac.uk.puzzle.DFSSolver.addChildren(DFSSolver.java:155)
   at dcs.aber.ac.uk.puzzle.DFSSolver.search(DFSSolver.java:85)
   at dcs.aber.ac.uk.puzzle.DFSSolver.&lt;init&gt;(DFSSolver.java:27)
       at dcs.aber.ac.uk.puzzle.Driver.main(Driver.java:86)
  </code></pre>
  
  <p>As you can see, after the first two the rest of the printed states are incorrect. I will post my code to show how i handle the swapping and updating of the board to see if you can identify where the complication arises.</p>
  
  <pre><code>    public class Node  {
  
  
  
  private Node parent;
  private char[][] state = new char[3][3];
  private double cost; 
  private double heurCost; 
  private double funcCost; 
  private int depth;
  
  public Node() {
      parent = null;
      }
  
  public Node(Node parent) {
      this.parent = parent;
  
       for(int i = 0; i &lt; 3; i++){
          for(int j = 0; j&lt; 3; j++){
              state[i][j] = parent.getState()[i][j];
  
          }   
  
      } 
  } 
  
  
  public void setParent(Node parent) {
  
      this.parent = parent;
  
  
   }
  
  
  public char[][] getState() {
  
      return state;
  }
  
  public char[][] copyState(){
      char[][] a = new char[3][3];
  
      for(int i = 0; i &lt; 3; i++){
           for(int j = 0; j&lt; 3; j++){
               a[i][j] = state[i][j];
  
          }    
  
      } 
  
   return a;
  }
  
   } 
  
   public class PuzzleBoard {
  
  private  char[][] goalState;
  private char[][] currentBoard;
  private int emptyRow, emptyCol;
  private int outOfPlace;
  
  public PuzzleBoard(char[][] currentState, char[][] goal ){
  
  
      this.setCurrentState(currentState);
      this.setGoalState(goal);
      trackEmptySqaure();
  
  }
  
  public void setGoalState(char[][] goalState){
  
      this.goalState = goalState;
  
  }
  
  
  public void setCurrentState(char[][] currentState){
  
      this.currentBoard = currentState;
  
  }
  
  
  
  public char[][] getCurrentBoard() {
  
      return currentBoard;
  
  }
  
  public boolean checkIsGoal(char[][] board){
  
      for(int i = 0; i &lt; 9; i ++){
          for(int j = 0; j &lt; 3; j ++){
              if(!(goalState[i][j] != (board[i][j]))){
  
                  return false;
              }
          }
      }
      return true;
  }
  
  public void trackEmptySqaure() {
  
      for(int i = 0; i &lt; 3; i ++){
          for (int j = 0; j &lt; 3; j ++){
              if(currentBoard[i][j] == '0'){
                  emptyCol = j;
                  emptyRow = i;
              }
  
          }
      }
  
  }
  
  public int getemptyRow() {
      return emptyRow;
  
  }
  
  public int getemptyCol() {
      return emptyCol;
  
  }
  
  
  
  public Node moveLeft(Node parent){
      currentBoard = parent.copyState();
  
      Node result = new Node(parent);
  
      /* check you can move 'empty' left one space*/
      if(getemptyCol()  &gt; 0){
  
  
          swapValues(result.getState(),emptyRow, emptyCol, 1);
  
  
          return result;
      }
  
      return null;
  }
  public Node moveDown(Node parent){
      currentBoard = parent.copyState();
  
      Node result = new Node(parent);
  
      /* check you can move 'empty' down one space*/
      if(getemptyRow()  &lt; 2){
  
  
          swapValues(result.getState(),emptyRow, emptyCol,2);
  
          return result;
      }
  
      return null;
  }
  
  public Node moveUp(Node parent){
      currentBoard = parent.getState();
      Node result = new Node(parent);
  
  
      /* check you can move 'empty' up one space*/
      if(getemptyRow() &gt; 0){
  
  
          swapValues(result.getState(),emptyRow, emptyCol,2);
  
  
  
          return result;
      }
  
      return null;
  }
  
  public Node moveRight(Node parent){
      currentBoard = parent.getState();
      Node result = new Node(parent);
  
  
      /* check you can move 'empty' right one space*/
      if(getemptyCol()  &lt; 2){
  
  
          swapValues(result.getState(),emptyRow, emptyCol,2);
  
  
  
          return result;
      }
  
      return null;
  }
  
     public void swapValues (char[][] c,int x, int y, int method){
  
      char empty = '0';
      char swapValue = '0'; // should never be kept as 0
  
      if(method == 1){ // left
  
          swapValue= c[emptyRow][emptyCol -1];
          c[emptyRow][emptyCol] = swapValue;
          c[emptyRow][emptyCol -1] = empty;
          trackEmptySqaure();
  
  
      }
      else if(method == 2){ // down
  
          swapValue = c[emptyRow + 1][emptyCol];
          c[emptyRow][emptyCol] = swapValue;
          c[emptyRow + 1][emptyCol] = empty;
          trackEmptySqaure();
  
  
      }
      else if(method == 3){ // up
          swapValue = c[emptyRow -1][emptyCol];
          c[emptyRow][emptyCol] = swapValue;
          c[emptyRow -1][emptyCol] = empty;
          trackEmptySqaure();
  
  
      }
      else if(method == 4){// right
          swapValue = c[emptyRow][emptyCol + 1];
          c[emptyRow][emptyCol] = swapValue;
          c[emptyRow ][emptyCol + 1] = empty;
          trackEmptySqaure();
  
  
      }
  
  
  
  
  }
  public class DFSSolver {
  
  private ArrayList&lt;Node&gt; closed = new ArrayList&lt;Node&gt;();
  
  private Stack&lt;Node&gt; open = new Stack&lt;Node&gt;();
  
  private PuzzleBoard pb;
  
  private boolean solved;
  
  private int numberOfSteps;
  
  public DFSSolver(PuzzleBoard puzzle) {
  
      pb = puzzle;
      numberOfSteps = 0;
      solved = false;
      Node root = new Node();
      root.setState(pb.getCurrentBoard());
      addToOpen(root);
      checkIfSolved(root);
      search();
  
  }
  
  public boolean inOpenList(Node n){
  
      for(Node node: open){
          if(node.equals(n)){
              return true;
          }
  
      }
      return false;
  
  }
  
  public boolean inClosedList(Node n){
  
      for(Node node: closed){
          if(node.equals(n)){
              return true;
          }
  
      }
      return false;
  
  }
  
  
  public void addToOpen(Node n){
      open.push(n);
  }
  
  public void addToClosed(Node n){
      closed.add(n);
  
  }
  
  public Node popOpen(){
      return open.pop();
  }
  
  public void removeFromClosed(Node n){
  
      closed.remove(n);
  
  }
  
  
  
  public void search(){
  
      while(!solved){
  
          Node current = popOpen();
          if(current != null){
              if(!(inClosedList(current))){ // is it previously explored?
                  checkIfSolved(current);
                  addChildren(current);
                  numberOfSteps++;
  
              }
  
              addToClosed(current);
          }
      }
      System.out.println("No of steps: " + numberOfSteps);
  }
  
  public void checkIfSolved(Node curr) {
      char[][] goal = pb.getGoal();
      char[][] current = curr.getState();
      for(int i = 0; i &lt; 3; i ++){
          for(int j = 0; j &lt; 3; j ++){
              char c = current[i][j];
              char x = goal[i][j];
              if(c != x){
                  return;
              }
          }
      }
  
      solved = true;
  }
  
  
  public void addChildren(Node parent){
  
  
      Node newNode = new Node(parent);
  
  
  
      newNode = pb.moveLeft(parent);
  
      if(newNode != null){
          System.out.println("Parent: " + parent.getState().toString());
          System.out.println("atfer moving left");
          System.out.println(newNode.toString());
          addToOpen(newNode);
  
  
      }
  
      newNode = pb.moveDown(parent);
  
      if(newNode != null){
          System.out.println("Parent: " + parent.getState().toString());
          System.out.println("atfer moving down");
          System.out.println(newNode.toString());
          addToOpen(newNode);
  
  
      }
  
  
      newNode = pb.moveRight(parent);
  
      if(newNode != null){
          System.out.println("Parent: " + parent.getState().toString());
          System.out.println("atfer moving right");
          System.out.println(newNode.toString());
          addToOpen(newNode);
  
  
      }
  
  
      newNode = pb.moveUp(parent);
  
      if(newNode != null){
          System.out.println("Parent:\n " + parent.toString());
          System.out.println("atfer moving up");
          System.out.println(newNode.toString());
          addToOpen(newNode);
  
  
      }
  }
  </code></pre>