eight.java

本程序实现八数码的实现

import java.util.ArrayList;
public class eight
{
	private int[][] current;
	private int[][] target;
	private int g;
	public ArrayList<Node> open;
	public ArrayList<Node> close;
	public ArrayList<Node> next;//用于保存最佳路径,演示过程时使用
	
	//构造函数
	public eight()
	{
		current=new int[3][3];
		target=new int[3][3];
		g=0;
		open=new ArrayList<Node>();
		close=new ArrayList<Node>();
		next=new ArrayList<Node>();
	}
	//使一个节点按照顺序插入open表的中
	public void insterOpen(Node n)
	{
		open.add(n);
	}
	//使一个节点插入close表的中
	public void insertClose(Node n)
	{
		close.add(n);
	}
	public void insterNext(Node n)
	{
		next.add(n);
	}
	//在open表中取出第一个节点
	public Node pushOpenFirst()
	{
		if(!open.isEmpty())
		{
			Node n=open.get(0);
			return n;
		}
		return null;
	}
	//在open表中删除第一个节点
	public void deleteOpenFirst()
	{
		if(!open.isEmpty())
		{
			open.remove(0);	
		}
	}
	//计算每个不在位的总和P
	public int p(int[][] curr,int[][] targ)
	{
		int p=0;
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				if(curr[i][j]!=0 && curr[i][j]!=targ[i][j])
				{ //如果curr[i][j]不和当前同一位置目标的数字相同则去检测同一数字在trag[][]中的位置mn
					for(int m=0;m<3;m++){
						for(int n=0;n<3;n++)
						{
							if(curr[i][j]==targ[m][n])
							{
								p=p+Math.abs(i-m)+Math.abs(j-n);
							}
						}
					}
				}
			}
		}
		return p;
	}
	//扩展节点n
	public ArrayList<Node> extendNum(Node nd)
	{
		int[][] num=nd.getArray();
		int zero_x=0;int zero_y=0;
		ArrayList<Node> array=new ArrayList<Node>();
		int[][] n=new int[3][3];
		arrayscopy(num,n);
		//判断0所在的坐标位置
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				if(n[i][j]==0)
				{
					zero_x=i;
					zero_y=j;
					break;
				}
			}
		}
		//如果0上面有数字则可以扩张
		if(zero_x-1>=0)
		{
			n[zero_x][zero_y]=n[zero_x-1][zero_y];
			n[zero_x-1][zero_y]=0;
			int[][] t=new int[3][3];
			arrayscopy(n,t);
			Node temp=new Node();
			temp.setArray(t);
			if(!equal(temp, nd.getParNode()))
				array.add(temp);
			arrayscopy(num,n);
		}
		//如果0右面有数字则可以扩张
		if(zero_y+1<=2)
		{
			n[zero_x][zero_y]=n[zero_x][zero_y+1];
			n[zero_x][zero_y+1]=0;
			int[][] t1=new int[3][3];
			arrayscopy(n,t1);
			Node temp1=new Node();
			temp1.setArray(t1);
			if(!equal(temp1, nd.getParNode()))
				array.add(temp1);
			arrayscopy(num,n);
		}
		//如果0下面有数字则可以扩张
		if(zero_x+1<=2)
		{
			n[zero_x][zero_y]=n[zero_x+1][zero_y];
			n[zero_x+1][zero_y]=0;
			int[][] t2=new int[3][3];
			arrayscopy(n,t2);
			Node temp2=new Node();
			temp2.setArray(t2);
			if(!equal(temp2, nd.getParNode()))
				array.add(temp2);
			arrayscopy(num,n);
		}
		//如果0左面有数字则可以扩张
		if(zero_y-1>=0)
		{
			n[zero_x][zero_y]=n[zero_x][zero_y-1];
			n[zero_x][zero_y-1]=0;
			int[][] t3=new int[3][3];
			arrayscopy(n,t3);
			Node temp3=new Node();
			temp3.setArray(t3);
			if(!equal(temp3, nd.getParNode()))
				array.add(temp3);
			arrayscopy(num,n);
		}
		for(int i=0;i<array.size();i++)
		{
			array.get(i).setParNode(nd);
		}
		g++;               //每扩展一次深度加一
		return array;
	}
	//n节点和目标节点的匹配
	public boolean equal(Node n,Node targ)
	{
		boolean OK=true;
		int[][] curr=new int[3][3];
		int[][] tar=new int[3][3];
		curr=n.getArray();
		if(targ==null){
			return false;
		}
		tar=targ.getArray();
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				if(curr[i][j]!=tar[i][j])
				{
					OK=false;
					break;
				}
			}
		}
		return OK;
	}
	// 数组之间的拷贝，两个数组引用的不是同一个对象
	private void arrayscopy(int[][] src,int[][] dest)
	{
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				dest[i][j]=src[i][j];
			}
		}
	}
	
	//current,target的get/set方法
	public int[][] getCurrent() 
	{
		return current;
	}
	public void setCurrent(int[][] current)
	{
		this.current = current;
	}
	public int[][] getTarget()
	{
		return target;
	}
	public void setTarget(int[][] target)
	{
		this.target = target;
	}
	public int getG()
	{
		return g;
	}
	public void setG(int g)
	{
		this.g = g;
	}

	public void chushihua(int current0[][])
	{
		current=current0;
	}
	public void chushihua2(int target0[][])
	{
		target=target0;
	}
	public int[] zhuanhuan (int a[][])
	{
		int m=0; 
		int[] num =new int[9];
		for(int i=0;i<3;i++) 
		{
			for(int j=0;j<3;j++) 
            { 
                num[m]=a[i][j]; 
                m++; 
            } 
        }
        return num;
	}
	public	boolean HaveSolution( )
	{
		int i,j,sum2 = 0,sum1=0;
		int[] num0 =new int[9];
		int[] num1 =new int[9];
		num0=zhuanhuan(current);
		num1=zhuanhuan(target);
		for(i=1;i<9;i++ )
		for(j=0;j<i;j++ )
		{
			if(num0[i]==0)
			{
				j=i;
			}
			else
			{
				if(num0[j]>num0[i])
				{
					sum1++;
			    }
			}
		}
		for(i=1;i<9;i++ )
		for(j=0;j<i;j++ )
		{
			if(num1[i]==0)
			{
				j=i;
			}
			else
			{
				if(num1[j]>num1[i])
				{
					sum2++;
			    }
			}
		}
		if( sum1%2 == sum2%2 )
		return true;
		return false;
	}
}