dig.java

8数码问题用java来说明 实现了8数码问题的编程

import java.util.Scanner;
import java.util.Random;
public class ENP
{
	public static Scanner scanner;
	public  static Branch root;
	public  static Node   target;
	public  static long startTime;
	public  static long finishTime;
	public  static int steps;	
	public ENP()
	{
		scanner=new Scanner(System.in);
		root=new Branch();
		target=new Node();
		startTime=0;
		finishTime=0;
		steps=0;	
	}
	public  static void main(String[] args)
	{
		ENP enp=new ENP();
		enp.produceRootAndTarget(root,target);
		enp.printBranchNode(root);
		enp.startTime=System.currentTimeMillis();
		enp.solve(root,target);
	}

	/*产生初始状态：*/
	public  void produceRootAndTarget(Branch root,Node target)
	{
		root.node=new Node();
		root.node.table=new int[9];		
		System.out.println("请输入9个数字(0~8之间, 0 代表问题中的空格) 或者按一下'r'键自动产生一个随机数组:");
		int i=1;
		int r=-1;
		int temp=-1;
		String tempS=ENP.scanner.next();
		if(tempS!=null&&tempS.equals("r"))
		{
			Random random=new Random();
			for(int j=0;j<9;j++)
			{
				while(true)
				{
					r=random.nextInt(9);
					int k=0;
					for(;k<j;k++)
						if(r==root.node.table[k])break;
					if(k==j){root.node.table[j]=r;break;}
				}					
			}
		}
		else 
		{
			root.node.table[0]=Integer.parseInt(tempS);
			while(ENP.scanner.hasNextInt())
			{
				temp=ENP.scanner.nextInt();
				root.node.table[i++]=temp;
				if(i==9){break;}
			} 
		}
		
		//判断解的形式: 
		System.out.println(isOdd(root.node.table));
		if(isOdd(root.node.table))
			target.table=new int[]{1,2,3,4,5,6,7,8,0};//偶
		else target.table=new int[]{1,2,3,8,0,4,7,6,5};//奇
	}
	
	/*判断初始矩阵的∑（Ｆ（Ｘ）是否为偶数,其中Ｆ（Ｘ）表示矩阵中某一元素其前面比它本身小的元素(不包括零)的个数.*/
	public boolean isOdd(int[] array)
	{
		int length=array.length;
		int totalFX=0;
		for(int i=0;i<length;i++)
		{
			int fx=0;
			for(int j=0;j<i;j++)
				if(array[j]<array[i]&&array[j]!=0) fx++;
			totalFX+=fx;
		}
		System.out.println("totalFX="+totalFX);
		return(totalFX%2==0);
	}

	/*打印指定分支的节点值*/
	public  void printBranchNode(Branch branch)
	{
		System.out.println("Node:---------Step:"+ENP.steps);
		for(int i=0;i<9;i++)
		{
			System.out.print(" "+branch.node.table[i]+" ");
			if((i+1)%3==0) System.out.println();
		}
	}

