package runs;

//8數碼類
class Eight{
     int e[][] = {{0,2,3},{1,8,4},{7,6,5}};   //默認的起始狀態
     int faX ,faY;                      //保存父狀態中0的位置
     int f;                            //估價函數值
     Eight former ;            

 
     public Eight(){
          faX = -1;
          faY=-1;
          f=-1;
          former = null;
     }

     public Eight(Eight other){
        for(int i = 0; i<3; i++)
           for(int j=0 ;j<3; j++){
              e[i][j] = other.e[i][j];
            }
        this.faX = other.faX;
        this.faY = other.faY;
        this.f = other.f;
        this.former = other.former;
     }

     public void print()
     {
       for(int i1 = 0;i1<3;i1++)
          for(int j1=0;j1<3;j1++){
             System.out.print(e[i1][j1]);
             if(j1==2)
             System.out.println();
          }
       System.out.println();
     }

     public void listAll( Eight e ){
       e.print();
         while( e.former != null ){
               e.former.print();
              e = new Eight(e.former);    
         }
         return ;
     }
}

class Queue extends Object{ //隊列類
    private int size = 0;
    Eight qe[] = new Eight[100];

    public void print(){
       for(int i=0;i<size;i++)
          qe[i].print();
    }

    public void addElement(Eight e){
       qe[size] = e;
       size++;
    }

    public boolean contains(Eight e){
       if( size == 0 )
          return false;
       else{
          for(int i=0;i<size;i++){
          if(qe[i].equals(e))
          return true;
          }
       }
       return false;
    }

    public boolean isEmpty(){
        if (size == 0) 
           return true;
        else return false;
    }

    public Eight elementAt(int index){
        return qe[index];
    }

    public void setElementAt( Eight e,int index ){
        qe[index] = e;
   }

   public int size(){
       return size;
   }

   public int indexOf (Eight e) {
       for (int i = 0; i < size; i++){
          if (qe[i].equals( e ))
             return i;
       }
       return -1;
   }

   public void removeFirst( ){
       for(int i=0;i<size;i++){
          qe[i] = qe[i+1];
       }
       size--;
   }

   public void remove( Eight e ){
      for( int i = 0; i < size; i++ ){
         if( qe[i].equals( e ))
           qe[i] = null;
      }
      size--;
   }


   public void removeAllElements(){
       for (int i = 0; i < size; i++)
           qe[i] = null;
       size = 0;
   }

}

//算法實現類
public class Asearch{
    static int dest[][] = {{1,2,3},{8,0,4},{7,6,5}};
    static void Swap(Eight ee,int i,int j,int m,int n){
     int temp;
        temp = ee.e[i][j];
        ee.e[i][j] = ee.e[m][n];
        ee.e[m][n] = temp;
     }


    static int compare(Eight a){
        int h =0,i,j;
        for(i=0;i<3;i++)
        for(j=0;j<3;j++){
           if(a.e[i][j]!=dest[i][j])
              h++;
        }
        return h;
    }
 
    //生成子狀態
    static Queue born(Eight e){
        int m=1,n=1,i=0,j=0;
        boolean flag = true;
        Queue sons = new Queue();
        for(i=0;i<3&&flag;i++)
           for(j=0;j<3&&flag;j++){
              if(e.e[i][j]==0){
                 flag=false;
                 break;
              }
           }
     
        i--;
        if(i-1>=0){   ///up
           m=i-1;
           if(m!=e.faX){
             Swap(e,m,j,i,j);
             e.print();
             Eight son1 = new Eight(e);
             son1.faX = i;
             son1.faY = j;
             son1.former = e;
             sons.addElement(son1);
             Swap(e,i,j,m,j);
            // son1.former = e;

           }
        }
        if(i+1<3){/////down
           m=i+1;
           if(m!=e.faX){
             Swap(e,m,j,i,j);
               e.print();
             Eight son2 = new Eight(e);
             son2.faX = i;
             son2.faY = j;
             son2.former = e;
             sons.addElement(son2);
             Swap(e,i,j,m,j);
           }
        }
        if(j-1>=0){////left
          n=j-1;
          if(n!=e.faY){
            Swap(e,i,n,i,j);
           e.print();
            Eight son3 = new Eight(e);
            son3.faX = i;
            son3.faY = j;
            son3.former = e;
            sons.addElement(son3);
            Swap(e,i,j,i,n);
          }
        }
        if(j+1<3){////right
          n=j+1;
          if(n!=e.faY){
             Swap(e,i,n,i,j);
             e.print();
             Eight son4 = new Eight(e);
             son4.faX = i;
             son4.faY = j;
             son4.former = e;
             sons.addElement(son4);
             Swap(e,i,j,i,n);
          }
       }
       return sons;
    }
    public static void main(String[] args){
        int depth=0;      //深度
        Eight n = new Eight() ;
        Eight temp1 = new Eight() , temp2 = new Eight() ;
        //open表
        Queue open = new Queue();
        //closed表
        Queue closed = new Queue();
        //保存子狀態的表
        Queue son = new Queue();
        open.addElement(n);

        while(!open.isEmpty()){
            n= open.elementAt(0);
            open.removeFirst( );
            if(compare(n)==0){
              n.listAll(n);
              System.out.println("Success!");
              return;
            }
            son = born(n);
            depth++;
            int count = son.size(); 

            if(count==0)
               continue;
            else 
               for(int t=0;t<count;t++){
                  temp1 = son.elementAt(t);
                  if(!open.contains(temp1)&&!closed.contains(temp1)){
                    temp1.f = depth + compare(temp1);
                    open.addElement(temp1);
                  }
                  else if(open.contains(temp1)){
                      temp1.f = depth + compare(temp1);
                      int pos = open.indexOf(son.elementAt(t));
                      temp2 = open.elementAt(pos);
                      if(temp1.f<temp2.f){
                        open.setElementAt(temp1,pos);
                      }
                  }
                  else if(closed.contains(temp1)){
                     temp1.f = depth + compare(temp1);
                     int pos = closed.indexOf(temp1);
                     temp2 = closed.elementAt(pos);
                     if( temp1.f<temp2.f ){
                        closed.remove(son.elementAt(t));
                        open.addElement(temp1);
                     }
                  }
        }//end for
        closed.addElement(n);
        for(int i=open.size()-1;i>0;i--)
           for(int j=0;j<i;j++){
              temp1 = (Eight)open.elementAt(j);
              temp2 = (Eight)open.elementAt(j+1);
              if(temp1.f>temp2.f){
                Eight tq=new Eight();
                tq = open.elementAt(j);
                open.setElementAt(open.elementAt(j+1),j);
                open.setElementAt(tq,j+1);
              }
           }
        }//end while
        System.out.println("Fail!");
        return;
        }//end main
     }