import java.io.*;
public class GridNode
{
  private int[][] state;
  private GridNode leftChild;
  private GridNode upChild;
  private GridNode rightChild;
  private GridNode downChild;
  
  // set state to newState and firstChild to newFirstChild and nextSibling to newNextSibling
   public GridNode(int[][] newState, GridNode newLeftChild, GridNode newUpChild, GridNode newRightChild, GridNode newDownChild)
   {
      setState(newState);
      setLeftChild(newLeftChild);
      setUpChild(newUpChild);
      setRightChild(newRightChild);
      setDownChild(newDownChild);
   } // end GridNode constructor
   
   // copy one state to another
   public static int[][] copy(int[][] a)
   {
      int[][] b = new int[a[0].length][a.length];
      for (int i = 0; i < a.length; i++)
          for (int j = 0; j < a[0].length; j++)
              b[i][j] = a[i][j];
     
      return b;
} // end copy
   
   public static GridNode copy(GridNode a)
   {
      GridNode b = a;
      return b;
   } // end copy
   
   // get current state
   public int[][] getState()
   {
      return state;
   } // end getState
   
   public void setState(int[][] newState)
   {
      state = newState;
   } // end setState
   
   // set leftChild
   public void setLeftChild(GridNode newLeftChild)
   {
      leftChild = newLeftChild;
   } // end setLeftChild
   
   // set UpChild
   public void setUpChild(GridNode newUpChild)
   {
      upChild = newUpChild;
   } // end setUpChild
   
   // set right child
   public void setRightChild(GridNode newRightChild)
   {
      rightChild = newRightChild;
   } // end setRightChild
   
   // set down child
   public void setDownChild(GridNode newDownChild)
   {
       downChild = newDownChild;
   } // end setDownChild;
   
   // get leftChild
   public GridNode getLeftChild()
   {
      return leftChild;
   } // end getLeftCHild
   
   // getUpChild
   public GridNode getUpChild()
   {
       return upChild;
   } // end getUpChild
  
   // get right child
   public GridNode getRightChild()
   {
      return rightChild;
   } // getRightChild;
   
   public GridNode getDownChild()
   {
      return downChild;
   } // end getDownChild
   
   // print the current state
   public void printNode()
   {
      for(int row = 0; row < 3; row++)
      {
        for(int col = 0; col < 3; col++)
          System.out.print(state[row][col] + "   ");
        
        System.out.println();
      } // end for
    } // end printNode
   
   // check to see if current state is equal to the goal state
   public boolean isEqual(int[][] state, int[][] goalState)
   {
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
            if (state[row][col] == goalState[row][col])
               continue;
            
            else
             return false;
         } // end for
      }  // end for
      return true;
   } // end isEqual
   
   // calculates h1(n)
   public int findHone(int[][] state, int[][] goalState)
   {
      int hOne = 0;
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
            if (state[row][col] != goalState[row][col] && state[row][col] != 0)
               hOne++;
            
            else
             continue;
         } // end for
      }  // end for
      return hOne;
   } // end findHone
   
   // find f(n) = g(n) + h(n)
   public int findF(int g, int h)
   {
      return g + h;
   } // end findF
   
   // check to see if it can move left
   public boolean canMoveLeft(int[][] state)
   {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
                tempPos = col;
         } // end for
      } // end for
      
      if (tempPos == 0)
        return false;
      else
       return true;
   } // end canMoveLeft
   
   // check to see if it can move up
   public boolean canMoveUp(int[][] state)
   {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
                tempPos = row;
         } // end for
      } // end for
      
      if (tempPos == 0)
        return false;
      else
       return true;
   } // end canMoveUp
   
   // check to see if it can move right
   public boolean canMoveRight(int[][] state)
   {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
                tempPos = col;
         } // end for
      } // end for
      
      if (tempPos == 2)
        return false;
      else
       return true;
   } // end canMoveRight
   
   // check to see if it can move down
   public boolean canMoveDown(int[][] state)
   {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
                tempPos = row;
         } // end for
      } // end for
      
      if (tempPos == 2)
        return false;
      else
       return true;
   } // end canMoveDown
   
    // move it left, the old one
   public void moveLeft(int[][] state)
   {
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
             {
                  state[row][col] = state[row][col-1];
                  state[row][col-1] = 0;
                  //printNode();
                  return;
             } // end if
         } // end for
      } // end for
   } // end moveLeft
   
   
   // move it Up
   public void moveUp(int[][] state)
   {
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
             {
                  state[row][col] = state[row-1][col];
                  state[row-1][col] = 0;
                 // printNode(state);
                  return;
             } // end if
         } // end for
      } // end for
   } // end moveUp
   
    // move it right
   public void moveRight(int[][] state)
   {
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
             {
                   state[row][col] = state[row][col+1];
                   state[row][col+1] = 0;
                  // printNode(state);
                   return;
             } // end if
         } // end for
      } // end for
   } // end moveRight
   
    // move it down
   public void moveDown(int[][] state)
   {
      //int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
         for (int col = 0; col < 3; col++)
         {
             if (state[row][col] == 0)
             {
                 state[row][col] = state[row+1][col];
                 state[row+1][col] = 0;
                // printNode(state);
                 return;
             } // end if
         } // end for
      } // end for
   } // end moveDown
   
} // end GridNode