	/*求解*/
	public  void solve(Branch root,Node target)
	{		
		Branch branch=null;
		if(isTarget(root,target))
		{
			System.out.println("~~~~~~~~~~~~~~~~解题完毕~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
			ENP.finishTime=System.currentTimeMillis();
			double milliseconds=ENP.finishTime-ENP.startTime;
			System.out.println("此问题总共花了: "+milliseconds+"毫秒\n总步数为: "+ENP.steps+"步!");
		}

		else
		{
			if(ENP.steps==200)
			{
				System.out.println("对不起此问题无解(至少在200步内无解)~!\n请重新输入!");
				/*Scanner s=new Scanner(System.in);
				while(s.hasNext())
				{
					if(s.next()==null)
						System.exit(0);
					else break;
				}
				s.close();*/
				new ENP().main(new String[]{"",""});
				return;					
			}			
			move(root);			
			ENP.steps++;
			branch=chooseBest(root,target);
			printBranchNode(branch);			
			solve(branch,target);				
		}		
	}
	
	/*选择当前节点最优的子节点，并让当前节点的path指向此节点*/
	public  Branch chooseBest(Branch root,Node target)
	{
		Branch best=null;
		int least=9999;
		int temp0=0;	
		int temp1=0;
		int temp2=0;
		int temp3=0;
		temp0=numOfStep(root.path,target);
		temp1=numOfStep(root.son1,target);
		temp2=numOfStep(root.son2,target);
		temp3=numOfStep(root.son3,target);
		if(temp0<temp1&&temp0<temp2&&temp0<temp3)return root.path;
		else if(temp1<=temp0&&temp1<=temp2&&temp1<=temp3)return root.son1;
		else if(temp2<=temp1&&temp2<=temp0&&temp2<=temp3)return root.son2;
		else return root.son3;
	}
	
	/*计算指定节点到目标节点的最少步数*/
	public  int numOfStep(Branch branch,Node target)
	{
		if(branch==null) return 10000;
		int[] now=branch.node.table;
		int[] tar=target.table;
		int totalSteps=0;
		for(int i=0;i<9;i++)
		{
			int increat=0; 
			for(int j=0;j<9;j++)
			{
				if(tar[j]==now[i])
					increat=j;
			}
			int steps=increat/3-i/3;
			if(steps<0)steps=-steps;
			if((increat%3-i%3)<0)steps=steps-(increat%3-i%3);
			else steps=steps+(increat%3-i%3);
			totalSteps+=steps;
		}
		return totalSteps;
	}
	
	/*根据当前节点产生新的分支节点*/
	public  void move(Branch root)
	{
		Branch temp=root;
		int zero=-1;
		for(int i=0;i<9;i++)
			if(temp.node.table[i]==0) zero=i;
		if(zero==0){
			root.son1=switcher(temp,zero,1);
			root.son2=switcher(temp,zero,3);}
		else if(zero==1){
			root.son1=switcher(temp,zero,0);
			root.son2=switcher(temp,zero,2);
			root.son3=switcher(temp,zero,4);}
		else if(zero==2){
			root.son1=switcher(temp,zero,1);
			root.son2=switcher(temp,zero,5);}
		else if(zero==3){
			root.son1=switcher(temp,zero,0);
			root.son2=switcher(temp,zero,6);
			root.son3=switcher(temp,zero,4);}
		else if(zero==4){
			root.son1=switcher(temp,zero,1);
			root.son2=switcher(temp,zero,3);
			root.son3=switcher(temp,zero,5);
			root.path=switcher(temp,zero,7);}
		else if(zero==5){
			root.son1=switcher(temp,zero,2);
			root.son2=switcher(temp,zero,4);
			root.son3=switcher(temp,zero,8);}
		else if(zero==6){
			root.son1=switcher(temp,zero,3);
			root.son2=switcher(temp,zero,7);}
		else if(zero==7){
			root.son1=switcher(temp,zero,4);
			root.son2=switcher(temp,zero,6);
			root.son3=switcher(temp,zero,8);}
		else if(zero==8){
			root.son1=switcher(temp,zero,5);
			root.son2=switcher(temp,zero,7);}
		else System.err.println("wrong number!zero not between 0 and 8");
		
		if(root.son1!=null)root.son1.father=root;
		if(root.son2!=null)root.son2.father=root;
		if(root.son3!=null)root.son3.father=root;
		if(root.path!=null)root.path.father=root;
		
		
		
	}
	
	/*交换二维数组指定两个位置的数值*/
	public  Branch switcher(Branch branch,int toWhere,int from)
	{
		int moved=branch.moved;
		Branch sonBranch=new Branch();
		sonBranch.node=new Node();
		sonBranch.node.table=new int[9];
		for(int i=0;i<9;i++)
			sonBranch.node.table[i]=branch.node.table[i];
		sonBranch.moved=toWhere;
		int[] array=sonBranch.node.table;
		int m=array[toWhere];
		if(from==moved) return null;//防止回溯
		else
		{
			array[toWhere]=array[from];
			array[from]=m;
			return sonBranch;			
		}
	}
		
	/*判断指定分支的节点值是否与目标状态相同*/
	public  boolean isTarget(Branch root, Node target)
	{
		for(int i=0;i<9;i++)
			if(root.node.table[i]!=target.table[i])
				return false;
		return true;
	}

	/*打印求解过程图*/
	public  void printPath(Branch root)
	{
		Branch now=root;
		int i=0;
		do
		{
			System.out.println("Step "+i+":");
			printBranchNode(now);
			now=now.path;
			i++;
		}while(now!=null);
	}

}

/*分支节点类*/
class Node
{
	int moved=-1;
	int[] table=null;
}

/*分支类*/
class Branch
{	
	Branch father;
	Branch son1;
	Branch son2;
	Branch son3;
	Branch path;
	Node node;
	int moved;
	public Branch()
	{
		father=null;
		son1=null;
		son2=null;
		son3=null;
		path=null;
		node=null;
		moved=-1;
	}
}