showa.java

用java编写的八数码算法

//package EightNum;
import java.awt.*;
import javax.swing.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowListener;
import java.awt.event.TextEvent;
import javax.swing.JOptionPane;
import java.util.*;
import java.lang.Math;
class Eight implements Comparable<Object>{
    int a[][]=new int[3][3];
	int dest[][]={{1,2,3},{8,0,4},{7,6,5}};//目的结点值
	Eight father;
	private int X,Y;//空码位置
	private int f;//估价函数值
	private int h;
	public Eight(){
		int b[][]={{0,0,0},{0,0,0},{0,0,0}};
		a=b;
        X=-1; 
        Y=-1; 
        f=-1; 
        father = null; 
        this.setXY();
		}
	public Eight(int c[][]){
		a=c;
        X=-1; 
        Y=-1; 
        f=-1; 
        father = null; 
        this.setXY();
		}
	public Eight(Eight e){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				this.a[i][j]=e.a[i][j];
			}
		}
		this.f=e.f;
		this.X=e.X;
		this.Y=e.Y;
		this.father=e.father;
		this.setXY();
	}
	public int getF(){return f;}//获取f值
	/*public int getH(){          //获取h值
		h=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(this.a[i][j]!=dest[i][j]&&a[i][j]!=0)
					h++;
			}
			
		}
		return h;
    }*/
    public int[][]getE(){
    	return a;
    }
    public int getH(){          //获取h值
		h=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
			    if(this.a[i][j]==1){
			    	int k=Math.abs(i-0);
			    	int l=Math.abs(j-0);
			    	h=h+k+l;
			    }
			    if(this.a[i][j]==2){
			    	int k=Math.abs(i-0);
			    	int l=Math.abs(j-1);
			    	h=h+k+l;
			    }
			    if(this.a[i][j]==3){
			    	int k=Math.abs(i-0);
			    	int l=Math.abs(j-2);
			    	h=h+k+l;
			    }
			    if(this.a[i][j]==4){
			    	int k=Math.abs(i-1);
			    	int l=Math.abs(j-2);
			    	h=h+k+l;
			    }
			    if(this.a[i][j]==5){
			    	int k=Math.abs(i-2);
			    	int l=Math.abs(j-2);
			    	h=h+k+l;
			    }
			    if(this.a[i][j]==6){
			    	int k=Math.abs(i-2);
			    	int l=Math.abs(j-1);
			    	h=h+k+l;
			    }
			    if(this.a[i][j]==7){
			    	int k=Math.abs(i-2);
			    	int l=Math.abs(j-0);
			    	h=h+k+l;
			    }
			    if(this.a[i][j]==8){
			    	int k=Math.abs(i-1);
			    	int l=Math.abs(j-0);
			    	h=h+k+l;
			    }
			}
			
		}
		return h;
    }
    public void print(){
    	for(int i1 = 0;i1<3;i1++)
    	     for(int j1=0;j1<3;j1++){
    	     	System.out.print(a[i1][j1]);
    	     	   if(j1==2) 
    	     	   System.out.println();
    	     	   }   
    	     System.out.println(); 
    } 
	public int getX(){return X;}//获取x值
	public int getY(){return Y;}//获取y值
	public void setF(int x){this.f=x;}
	public int compareTo(Object o){//实现Comparable接口 按f值排序
		if(((Eight)o).getF()<this.getF())
			return 1;
		if(((Eight)o).getF()>this.getF())
			return -1;
		return 0;
	}
	public void setXY(){//设置空码坐标值
		int i,j;
		for(i=0;i<3;i++){
			for(j=0;j<3;j++){
				if(a[i][j]==0){
					this.X=i;
					this.Y=j;
				}
			}
		}
	}
	public void Swap(int i,int j,int I,int J){ 
		int temp;
		temp=a[i][j];
		a[i][j]=a[I][J];
		a[I][J]=temp;
	}
	public int solve(int num[],int target[]){//判断是否有解的函数,利用逆序数的奇偶性来判断
	int i,j;
	int num_con=0,tar_con=0;
	for(i=0;i<9;i++)
		for(j=0;j<i;j++){
			if(num[j]<num[i] && num[j]!=0)
				num_con++;
			if(target[j]<target[i] && target[j]!=0)
				tar_con++;
		}
	num_con=num_con%2;
	tar_con=tar_con%2;
	if((num_con==0 && tar_con==0)||(num_con==1 && tar_con==1))
		return 1;
	else
		return 0;
	}
	public LinkedList<Eight> sonBorn(){//生成子结点
		LinkedList<Eight> sons=new LinkedList<Eight>();
		int m,n,i,j;
		i=this.getX();
		j=this.getY();
		if(i-1>=0){
			m=i-1;
		    this.Swap(m, j, i, j);
			Eight son1=new Eight(this);
			son1.X=m;
			son1.Y=j;
			son1.father=this;
			this.setXY();
			sons.add(son1);
			this.Swap(i,j,m,j);
		}
		if(i+1<3){
			m=i+1;
			this.Swap( m, j, i, j);
            Eight son2=new Eight(this);
			son2.X=m;
			son2.Y=j;
			son2.father=this;
			this.setXY();
		    sons.add(son2);
			this.Swap(i, j, m, j);
		}
		if(j-1>=0){
			n=j-1;
			this.Swap( i, n, i, j);
			Eight son3=new Eight(this);
			son3.X=i;
			son3.Y=n;
			son3.father=this;
		    this.setXY();
			sons.add(son3);
			this.Swap(i, j, i, n);
	    }
		if(j+1<3){
			n=j+1;
			this.Swap( i, n, i, j);
			Eight son4=new Eight(this);
			son4.X=i; 
			son4.Y=n;
			son4.father=this;
		    this.setXY();
			sons.add(son4);
			this.Swap(i,j,i,n);  
		}
		return sons;
	}
}

