public class Eight{	int g;    int e[][]={{2,8,3},{1,6,4},{7,0,5}};    int zi,zj;     //0的位置    Eight former;        public Eight()    {    	g=0;        zi=-1;        zj=-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];    	}    	zi=other.zi;    	zj=other.zj;    	former=other.former;    }        public void setFormer(Eight e){    	this.former=e;    }    public void listAll( Eight e ){    	System.out.println("最優(yōu)路徑為：");    	List l=new List();    	l.insertAtFront(e);    	while( e.former != null ){    		l.insertAtFront(e.former);    		e = new Eight(e.former);    	}    	while(!l.isEmpty()){    		e=l.getFirstNode();    		e.print();    		l.removeFromFront();    	}    	return ;    }    	    public boolean equals(Eight a)    {    	int i=0;    	int j=0;    	if(a==null)    		return false;    	else {    		for( i = 0; i<3; i++)    			for(j=0;j<3; j++){    				if(a.e[i][j] != this.e[i][j])    					return false;        	}        		return true;    	}    }    public void Swap(int i,int j,int m,int n){		int temp;		temp = this.e[i][j];		this.e[i][j] = this.e[m][n];		this.e[m][n] = temp;	}      public int h(){    	int dest[][] = {{1,2,3},{8,0,4},{7,6,5}};    	int h =0,i,j;    	for(i=0;i<3;i++)    		for(j=0;j<3;j++){    			if(this.e[i][j]!=dest[i][j] && e[i][j]!=0)    				h++;    		}    	return h;    }    public int f(){    	return g+h();    }        public Eight[] ex(){    	    	List e =new List();    	int i=0,j=0,k=0;    	int m,n;    	    	boolean flag = true;	    	for(i=0;i<3&&flag;i++)    		for(j=0;j<3&&flag;j++){    			if(this.e[i][j]==0){    				flag=false;    				break;    			}    		}    	i=i-1;    	if(i-1>=0){    		Eight a=new Eight(this);    		m=i-1;    		a.Swap(m,j,i,j);    		e.insertAtBack(a);    		++k;    	}    	if(i+1<3){    		Eight a=new Eight(this);    		m=i+1;    		a.Swap(m,j,i,j);    		e.insertAtBack(a);    		++k;    	}    	if(j-1>=0){    		Eight a=new Eight(this);    		n=j-1;    		a.Swap(i,n,i,j);    		e.insertAtBack(a);    		++k;    	}    	if(j+1<3){    		Eight a=new Eight(this);    		n=j+1;    		a.Swap(i,n,i,j);    		e.insertAtBack(a);    		++k;    	}    	Eight b[]=new Eight[k];    	for(int x=0;x<b.length;x++){    		b[x]=e.getFirstNode();    		b[x].setFormer(this);    		b[x].g=this.g+1;    		e.removeFromFront();    	}    	return b;    }    static void sort(Eight a[]){    	Eight temp;        for(int i=0;i<a.length;i++){            for(int j=a.length-1;j>i;j--){              if(a[j].f()<a[j-1].f()){            	  temp=a[j-1];            	  a[j-1]=a[j];            	  a[j]=temp;            	              	                }            }        }    }    static void listSort(List l){    	Eight a[]=new Eight[l.length];    	for(int i=0;i<a.length;i++){    		a[i]=l.getFirstNode();    		l.removeFromFront();    	}    	sort(a);    	for (int i=0;i<a.length;i++)    	{    		l.insertAtBack(a[i]);    	}    }    public boolean hasIt(List l){    	ListNode s=l.firstNode;    	boolean b=false;    	while(s!=null)    	{    		if(this.equals(s.data)){    			b=true;    			break;    		}    		s=s.next;    	}    	return b;    	    }        public void print()    {    	if(this!=null){    		for(int i=0;i<3;i++){    			for(int j=0;j<3;j++){    				System.out.print(e[i][j]);    			}            System.out.println();        		}    		System.out.println("=====");    	}        else         	return;        }             public static void main(String args[]){        Eight e=new Eight();        List open =new List();        List closed =new List();        open.insertAtBack(e);    	while(true){    		if(open.isEmpty())    			break;    		Eight a=open.getFirstNode();    		 if (a.h()==0){    			e=a;    			 break;    		 }    		     		 open.removeFromFront();    	    a.ex();    		closed.insertAtBack(a);            		for(int i=0;i<a.ex().length;i++){        		if(!a.ex()[i].hasIt(open) && !a.ex()[i].hasIt(closed)){        			open.insertAtBack(a.ex()[i]);        		}    		}    		listSort(open);    	}    	e.listAll(e);    	System.out.println("open表為：");    	open.print();    	System.out.println("closed表為：");        closed.print();	    }  }