import java.util.Scanner;
import java.io.*;
class EightCode{ 

int e[][] = {{2,8,3},{1,0,4},{7,6,5}}; //初始狀態(tài) 

int father1 ,father2; 
int f; //函數(shù)值 
EightCode former ; 

public EightCode(){ 
father1 = -1; 
father2=-1; 
f=-1; 
former = null; 
} 

public EightCode(EightCode other){ 
for(int i = 0; i<3; i++) 
for(int j=0 ;j<3; j++){ 
e[i][j] = other.e[i][j]; 
} 
father1 = other.father1; 
father2 = other.father2; 
f = other.f; 
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 static EightCode save(EightCode e){
int z=0;
EightCode u[]=new EightCode[20];
u[z++]=e;

return u[z];
}*/
public void display( EightCode e ){ 
while( e.former != null ){ 
e.former.print();
/*e.former.save(e);*/
e = new EightCode(e.former);
} 

return ; 
} 

} 

class Queue extends Object{ //隊列  
private int number = 0; 
EightCode qu[] = new EightCode[20]; 

public void print(){ 
for(int i=number-1;i>=0;i--) 
qu[i].print(); 
} 

public void push(EightCode e){ 
qu[number] = e; 
number++; 
} 

public boolean equal(EightCode e){ 
if( number == 0 ) 
return false; 
else{ 
for(int i=0;i<number;i++){ 
if(qu[i].equals(e)) 
return true; 
} 
} 
return false; 
} 

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

public EightCode popQueue(int sequence_number){ 

return qu[sequence_number]; 
} 

public void setQueue( EightCode e,int sequence_number ){ 

qu[sequence_number] = e; 
} 

public int number(){ 
return number; 
} 

public int sequence_numberFrom (EightCode e) { 
for (int i = 0; i < number; i++){ 
if (qu[i].equals( e )) 
return i; 
} 
return -1; 
} 

public void removeBase( ){ 
for(int i=0;i<number;i++){ 
qu[i] = qu[i+1]; 
} 
number--; 
} 

public void remove( EightCode e ){ 
for( int i = 0; i < number; i++ ){ 
if( qu[i].equals( e )) 
qu[i] = null; 
} 
number--; 
} 


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

} 

//算法實現(xiàn)類 
public class Arithmetic_realization{ 
static int target[][] = {{1,2,3},{8,0,4},{7,6,5}}; 

static void Exchange(EightCode e,int i,int j,int m,int n){ 
int temp; 
temp = e.e[i][j]; 
e.e[i][j] = e.e[m][n]; 
e.e[m][n] = temp; 
} 


static int compareDiffNum(EightCode e){ 
int h =0,i,j; 
for(i=0;i<3;i++) 
for(j=0;j<3;j++){ 
if(e.e[i][j]!=target[i][j]) 
h++; 
} 
return h; 
} 

//生成子狀態(tài) 
static Queue nextEightCode(EightCode 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){ //1,1.
flag=false; 
break; 
} 
} 
i--; //0.
if(i-1>=0){ //“0”向下移一位
m=i-1; 
if(m!=e.father1){ 
Exchange(e,m,j,i,j); 
//e.print(); 

EightCode son1 = new EightCode(e); //創(chuàng)建當前相同對象
son1.father1 = i; 
son1.father2 = j; 
son1.former = e; 
sons.push(son1);//當前狀態(tài)壓入隊列中 
Exchange(e,i,j,m,j);//返回前一狀態(tài) 

} 
} 
if(i+1<3){ //“0”向上移一位
m=i+1; //1
if(m!=e.father1){ 
Exchange(e,m,j,i,j); //1,1,0,1
//e.print(); 
EightCode son2 = new EightCode(e);
son2.father1 = i; 
son2.father2 = j; 
son2.former = e; 
sons.push(son2); 
Exchange(e,i,j,m,j); //0，1，1，1
} 

} 
if(j-1>=0){ //“0”向左移一位
n=j-1; 
if(n!=e.father2){ 
Exchange(e,i,n,i,j);
//e.print(); 
EightCode son3 = new EightCode(e); 
son3.father1 = i; 
son3.father2 = j; 
son3.former = e; 
sons.push(son3); 
Exchange(e,i,j,i,n); 
} 

} 
if(j+1<3){ //“0”向左移一位
n=j+1; 
if(n!=e.father2){ 
Exchange(e,i,n,i,j); 
//e.print(); 
EightCode son4 = new EightCode(e); 
son4.father1 = i; 
son4.father2 = j; 
son4.former = e; 
sons.push(son4); 
Exchange(e,i,j,i,n); 
} 

} 
return sons; 
} 
public static void main(String[] args){ 
EightCode w = new EightCode();
System.out.println("Do you want to change the sequence:(y/n)");
try{
char k = (char)System.in.read();
if(k=='y')
{
System.out.println("Please input the new numbers:");
System.out.println();
Scanner sc=new Scanner(System.in);
for(int p=0;p<3;p++) 
   for(int q=0;q<3;q++){ 
   w.e[p][q]=sc.nextInt();
  }
}
}catch(IOException e){}
System.out.println();
System.out.println("The contrary sequence of the steps is:");
for(int p = 0;p<3;p++)
   for(int q=0;q<3;q++){ 
      System.out.print(Arithmetic_realization.target[p][q]);
      if(q==2) 
      System.out.println();
}
System.out.println();
int depth=0; //深度 
EightCode n = new EightCode(w) ; 
EightCode temp1 = new EightCode(w) , temp2 = new EightCode(w) ; 
//open表 
Queue open = new Queue(); 
//closed表 
Queue closed = new Queue(); 
//保存子狀態(tài)的表 
Queue son = new Queue(); 
open.push(n); 

while(!open.isEmpty()){ 
n= open.popQueue(0); 
open.removeBase( );
if(compareDiffNum(n)==0){ 
n.display(n);
/*
EightCode l[]=new EightCode[20];
l[0]=n.save(n);
for(int m=0;m<20;m--)
for(int i1 = 0;i1<3;i1++) 
for(int j1=0;j1<3;j1++){ 
System.out.print(l[m].e[i1][j1]); 
if(j1==2) 
System.out.println();
}*/


System.out.println("Success!"); 
return; 
} 
son = nextEightCode(n); 
depth++; 
int count = son.number(); 
if(count==0) 
continue; 
else for(int t=0;t<count;t++){ 
temp1 = son.popQueue(t); 
if(!open.equal(temp1)&&!closed.equal(temp1)){ 
temp1.f = depth + compareDiffNum(temp1); 
open.push(temp1); 
} 
else if(open.equal(temp1)){ 
temp1.f = depth + compareDiffNum(temp1); 
int pos = open.sequence_numberFrom(son.popQueue(t)); 
temp2 = open.popQueue(pos); 
if(temp1.f<temp2.f){ 
open.setQueue(temp1,pos); 
} 
} 
else if(closed.equal(temp1)){ 
temp1.f = depth + compareDiffNum(temp1); 
int pos = closed.sequence_numberFrom(temp1); 
temp2 = closed.popQueue(pos); 
if( temp1.f<temp2.f ){ 
closed.remove(son.popQueue(t)); 
open.push(temp1); 
} 
} 
} 
closed.push(n); 
for(int i=open.number()-1;i>0;i--) 
for(int j=0;j<i;j++){ 
temp1 = (EightCode)open.popQueue(j); 
temp2 = (EightCode)open.popQueue(j+1); 
if(temp1.f>temp2.f){ 
EightCode tq=new EightCode(w); 
tq = open.popQueue(j); 
open.setQueue(open.popQueue(j+1),j); 
open.setQueue(tq,j+1); 
} 
} 
} 

System.out.println("Fail!"); 
return; 
} 
}