eightdigit.java

求解八数码问题,初始状态存放在文件中

import java.io.*;
import java.util.*;
//主类
public class EightDigit{
	public static void main(String args[]){
		int a[][]=new int[3][3];//存放由文件读入的初始状态
		int judge[]=new int[9];//判断逆序数所用数组
		int c=0;//初始状态的逆序数对数
		Eight start=new Eight();//初始状态结点
		try{
			BufferedReader reader;
			FileInputStream fi;
			StringBuffer sb=new StringBuffer();
			int p=0;
			while((p=System.in.read())!=13){//从命令行读入文件名，暂存在一个字符串缓冲区，结束条件为读入回车
				sb.append((char)p);
			}
			String name=new String(sb);//由字符串缓冲区中的字符序列新建一个字符串，代表读入的文件名
			fi=new FileInputStream(name);
			reader=new BufferedReader(new InputStreamReader(fi));
			StringBuffer s;
			String str;	
			int n=0;
			int m=0;
			while((str=reader.readLine())!=null){//以行为单位读入
				StringBuffer ss=new StringBuffer(str);
				//根据文件内容格式，分别将每一行代表数字的三个字符转化为整型，存入数组相应位置
				a[n][0]=((int)ss.charAt(0))-48;
				a[n][1]=((int)ss.charAt(2))-48;
				a[n][2]=((int)ss.charAt(4))-48;
				//按顺序存放在判断逆序数的数组中
				judge[m]=a[n][0];
				judge[m+1]=a[n][1];
				judge[m+2]=a[n][2];
				n=n+1;
				m=m+3;
			}
			reader.close();//关闭流
			int loc=0;
			//寻找0在逆序数组中的位置
			for(int i=0;i<9;i++){
				if(judge[i]==0){
					loc=i;
				}
			}
			//将0忽略
			for(int i=loc;i<8;i++){
				judge[i]=judge[i+1];
			}
			//计算逆序数对数
			for(int i=0;i<7;i++){
				for(int j=i+1;j<8;j++){
					if(judge[i]>judge[j]){
						c++;
					}
				}
			}
			//目标状态逆序数共奇数对，所以初始状态若为偶数对，则无解，直接输出no solution并返回
			if(c%2==0){
				System.out.println("no solution");
				return;
			}
			//建立初始结点
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					start.state[i][j]=a[i][j];
					if(a[i][j]==0){
						start.faX=i;
						start.faY=j;
					}
				}	
			}
			start.calculate_f();//计算初始结点的f值
			EightList open=new EightList();//建立open表
			EightList close=new EightList();//建立close表
			EightList son=new EightList();//扩展结点时用作暂存的表
			open.addLast(start);//初始结点存入open表
			Eight here=new Eight();//搜索过程中用到的临时变量
			Eight temp1=new Eight();//同上
			Eight temp2=new Eight();//同上
			int depth=0;
			//搜索开始
			while(open.size()!=0){//结束条件：open表不空
				here=open.poll();//取出open表中第一个元素，并将之从open表中删除
				if(here.h==0){//达到目标状态条件：h函数值为0（此处h函数定义为不在位的将牌数）
					here.listall();//达到目标状态时输出整个路径
					System.out.println("total steps:"+here.f);//输出总步数，即目标状态的f值
					return;//返回
				}
				//未达到目标状态
				son=here.expand();//对于取出的结点进行扩展，暂存入son表中
				int count=son.size();//得到扩展出的结点个数
				if(count==0)continue;//无新扩展结点，则继续循环
				else{//否则对于每个扩展出来的结点进行判断
					for(int i=0;i<count;i++){
						temp1=son.get(i);//暂存当前扩展出的结点
						if(!open.contains(temp1)&&!close.contains(temp1)){//如果该结点在open表和close表中都不存在
							open.insert(temp1);//将新结点插入到open表相应位置（根据f值判断）
						}
						else if(open.contains(temp1)){//若open表中已有表示该状态的结点
							int pos=open.indexOf(temp1);
							temp2=open.get(pos);//取出open表中相同状态的结点
							if(temp1.f<temp2.f){//比较两者f值的大小，将小者重新存入open表，大者忽略
								open.remove(temp2);//将原结点从open表中删除
								open.insert(temp1);//将新结点加入open表中
							}
						}
						else if(close.contains(temp1)){//若在close表中有表示该状态的结点
							int pos=close.indexOf(temp1);
							temp2=close.get(pos);//取出close表中相同状态的结点
							if(temp1.f<temp2.f){//若当前结点的f值比close表中表示相同状态的结点的f值小
								close.remove(temp1);//则将原结点其从close表中删除
								open.insert(temp1);//将新结点加入open表
							}
						}
					}
					close.addLast(here);//将此次扩展的结点加入到close表中
				}
				
			}
			System.out.println("no solution");//open表空，未找到解，输出无解
			return;
			}catch(FileNotFoundException e){//异常处理
			System.out.println("Catch "+e);
			}catch(IOException i){//异常处理
			System.out.println("Catch "+i);
			}
	}
}