class Astar {
	int depth=0;   //深度 亦即g(x)的值
	Eight n;
	public LinkedList<Eight> open; //open表
	LinkedList<Eight> closed; //closed表
	LinkedList<Eight> son; //子结点队列
	public Astar(Eight a){
	Eight n = new Eight() ;
	n=a; 
    open = new LinkedList<Eight>(); 
	closed = new LinkedList<Eight>(); 
	son = new LinkedList<Eight>(); 
	open.addFirst(n); 
	}
	public boolean opennull(){//判断open表是否为空
		boolean g =open.isEmpty();
		return g;
	}
    public boolean isSuccess(){//是否到达目的结点
    	if(open.get(0).getH()==0)
    	     return true;
    	return false;   
    }
	public Eight FindNext(){ //搜索下一结点
		Eight t1 = new Eight() , t2 = new Eight() ;
		n= open.removeFirst();
		closed.addFirst(n);
	    son = n.sonBorn();
		depth++; 
		int count = son.size();
		if(count!=0){ 
		    for(int t=0;t<count;t++){ 
			t1 = son.get(t); 
			int y=t1.getH();
			if(!open.contains(t1)&&!closed.contains(t1)){ 
				int x = depth + y;
			    t1.setF(x) ;
		        open.addFirst(t1); 
		        } 
		    if(open.contains(t1)){ 
				int z = depth + y;
		        t1.setF(z); 
		        int pos = open.indexOf(son.get(t)); 
		        t2 = open.get(pos); 
		        if(t1.getF()<t2.getF()){ 
		        	open.set(pos,t1); 
		        	} 
		    } 
			if(closed.contains(t1)){ 
				int w = depth + y;
				t1.setF(w) ; 
				int pos = closed.indexOf(t1); 
		        t2 = closed.get(pos); 
		        if( t1.getF()<t2.getF() ){ 
		            closed.remove(son.get(t)); 
		            open.addFirst(t1); 
		        } 
		        
		    } 
		   }
		}
        
		Collections.sort(open);
		open.getFirst().print();
		Eight p=new Eight();
		p=open.getFirst();
		return p;
    }
}
public class ShowA extends JFrame implements ActionListener{
	JButton ok;
	JButton exit;
	JLabel tishi;
	JLabel tishi1;
	JTextField tishi2;
	JTextField e1;
	JTextField e2;
	JTextField e3;
	JTextField e4;
	JTextField e5;
	JTextField e6;
	JTextField e7;
	JTextField e8;
	JTextField e0;
	int a[]=new int[9];
    int gridx,gridy,gridwidth,gridheight,anchor,fill,ipadx,ipady; 
    double weightx,weighty; 
    Insets inset;
    int u;
	public ShowA(){
		this.setBounds(150,150,500,300);
		this.setTitle("用八数码实现A*算法");
		GridBagLayout grid=new GridBagLayout();
		GridBagConstraints gbc=new GridBagConstraints();
		gbc.fill=GridBagConstraints.BOTH;
		this.setLayout(grid);
		int gridx,gridy,gridwidth,gridheight,anchor,fill,ipadx,ipady;