import java.util.*;
public class Cain {
 
     static List values;
    /**
     * @param args the command line arguments
     */
 
 
        private static String Board [][] = {{ " ", " ", " "},
                                            { " ", " ", " "},
                                            { " ", " ", " "}};
                                 //////RESETS BOARD AFTER GAME
        private static String BoardB [][] = {{ " ", " ", " "},
                                             { " ", " ", " "},
                                             { " ", " ", " "}};
        private static String BoardC [][] = {{ " ", " ", " "},
                                             { " ", " ", " "},
                                             { " ", " ", " "}};
        private static String BoardD [][] = {{ " ", " ", " "},
                                             { " ", " ", " "},
                                             { " ", " ", " "}};
        private static String BoardE [][] = {{ " ", " ", " "},
                                             { " ", " ", " "},
                                             { " ", " ", " "}};
 
 
    /////VALUES OF BEST SPOTS TO PLAY IN FOR THE GAMES/////////////////
    /////////////DISPLAYS BOARD//////////////////////
    public static void displayBoard (String z[][])
{
System.out.println(" "+z[0][0]+" | "+z[0][1]+" | "+z[0][2] + " | ");
System.out.println(" --------------");
System.out.println(" "+z[1][0]+" | "+z[1][1]+" | "+z[1][2] + " | ");
System.out.println(" --------------");
System.out.println(" "+z[2][0]+" | "+z[2][1]+" | "+z[2][2] + " | ");
System.out.println(" --------------");
 
}
    public static boolean GoalState(String z[][])
    {
        if(
        z[0][0].equals("0")&&
        z[0][1].equals("1")&&
        z[0][2].equals("2")&&
        z[1][0].equals("3")&&
        z[1][1].equals("4")&&
        z[1][2].equals("5")&&
        z[2][0].equals("6")&&
        z[2][1].equals("7")&&
        z[2][2].equals("8"))
 
            return true;
        else
            return false;
    }
 