import java.util.*;
public class NewMain
{
   private static int level;
   private static List tree = new LinkedList();
   
   private static int[][] goalState = {{7, 6, 4},
                        {8, 5, 2},
                        {1, 0, 3}
                       };
   
   
   // insert root and check if its goal
   static void insertRoot(GridNode root)
   {
     tree.add(0, root);
   } // end insertRoot
   
   // find smallest f(n)
   static int findF(List tree)
   {
      GridNode temp;
      int lowestF = 0;
      int tempLowestF = 0;
      int i = 0;
      while (i < tree.size())
      {
         temp = (GridNode) tree.get(i);
         tempLowestF = temp.findF(level, temp.findHone(temp.getState(), goalState)); 
          
         if (tempLowestF < lowestF)
           lowestF = tempLowestF;
         i++;
      }
      
      return lowestF;
   } // end findF
   
   // insert children
   static void insertChild(GridNode parent, GridNode child)
   {
      if (parent.canMoveLeft(parent.getState()))
      {
         child.setState(parent.copy(parent.getState()));
         child.moveLeft(child.getState());
         tree.add(child);
         parent.setLeftChild(parent.copy(child));
         System.out.println("The child is");
         child.printNode();
         System.out.println();
         System.out.println("the parent is");
         parent.printNode();
         level++;
      }  // end if
      
      
      if (parent.canMoveUp(parent.getState()))
      {
         child.setState(parent.copy(parent.getState()));
         child.moveUp(child.getState());
         tree.add(child);
         parent.setUpChild(child);
         System.out.println("The child is");
         child.printNode();
         System.out.println();
         System.out.println("the parent is");
         parent.printNode();
         level++;
      } // end else if
      
      else if (parent.canMoveRight(parent.getState()))
      {
         child.setState(parent.copy(parent.getState()));
         child.moveRight(child.getState());
         tree.add(child);
         parent.setRightChild(child);
          System.out.println("The child is");
         child.printNode();
         System.out.println();
         System.out.println("the parent is");
         parent.printNode();
         level++;
      } // end else if
      
      else if (parent.canMoveDown(parent.getState()))
      {
         child.setState(parent.copy(parent.getState()));
         child.moveDown(child.getState());
         tree.add(child);
         parent.setDownChild(child);
         System.out.println("The child is");
         child.printNode();
         System.out.println();
         System.out.println("the parent is");
         parent.printNode();
         level++;
      } // end else if
   } // end insertChild
   
   public static void main(String[] args)
   {
       int[][] initialState = {{7, 6, 4},
                             {8, 5, 2},
                             {1, 0, 3}
                            };
      
      GridNode parent = new GridNode(initialState, null, null, null, null);
      GridNode child = new GridNode(null, null, null, null, null);
      insertChild(parent, child);
      parent.getLeftChild().printNode();
      //insertChild(parent.getLeftChild(), child);
       //System.out.println(findF(tree));
      // insertChild(parent, child);
       //insertSibling(parent, child);
   } // end main
 
} // end NewMain