eight.java

八数码问题,可以实现将九个空格里的八个数进行排列

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("最优路径为：");
    	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();	
    }  
}