//八数码状态结点类
class Eight{
	int state[][]=new int[3][3];//保存当前的八数码状态
	static int dest[][]={{1,2,3},{8,0,4},{7,6,5}};//标准状态
	int faX,faY;//记录0所在位置
	int f;//估计函数值
	int h;//h函数值
	Eight former;//当前状态的前一状态
	//构造函数，将所有值初始化
	Eight(){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				state[i][j]=0;
			}
		}
		faX=-1;
		faY=-1;
		f=-1;
		h=-1;
		former=null;
	}
	//拷贝构造函数，将对应的状态结点拷贝到当前新结点
	Eight(Eight other){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				state[i][j]=other.state[i][j];
			}
		}
		faX=other.faX;
		faY=other.faY;
		f=other.f;
		h=other.h;
		former=other.former;
	}
	//输出当前结点
	public void print(){
		for(int i=0;i<3;i++){ 
			for(int j=0;j<3;j++){ 
				System.out.print(state[i][j]+" ");
			}
			System.out.println(); 
		}
		System.out.println();
	}
	//计算f函数值
	public void calculate_f(){
		h=0;//将当前结点的h函数先清0
		for(int i=0;i<3;i++){//对于所有位置上的数字进行扫描，若与目标状态不同，则将h函数值加1
			for(int j=0;j<3;j++){
				if(state[i][j]!=dest[i][j]){
					h++;
				}
			}
		}
		if(this.former!=null){//若存在父结点，则g函数的值为其父结点f函数与h函数之差加1（因为每条路径的耗散值均为1），而当前f函数值即g+h
			f=h+this.former.f-this.former.h+1;
		}
		else f=h;//若不存在父结点，即初始结点，则f=h
	}
	//按顺序列出所有步数
	public void listall(){
		Eight e=new Eight(this);
		if(e.former.former!=null){//判断当前结点的父结点是否为第一步，若不是，递归输出前一结点
			e.former.listall();
		}
		e.print();//输出当前结点
	}
	//对当前结点扩展，返回一个存放扩展出的所有结点的sons表
	public EightList expand(){
		EightList sons=new EightList();//初始化sons表
		//每一步最多扩展出四个结点
		Eight son1=new Eight(this);
		Eight son2=new Eight(this);
		Eight son3=new Eight(this);
		Eight son4=new Eight(this);
		//罗列所有0可能在的位置，对每一种情况列出其所有的扩展结点状态，并记录新的0位，记录其父结点，并计算其对应的f值，最后加入到sons表中
		if(faX==0&&faY==0){//0在第一行第一列，则有两个扩展结点，分别是将第一行第二列的左移，与将第二行第一列的上移
			son1.state[0][0]=this.state[0][1];
			son1.state[0][1]=0;
			son1.faX=0;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[0][0]=this.state[1][0];
			son2.state[1][0]=0;
			son2.faX=1;
			son2.faY=0;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		else if(faX==0&&faY==1){//0在第一行第二列，有三个扩展结点，为第一行第一列右移，第一行第三列左移和第二行第二列上移
			son1.state[0][1]=this.state[0][0];
			son1.state[0][0]=0;
			son1.faX=0;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[0][1]=this.state[0][2];
			son2.state[0][2]=0;
			son2.faX=0;
			son2.faY=2;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[0][1]=this.state[1][1];
			son3.state[1][1]=0;
			son3.faX=1;
			son3.faY=1;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==0&&faY==2){//0在第一行第三列，有两个扩展结点，为第一行第二列右移和第二行第三列上移
			son1.state[0][2]=this.state[0][1];
			son1.state[0][1]=0;
			son1.faX=0;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[0][2]=this.state[1][2];
			son2.state[1][2]=0;
			son2.faX=1;
			son2.faY=2;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		else if(faX==1&&faY==0){//0在第二行第一列，有三个扩展结点，为第一行第一列下移，第二行第二列左移和第三行第一列上移
			son1.state[1][0]=this.state[0][0];
			son1.state[0][0]=0;
			son1.faX=0;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[1][0]=this.state[1][1];
			son2.state[1][1]=0;
			son2.faX=1;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[1][0]=this.state[2][0];
			son3.state[2][0]=0;
			son3.faX=2;
			son3.faY=0;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==1&&faY==1){//0在第二行第二列，有四个扩展结点，为第一行第二列下移，第二行第一列右移，第二行第三列左移和第三行第二列上移
			son1.state[1][1]=this.state[0][1];
			son1.state[0][1]=0;
			son1.faX=0;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[1][1]=this.state[1][0];
			son2.state[1][0]=0;
			son2.faX=1;
			son2.faY=0;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[1][1]=this.state[1][2];
			son3.state[1][2]=0;
			son3.faX=1;
			son3.faY=2;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
			son4.state[1][1]=this.state[2][1];
			son4.state[2][1]=0;
			son4.faX=2;
			son4.faY=1;
			son4.former=this;
			son4.calculate_f();
			sons.addLast(son4);
		}
		else if(faX==1&&faY==2){//0在第二行第三列，有三个扩展结点，为第一行第三列下移，第二行第二列右移和第三行第三列上移
			son1.state[1][2]=this.state[0][2];
			son1.state[0][2]=0;
			son1.faX=0;
			son1.faY=2;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[1][2]=this.state[1][1];
			son2.state[1][1]=0;
			son2.faX=1;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[1][2]=this.state[2][2];
			son3.state[2][2]=0;
			son3.faX=2;
			son3.faY=2;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==2&&faY==0){//0在第三行第一列，有两个扩展结点，为第二行第一列下移和第三行第二列左移
			son1.state[2][0]=this.state[1][0];
			son1.state[2][0]=0;
			son1.faX=2;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[2][0]=this.state[2][1];
			son2.state[2][1]=0;
			son2.faX=2;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		else if(faX==2&&faY==1){//0在第三行第二列，有三个扩展结点，为第三行第一列右移，第三行第三列左移和第二行第二列下移
			son1.state[2][1]=this.state[2][0];
			son1.state[2][0]=0;
			son1.faX=2;
			son1.faY=0;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[2][1]=this.state[1][1];
			son2.state[1][1]=0;
			son2.faX=1;
			son2.faY=1;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
			son3.state[2][1]=this.state[2][2];
			son3.state[2][2]=0;
			son3.faX=2;
			son3.faY=2;
			son3.former=this;
			son3.calculate_f();
			sons.addLast(son3);
		}
		else if(faX==2&&faY==2){//0在第三行第三列，有两个扩展结点，为第三行第二列右移和第二行第三列下移
			son1.state[2][2]=this.state[2][1];
			son1.state[2][1]=0;
			son1.faX=2;
			son1.faY=1;
			son1.former=this;
			son1.calculate_f();
			sons.addLast(son1);
			son2.state[2][2]=this.state[1][2];
			son2.state[1][2]=0;
			son2.faX=1;
			son2.faY=2;
			son2.former=this;
			son2.calculate_f();
			sons.addLast(son2);
		}
		return sons;
	}
	//判断两个结点的状态是否相同，相同返回true，否则false
	public boolean equals(Eight e){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(state[i][j]!=e.state[i][j]){
					return false;
				}
			}
		}
		return true;
	}
}

