eg.cpp

一个简单的求解八数码问题的程序。采用A*算法

//Eclipse + CDT

#include <cstdlib> //abs() 
#include <iostream>
#include <list>  //list
#include <utility>  //pair<x,y>
using namespace std;
//Node
struct Node
	{
		int state[3][3];//当前状态
		int f,g;  //估计 启发函数
		int prex,prey; //previous position Of zero
		int layer;                   //在空间树中的层数便于计算f             
		int curx,cury; //current position OF zero
};
//target status
int target[3][3] = {1,2,3,8,0,4,7,6,5};
//用于排序
bool comp(const Node& m, const Node& n)
{
	return m.f < n.f;
}
//find pair<x,y> 求目标点的坐标
pair<int, int> findxy(int target[3][3], int val)
{
	for(int i=0; i!=3; ++i)
		for(int j=0; j!=3; ++j)
			if(target[i][j] == val)
				return pair<int, int>(i,j);
}
//comput 启发函数
int func_g(const Node& n)
{
	int c = 0;
	pair<int,int> pr;
	for(int i=0; i!=3; ++i)
		for(int j=0; j!=3; ++j)
			{
				pr = findxy( target, n.state[i][j]);
				c += (int)(abs(pr.first - i)) 
					+ (int)(abs(pr.second - j));
		}
		return c;
}
//copyTO for function extendsNode
void copyTo(const Node& from, Node& to)
{
	for(int i=0; i!=3; ++i)
		for(int j=0; j!=3; ++j)
			to.state[i][j] = from.state[i][j];
}
//mySwap
void mySwap(Node& m)
{
	int t = m.state[m.curx][m.cury];
	m.state[m.curx][m.cury] = 0;
	m.state[m.prex][m.prey] = t;
}
//extends New Node
void extendsNode(const Node& n, list<Node>& ln)
{
	//尝试左移
	int a = n.cury-1;
	if( a!= n.prey && a>=0)
		{
			Node* m = new Node();
			copyTo(n, *m);
			m->layer = n.layer+1;
			m->curx = n.curx;
			m->cury = a; 
			m->prex = n.curx;
			m->prey = n.cury;
			mySwap(*m);
			m->g = func_g(*m);
			m->f = m->g + m->layer;
			ln.push_back(*m); 
	}
	//尝试上移
	a = n.curx-1;
	if( a != n.prex && a>=0)
		{
			Node* m = new Node();
			copyTo(n,*m);
			m->layer = n.layer+1;
			m->curx = a;
			m->cury = n.cury;
			m->prex = n.curx;
			m->prey = n.cury;
			mySwap(*m);
			m->g = func_g(*m);
			m->f = m->g + m->layer;
			ln.push_back(*m);
	}
	//尝试右移
	a = n.cury+1;
	if(a != n.prey && a<=2)
		{
			Node* m = new Node();
			copyTo(n, *m);
			m->layer = n.layer+1;
			m->curx = n.curx;
			m->cury = a;
			m->prex = n.curx;
			m->prey = n.cury;
			mySwap(*m);
			m->g = func_g(*m);
			m->f = m->g + m->layer;
			ln.push_back(*m);
	}
	//尝试下移
	a = n.curx+1;
	if(a != n.prex && a<=2)
		{
			Node* m = new Node();
			copyTo(n, *m);
			m->layer = n.layer+1;
			m->curx = a;
			m->cury = n.cury;
			m->prex = n.curx;
			m->prey = n.cury;
			mySwap(*m);
			m->g = func_g(*m);
			m->f = m->g + m->layer;
			ln.push_back(*m);
	}
}
//initial
//int init[3][3] = {2,8,3,1,0,4,7,6,5}; 
int init[3][3] = {0,1,3,2,8,4,7,6,5}; 

/** *//** by:  hncj.qiaomu **/

int main(int argc, char *argv[])
{
	list<Node> open;
	list<Node> closed;
	//头结点
	Node& head = *(new Node());
	//initial
	head.curx = head.cury = 1;
	head.prex = head.prey = 1;
	head.layer = 0;
	//init
	for(int i=0; i!=3; ++i)
		for(int j=0; j!=3; ++j)
			head.state[i][j] = init[i][j];
	head.g = func_g(head);
	//begin selecting. 
	open.push_back(head);
	while(!open.empty())  
		{ 
			Node& front = open.front();
			if(front.g !=0 )
				{
					closed.push_back(front);
					extendsNode(front, open); 
					open.pop_front();
					open.sort(comp);
			}
			else
				{
					closed.push_back(front);
					break;
			}
	}
	//printALL
	while(!closed.empty())
		{
			Node& t = closed.front();
			for(int i=0; i!=3; ++i)
				{
					for(int j=0; j!=3; ++j)
						cout << t.state[i][j] << " ";
					cout << endl;
			}
			closed.pop_front();
			cout << endl;
	}
	system("PAUSE");
	return EXIT_SUCCESS;
}