    public static void main(String[] args)
    {
        Random randomGenerator = new Random();
 
        int count = 0;
        String Blank = " ";
        int avail  = 0;
        int avail2 = 0;
        int posv   = 0;
        int posh   = 0;
        int posv2  = 0;
        int posh2  = 0;
        int posv3  = 0;
        int posh3  = 0;
        int posv4  = 0;
        int posh4  = 0;
        int posv5  = 0;
        int posh5  = 0;
        int mov    = 0; int mov1    = 0; int mov2    = 0; int mov3    = 0; int mov4    = 0;
        int mov5    = 0; int mov6    = 0; int mov7    = 0; int mov8    = 0;
        boolean possible = false;
        int Rand = 0;
        int Rand1 = 0;
        int Rand2 = 0;
        int Rand3 = 0;
        int Random = 0;
        int temp = 0;
        int temp2 = 0;
        int posh5B = 0;
        int posv5B = 0;
        int posh5C = 0;
        int posv5C = 0;
        int posh5D = 0;
        int posv5D = 0;
        int posh5E = 0;
        int posv5E = 0;
        String [] Array = new String [8];
        String This = " ";
        String This2= " ";
        String This3= " ";
        ArrayList arrayList = new ArrayList();
        boolean Goal = false;
        HashMap  hashm = new HashMap ();
 
        Board[0][0] = ("2");   BoardB[0][0] = ("3"); BoardC[0][0] = ("3"); BoardD[0][0] = ("3");  BoardE[0][0] = ("3");
        Board[0][1] = ("1");   BoardB[0][1] = ("0"); BoardC[0][1] = ("0"); BoardD[0][1] = ("0");  BoardE[0][1] = ("0");
        Board[0][2] = ("0");   BoardB[0][2] = ("5"); BoardC[0][2] = ("5"); BoardD[0][2] = ("5");  BoardE[0][2] = ("5");
        Board[1][0] = ("3");   BoardB[1][0] = ("6"); BoardC[1][0] = ("6"); BoardD[1][0] = ("6");  BoardE[1][0] = ("6");
        Board[1][1] = ("4");   BoardB[1][1] = ("1"); BoardC[1][1] = ("1"); BoardD[1][1] = ("1");  BoardE[1][1] = ("1");
        Board[1][2] = ("5");   BoardB[1][2] = ("7"); BoardC[1][2] = ("7"); BoardD[1][2] = ("7");  BoardE[1][2] = ("7");
        Board[2][0] = ("6");   BoardB[2][0] = ("4"); BoardC[2][0] = ("4"); BoardD[2][0] = ("4");  BoardE[2][0] = ("4");
        Board[2][1] = ("7");   BoardB[2][1] = ("2"); BoardC[2][1] = ("2"); BoardD[2][1] = ("2");  BoardE[2][1] = ("2");
        Board[2][2] = ("8");   BoardB[2][2] = ("8"); BoardC[2][2] = ("8"); BoardD[2][2] = ("8");  BoardE[2][2] = ("8");
 
     Scanner choice = new Scanner(System.in);
  //   while(Goal == false)
 
     while(GoalState(Board) == false)
     {
         if(GoalState(Board) == true)
             displayBoard(Board);
 
        avail    = 2;
        avail2 = 2;
        for(int i =0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                Array[i] = Board[i][j];
                arrayList.add(Array[i]);
       //         System.out.println("Array is drum roll " + Array[i]);
                if(BoardB[i][j].equals("0"))
                { posh5B  = i;
                  posv5B = j;
                }
                if(BoardC[i][j].equals("0"))
                { posh5C  = i;
                  posv5C = j;
                }
                if(BoardD[i][j].equals("0"))
                { posh5D  = i;
                  posv5D = j;
                }
                if(BoardE[i][j].equals("0"))
                { posh5E  = i;
                  posv5E = j;
                }
                if(Board[i][j].equals("0"))
                { posh5  = i;
                  posv5 = j;
             //   displayBoard(Board);
                  System.out.println ("KA CHING AL LING A LING BLING BLING ");
                 //MOVE LEFT
                 if(j  > 0 )
                 {
     //                System.out.println("LEFTMOVE " + i + " " + (j-1));
                      mov = i; mov2 = j-1;
                      avail = i; avail2 = j-1;
                  //    al.add(This);
                 //     String TempB = BoardB[avail][avail2];
                 //     BoardB[avail][avail2] = BoardB[posh5B][posv5B];
                 //     BoardB[posh5B][posv5B]  = TempB;
 
                      //       displayBoard(BoardB);  //*/
                 }
                 // MOVE DOWN
                 if(i >= 0 && i < 2)
                 {
       //              System.out.println("DOWNMOVE " + (i+1)  + " " + j );
                     mov3 = i+1; mov4 = j;
                /*     avail = mov3; avail2 = mov4;
 
                      String TempC = BoardC[avail][avail2];
                      BoardC[avail][avail2] = BoardC[posh5C][posv5C];
                      BoardC[posh5C][posv5C]  = TempC;
                      displayBoard(BoardC);//*/
 
                 }
                 // MOVE RIGHT\
                 if(j == 1 || j == 0)
                 {
      //               System.out.println("RIGHTMOVER " +i + " " + (j+1));
                     mov5 = i; mov6 = j+1;
                    /* avail = mov5; avail2 = mov6;
 
                      String TempD = BoardD[avail][avail2];
                      BoardD[avail][avail2] = BoardD[posh5D][posv5D];
                      BoardD[posh5D][posv5D]  = TempD;
                      displayBoard(BoardD);//*/
                 }
                 // MOVE UP
                 if(i == 1 || i == 2)
                 {
       //              System.out.println("UPMOVE " + (i-1)  + " " + j);
                     mov7 = i-1; mov8 = j;
/*                      avail = mov7; avail2 = mov8;
 
                      String TempU = BoardE[avail][avail2];
                      BoardE[avail][avail2] = BoardE[posh5E][posv5E];
                      BoardE[posh5E][posv5E]  = TempU;
                      displayBoard(BoardE);//*/
                 }
 
                }
            }
        }
                if(mov  + mov2 !=0)
                Rand = 1;
                if(mov3 + mov4 !=0)
                Rand1 = 2;
                if(mov5 + mov6 !=0)
                Rand2 = 3;
                if(mov7 + mov8 !=0)
                Rand3 = 4;
 
                int randomInts = randomGenerator.nextInt(4);
                int randoms    = randomGenerator.nextInt(5);
                int randomia   = randomGenerator.nextInt(5);
 
                randomInts +=1;// ((randoms + randomia)/3) +1;
             //   System.out.println("Random no is " + randomInts);
 
                 if(randomInts == Rand)
                 {
                   avail = mov; avail2 = mov2;
                 }
                 else if(randomInts == Rand1)
                 {
                   avail = mov3; avail2 = mov4;
                 }
                 else if(randomInts == Rand2)
                 {
                     avail = mov5; avail2 =  mov6;
                 }
                 else if(randomInts == Rand3)
                 {
                     avail = mov7; avail2 =  mov8;
                 }
                 displayBoard(Board);
 
                 System.out.println(" ");
         count +=1;
//hm.put("one",new Integer(1));
   // System.out.println("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" + hm.get(count-1));
     //    if(count/9 == 0)
           //  al = null;
         //if(count > 3){
         String Temp = Board[avail][avail2];
         Board[avail][avail2] = Board[posh5][posv5];
         Board[posh5][posv5]  = Temp;
             Goal = true;
       //  }
 
 System.out.println(" a " + arrayList );
hashm.put(count, arrayList);
//hashm.get(2);
 
 System.out.println(" The hash isst " + hashm);
// System.out.println(" HASSS IS    " + hashm.get(1));
// System.out.println(" The hash is " + hm);
 arrayList.clear();//*/
 
         }
//System.out.println(" The hash is " + hashm);
    }
 
 
    }