八数码问题C++代码

#include
#include
#include
using namespace std;

typedef struct node
{
	int a[3][3];
	int value;   //value  表示f（n）=d（n）+w（n）
	int height;  //搜索到当前节点的高度
	int from;   //表示该节点是由何种移动所得，1左移，2右移，3上移，4下移
	char path[1000];     //保存前面搜索路径
	friend bool operator < （const node &t1const node &t2）
	{
		return t1.value>t2.value;   //最小值优先
	}
}node*nodelist;

class eightnum
{
public:
	eightnum（）
	{
		int ij;
		for（i=0;i<3;i++）
		{
			for（j=0;j<3;j++）
			{
				cin>>a[i][j];
				if（a[i][j]==0）    //空格处置为9，便于后面比较求value
					a[i][j]=9;
			}
		}
		flag=0;
		height=0;
	}
	
	bool eightcan（）    //判断八数码问题可否有解
	{
		/*
		判断给出的排列是否能够通过有限次移动，达到目标状态。
		算法支持：
		首先指定Less（k）k表示在九宫格中的某个数字k的取值范围是1~9Less（k）
		表示为k所在九宫格位置之后比k小的数字的个数。k=0时，自动转换成k=9。
		在下列排列中
		1 0 3
		7 2 4
		6 8 5
		Less（1）=0Less（9）=7Less（3）=1Less（7）=4Less（2）=0Less（4）=0
		Less（6）=1Less（8）=0Less（5）=0
		设定ij表示空格位置在九宫格中的位置，此例中i=1j=2。
		判断排列是否可在有限次移动得到解的条件是
		k=1:9;
		（sum（Less（k））+i+j）%2==0
		*/
		int b[9];                    //将二维数组转化成一维数组便于操作
		int ijkxy;               //ijk为控制变量，xy表示空格位置的横坐标与纵坐标
		//二维数组转一维数组
		k=0;
		for（i=0;i<3;i++）              
		{
			for（j=0;j<3;j++）
			{
				b[k]=a[i][j];
				if（a[i][j]==9）
				{
					x=i+1;
					y=j+1;
				}
				k++;
			}
		}
		//求k=1:9;sum（Less（k））+i+j	
		int sum=x+y;                  	
		for（i=0;i<9;i++）
		{
			for（j=i;j<9;j++）
			{
				if（b[j]					sum++;
			}
		}
		if（sum%2==0）
			return true;
		else
			return false;		
	}
	
	int f（node now_node）    
	{
		/*求解该节点的f（n）=d（n）+w（n），在构造时已经将d（n）求出，
		为n.height且n.value<<=n.heightw（n）表示该节点与目标状态节点
		不同的个数*/
		int ij;
		int value=0;
		for（i=0;i<3;i++）
		{
			for（j=0;j<3;j++）
				if（now_node.a[i][j]!=i*3+j+1）
				{
					value++;
				}
		}
		return value+now_node.value;
	}
	
	int solution（）
	{
		if（!eightcan（））            //判断该排列是否能够达到目标状态
		{
			cout<<“该种排列无法移动得到目标状态“<			return 0;
		}
		int ijxy;
		priority_queue q;     //构造优先权队列，以value值最小的优先出队
		node p_first;
		for（i=0;i<3;i++）
		{
			for（j=0;j<3;j++）
				p_first.a[i][j]=a[i][j];
		}
		p_first.value=0;
		p_first.height=0;
		p_first.from=0;
		p_first.path[0]=48;
		p_first.path[1]=0;
		p_first.value=f（p_first）;
		if（resultOK（p_first）==1）     //如果初始状态即为目标状态直接输出
		{
			height=p_first.height;
			path[0]=p_first.path[0];
			path[1]=p_first.path[1];
			return 1;
		}
		q.push（p_first）;
		while（q.empty（）==false）
		{	
			//获得当前扩展节点的空格位置
			for（i=0;i<3;i++）
			{
				for（j=0;j<3;j++）
					if（q.top（）.a[i][j]==9）
					{
						x=i;y=j;
					}
			}
			//进行移动操作
			if（y-1>=0 && q.top（）.from!=2）
				q.push（*moveleft（q.top（）xy））;
			if（flag==1）
				break;
			if（y+1<=2 && q.top（）.from!=1）
				q.push（*moveright（q.top（）xy））;
			if（flag==1）
				break;
			if（x-1>=0 && q.top（）.from!=4）
				q.push（*moveup（q.top（）xy））;
			if（flag==1）
				break;
			if（x+1<=2 && q.top（）.from!=3）