//列表类，用来存放八数码问题中的结点
class EightList{
	Eight ee[]=new Eight[181440];
	private int size;
	//构造函数，初始化大小为0
	EightList(){
		size=0;
	}
	//往表的最后添加指定元素
	public void addLast(Eight e){
		ee[size]=e;
		size++;
	}
	//判断该表是否包含指定的状态结点，是返回true，否则false
	public boolean contains(Eight e){
		if(size==0){
			return false;
		}
		else{
			for(int i=0;i<size;i++){
				if(ee[i].equals(e)){
					return true;
				}
			}
			return false;
		}
	}
	//取出并删除表中的第一个元素，返回该元素
	public Eight poll(){
		Eight e=ee[0];
		for(int i=0;i<size-1;i++){
			ee[i]=ee[i+1];
		}
		size--;
		return e;
	}
	//获得该表的大小
	public int size(){
		return size;
	}
	//得到表中指定位置的元素
	public Eight get(int pos){
		return ee[pos];
	}
	//查找表中指定元素所在的位置
	public int indexOf(Eight e){
		for(int i=0;i<size;i++){
			if(ee[i].equals(e)){
				return i;
			}
		}
		return -1;
	}
	//删除表中某个元素，同时将其后所有元素前移一位，表的大小减一。若不存在该元素，则直接返回
	public void remove(Eight e){
		int pos=-1;
		for(int i=0;i<size;i++){
			if(ee[i].equals(e)){
				pos=i;
				break;
			}
		}
		if(pos==-1)return;
		for(int i=pos;i<size-1;i++){
			ee[i]=ee[i+1];
		}
		size--;
	}
	//插入函数，将新结点根据其f值插入到相应位置
	public void insert(Eight e){
		int pos=size;
		Eight temp1=new Eight();
		Eight temp2=new Eight();
		temp2=e;
		for(int i=0;i<size;i++){
			if(e.f<=ee[i].f){
				pos=i;
				break;
			}
		}
		size++;
		for(int i=pos;i<size;i++){
			temp1=ee[i];
			ee[i]=temp2;
			temp2=temp1;
		}
	}
	
}