eightcode.java

用类A*算法的全局择优搜索法解决8数码问题,可以选择不同的启发函数

//用类A*算法的全局择优搜索法解决8数码问题
import java.io.*;
import java.util.*;

//棋盘状态类
/*codes为模拟棋盘状态的三维数组
 *AIM为问题的目标状态
 *FAIL为问题的无解状态
 *path为保存空格移动路径的字符串，1向上，2向右，3向下，4向左
 *path第一字节保留为0，例path=02314表示空格依次向右下上左移动
 *value为状态评估值，越小表示越接近结果
 */
class State implements Comparable
{
	public int[][] codes=new int[3][3];
	public static int[][] AIM={{1,2,3},{8,0,4},{7,6,5}};
	public static int[][] FAIL={{1,2,3},{7,0,4},{8,6,5}};
	public String path;
	int value;
	//构造函数，由指定状态数组和路径信息建立State类，之后计算value值
	//估价函数可任意组合
	State(int[][] obj,String str)
	{
		for (int i=0;i<3;i++)
			for (int j=0;j<3;j++)
				{
				codes[i][j]=obj[i][j];
				}
		path=str;
		value=fun1()+fun3();
	}
	//估价函数1，返回值为路径长度，即初态至当前状态所需步数
	private int fun1()
	{
		return path.length();
	}
	//估价函数2，返回值为数字错放位置的个数
	private int fun2()
	{
		int value2=0;
		for (int i=0;i<3;i++)
			for (int j=0;j<3;j++)
				if (codes[i][j]==AIM[i][j])
					value2++;
		value2=9-value2;
		return value2;
	}
	//估价函数3，返回值为各数字离目标的最短距离之合
	private int fun3()
	{
		int value3=0;
		for(int i=0;i<3;i++)
			for (int j=0;j<3;j++)
				for(int x=0;x<3;x++)
					for (int y=0;y<3;y++)
						if (codes[i][j]==AIM[x][y]&&codes[i][j]!=0)
							value3=value3+Math.abs(x-i)+Math.abs(y-j);
		return value3;
	}
	//重载判等函数，仅当codes[][]相等时，两结点相等
	public boolean equals(State a)
	{
		for (int i=0;i<3;i++)
			for (int j=0;j<3;j++)
			{
				if (codes[i][j]!=a.codes[i][j])
					return false;
			}
		return true;
	}
	//重载比较函数，按value比较大小，但仅当codes[][]相等时，两结点相等
	public int compareTo(Object rv)
	{
		int rvv=((State)rv).value;
		if(((State)rv).equals(this))
			return 0;
		else if (value<rvv)
			return -1;
		else 
			return 1;
	}
	
}
public class EightCode 
{
	public static void main(String argv[])
	{
		//从键盘读入棋盘初态，输入方法如下例所示
		/*1 4 5
		 *3 8 0
		 *2 6 7 
		 */
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		String s;
		int[][] input=new int[3][3];
		try
		{
			for(int i=0;i<=2;i++)
			{	
				do
				{
					s=in.readLine();
			    }while(s==null||s.length()==0);	
			    input[i][0]=Integer.parseInt(s.substring(0, 1));
			    input[i][1]=Integer.parseInt(s.substring(2, 3));
			    input[i][2]=Integer.parseInt(s.substring(4, 5));
			}
		}
		catch(IOException e)
		{
			System.err.println(e);
		}	
		State start=new State(input,"0");
		State fail=new State(State.FAIL,"0");
		State end=new State(State.AIM,"0");
		//建立open表，类型为TreeSet<State>,此表按升序存储结点
		TreeSet<State> open=new TreeSet<State>();
		//建立cloded表，记录已搜索过的结点
		TreeSet<State> closed=new TreeSet<State>();
		open.add(start);
		//标识变量，1表示问题解决，2表示问题无解，0表示尚在解决中
		int flag=0;
		//搜索过的结点数量，用于比较估价函数优劣
		int num=0;
		while (flag==0)
		{
			State temp;
			temp=open.pollFirst();
			//将新取出的结点记录在临时变量中
			closed.add(temp);
			int codeState[][]=new int[3][3];
			String str=temp.path;
			//pdir记录该结点的路径中的最后一位数
			int pdir=Integer.parseInt(str.substring(str.length()-1));
			int x=0,y=0;
			for (int dir=1;dir<=4;dir++)
			{
				//取出状态数组并寻找空格位置
				for (int i=0;i<3;i++)
					for (int j=0;j<3;j++)
						{
						codeState[i][j]=temp.codes[i][j];
						if (codeState[i][j]==0)
						{x=i;y=j;}
						}
				//对1方向，当最后一次移动不是向下（避免重复移动）
				//且空格在第二、三行，空格上移
				if (dir==1&&x>0&&pdir!=3)
				{
					codeState[x][y]=codeState[x-1][y];
					codeState[x-1][y]=0;
				}
				//同理，对3方向，若可移动，空格下移
				if (dir==3&&x<2&&pdir!=1)
				{
					codeState[x][y]=codeState[x+1][y];
					codeState[x+1][y]=0;
					
				}
				//4方向，空格左移
				if (dir==4&&y>0&&pdir!=2)
				{
					codeState[x][y]=codeState[x][y-1];
					codeState[x][y-1]=0;
				}
				//2方向，空格右移
				if (dir==2&&y<2&&pdir!=4)
				{
					codeState[x][y]=codeState[x][y+1];
					codeState[x][y+1]=0;
				}	
				//若空格进行了移动
				if(codeState[x][y]!=0)
				{
					//建立新结点
					State newState=new State(codeState,str+String.valueOf(dir));
					//如果等于目标状态，输出路径，flag置1
					if (newState.equals(end))
					{
						System.out.println(newState.path);
						flag=1;
				    }
					//等于死局，flag置2
				    else if(newState.equals(fail))
				    	flag=2;
					//不在open或closed中，加入进open
				    else if(!open.contains(newState)&&!closed.contains(newState))
						open.add(newState);
					//在open中，比较路径信息，若短于open表中结点，修改其值
				    else if(open.contains(newState))
				    	{
				    	for(State a:open)
				    	{
				    		if(a.equals(newState)&&a.path.length()>newState.path.length())
				    			a.path=newState.path;
				    	}
				    	}
					//剩余的情况为在closed中，不做处理	    	
				}
			}
			num++;
		}
		if (flag==1)
			System.out.println("Succeed!"+num);
		else if(flag==2)
			System.out.println("Fail!");
	}
}