hehe.cpp

九宫问题原代码,解决九宫按要求重排问题.

#include <iostream.h>
struct Snode
{
	int key;                                                             //父亲节点的标志，同时也是找到目标的标志，也是判断重复的标志,key是独一无二的
	int map[9];                                                          //存放数据
	int g,f;                                                             //f是指估价值，g指高度值
	int last;                                                            //指孩子的父亲节点
public:
	Snode(){key=0;}
	void TransformIn(const int *d);
	void TransformOut(int *d);
};
void Snode::TransformIn(const int *d)
{
	key=0;
	for(int i=0;i<9;++i)
		key=key*9+(map[i]=d[i]);                                     //key的计算
}
void Snode::TransformOut(int *d)
{
	for(int i=0;i<9;++i)
	{
		d[i]=map[i];
	}
}
int spath[9][9]=                                               
{{0},
{0,1,2,1,2,3,2,3,4},
{1,0,1,2,1,2,3,2,3},
{2,1,0,3,2,1,4,3,2},
{3,2,1,2,1,0,3,2,1},
{4,3,2,3,2,1,2,1,0},
{3,2,3,2,1,2,1,0,1},
{2,3,4,1,2,3,0,1,2},
{1,2,3,0,1,2,1,2,3}
};                                                                          //错排数目
#define MAX_OPEN_LEN 50000
#define MAX_CLOSE_LEN 50000
Snode OPEN[MAX_OPEN_LEN];
int op=0;                                                                   //记录open表中记录的个数
Snode CLOSE[MAX_CLOSE_LEN];
int cp=0;                                                                   //cp是指close表中的个数  
int hFunction(const Snode &node)                                            //计算错排的数目
{
	int h=0;
	for(int i=0;i<9;++i)
	{
		h+=spath[node.map[i]][i];
	}
	return h;
}
inline void swapn(int &a,int &b)                                           //交换0和要移动的数目
{
	int tmp=a;
	a=b;
	b=tmp;
}
int Astar(const int *d)
{
	static int dp[4]={-3,-1,1,3};
	//int data[9];
	op=1;                                                              //记录open表中记录的个数
	cp=0;                                                              //cp是指close表中的个数   
	OPEN[0].TransformIn(d);
	OPEN[0].g=0;                                                       //根的高度为0
	OPEN[0].f=hFunction(OPEN[0]);
	OPEN[0].last=-1;//root node                                        //根的父亲节点key为-1
	while(op>0)                                                        //open表中没有元素结束
	{
		int i,min,zero,pos,j;                                      //min指找出的估价值最小的值存放处,zero为0的位置
		for(min=0,i=1;i<op;++i)//Choose a best                     //找出估价值最小的节点
		{
			if(OPEN[i].f<OPEN[min].f)
				min=i;
		}
		if(OPEN[min].key==54682916)                                //判断是否是最终目标，最终目标的key为54682916
		{
			CLOSE[cp++]=OPEN[min];
			return 1;
		}
		//OPEN[min].TransformOut(data);
		for(zero=0;zero<9;++zero)                                  //找0的位置
		{
			if(OPEN[min].map[zero]==0)
				break;
		}
		for(i=0;i<4;++i)                                           //找子节点
		{
			if((zero==3 || zero==6) && i==1)                   //算出移动的方向
				continue;
			if((zero==2 || zero==5) && i==2)
				continue;
			pos=zero+dp[i];
			if(pos<0 || pos>8)                                 //pos是指0四周的位置
				continue;
			swapn(OPEN[min].map[zero],OPEN[min].map[pos]);     //交换数据
			Snode child;                                       //生成孩子节点
			child.TransformIn(OPEN[min].map);                  //给孩子节点赋上key
			child.g=OPEN[min].g+1;                             //孩子节点是父亲节点的高度加上1
			child.f=child.g+hFunction(child);                  //计算估价值
			child.last=OPEN[min].key;                          //指定孩子节点的父亲节点
			for(j=0;j<cp;++j)                                  //判断是否重复
			{
				if(CLOSE[j].key==child.key)
					break;
			}
			if(j==cp)//got a new node                          //不重复则进入open表中
			{
				OPEN[op++]=child;
			}
			swapn(OPEN[min].map[zero],OPEN[min].map[pos]);     //恢复
		}
		CLOSE[cp++]=OPEN[min];                                     //把min最小的对象进入close表中
		ostream& operator<<(ostream& out,Snode &node);
		cout<<OPEN[min];
		//cout<<el<<op<<" "<<cp<<endl;
		OPEN[min]=OPEN[--op];                                      //从open表中删除
	}
	return 0;
}
ostream& operator<<(ostream& out,Snode &node)               
{
	int data[9];
	node.TransformOut(data);
	for(int i=0;i<3;++i)
	{
		for(int j=0;j<3;++j)
			out<<data[i*3+j]<<" ";
		out<<endl;
	}
	cout<<endl;
	//out<<"g="<<node.g<<endl
	//	<<"f="<<node.f<<endl<<endl;
	return out;
}


//{1,3,4,2,8,6,5,7,0};//{6,4,7,8,5,0,3,2,1};//{1,2,3,4,5,6,7,8,0};//{2,8,3,1,0,4,7,6,5};//{1,3,4,0,6,2,8,7,5};
int main(void)
{
	int a[9];
	int t1,lcount=0,j;
    int map[9]={ 2, 8, 3, 1, 0, 4, 7, 6, 5 };                             //初始状态
     for(int i=0;i<9;i++)
		 a[i]=map[i];
	for (i=0;i<9;i++)                                                 //计算逆序数,判断是否能达到目标
		{
			t1=0;
			for (j=0;j<i;j++)
				if (a[j]>a[i]&&a[j]!=9)
					t1++;
				lcount+=t1;
		}
		if (lcount%2==0)
		{
		    cout<<"unsolvable"<<endl;
			
		}else
		{
			Astar(map);
			a[0]=1;
			a[1]=2;
			a[2]=3;
			a[3]=8;
			a[4]=0;
			a[5]=4;
			a[6]=7;
			a[7]=6;
			a[8]=5;
			for(i=0;i<9;i++)                                  //输出最后一步
			{
				if(i%3==0&&i!=0)
					cout<<endl;
				cout<<a[i]<<" ";
			}
			cout<<endl;
			
		}
	//if(Astar(map))
	//	OutputSolution();
//	else
	//	cout<<"no solution!\n";
	return 0;
}