e_puzzle.cpp

原创！广度优先搜索和Astar算法求解八数码问题。是学习搜索算法和数据结构的较好参考源码。

/*8-puzzle A星算法求解 [e-mail]*/

#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "vld.h"

int state_init[9] = {
	//2,8,3,1,0,4,7,6,5   //4 steps
	//2,8,3,1,6,4,7,0,5   //5 steps
	2,1,6,4,0,8,7,5,3     //18 steps  //0.125s 2461malloc
	//6,3,0,4,8,5,7,2,1   //no solution
};

int state_goal[9] = {
	1,2,3,8,0,4,7,6,5
};

int  spos;

struct NODE
{
	int    ts[9];
	NODE   *next;
	NODE   *father;
	int		f;
	int		g;
	int		h;
};

NODE *end_node;

int	FindSpacePos(NODE *node)
{
	for(int i=0;i<9;i++){
		if (node->ts[i]==0)
			return i;
	}
	return 0;
}

int	CalcDiff(int* st)
{
	int diff=0;
	for(int i=0;i<9;i++){
		if (st[i] != state_goal[i])
			diff++;
	}
	return diff;
}

int AddSuccessor(NODE *open, NODE *close, int dir)
{
	int  ts_next[9];
	int  tmp;
	NODE *node_tmp,*node_tmp2,*node_tmp3;
	int i;
	
	for(i=0;i<9;i++){
		ts_next[i] = open->ts[i];
	}

	//chech if it in open list or close list
	switch(dir) {
	case 0://top
		tmp = ts_next[spos-3];
		ts_next[spos] = tmp;
		ts_next[spos-3] = 0;
		break;
	case 1://down
		tmp = ts_next[spos+3];
		ts_next[spos] = tmp;
		ts_next[spos+3] = 0;
		break;
	case 2://left
		tmp = ts_next[spos-1];
		ts_next[spos] = tmp;
		ts_next[spos-1] = 0;
		break;
	case 3://right
		tmp = ts_next[spos+1];
		ts_next[spos] = tmp;
		ts_next[spos+1] = 0;
		break;
	default:
		break;
	}

	int g = open->g+1;
	int h = CalcDiff(ts_next);
	int f = g + h;

	//find node in close list
	node_tmp2 = node_tmp = close;
	while (node_tmp) {
		for(i=0;i<9;i++){
			if(ts_next[i] != node_tmp->ts[i])
				break;
		}
		if (i==9) { //del it in close list and add it to openlist
			if(f < node_tmp->f){
				node_tmp2 = node_tmp->next;
				node_tmp->f = f;
				node_tmp->father = open;
				goto InserToOpenlist;
			}
			return 0;
		}
		node_tmp2 = node_tmp;
		node_tmp = node_tmp->next;
	}
	
	//find node in open list
	node_tmp = open->next;//as node_tmp is derived from open->first
	while (node_tmp) {
		for(i=0;i<9;i++){
			if(ts_next[i] != node_tmp->ts[i])
				break;
		}
		if (i==9) {
			if(f < node_tmp->f){
				node_tmp->f = f;
				node_tmp->father = open;
			}
			return 0;
		}
		node_tmp = node_tmp->next;
	}

	//add node here
	node_tmp = (NODE *)malloc(sizeof(NODE));
	node_tmp->next   = NULL;
	node_tmp->father = open;
	for(i=0;i<9;i++){
		node_tmp->ts[i] = ts_next[i];
	}
	node_tmp->g = g;
	node_tmp->h = h;
	node_tmp->f = f;

InserToOpenlist:
	//sort insert in open list
	node_tmp3 = open;
	node_tmp2 = open->next; //as first open will be delete
	while (node_tmp2 && node_tmp2->f < node_tmp->f) {
		node_tmp3 = node_tmp2;
		node_tmp2 = node_tmp2->next;
	}
	
	if (node_tmp2) 
		node_tmp->next = node_tmp2;
	node_tmp3->next = node_tmp;

	for(i=0;i<9;i++)
		if( ts_next[i] != state_goal[i])
			return 0;
	end_node = node_tmp;
	return 1;
}

void main()
{
	NODE *open,*close,*tmp/*,*solu*/;
	NODE *curr;
	int  ret;
	int  start;
	int  finish;

	open = (NODE *)malloc(sizeof(NODE));
	open->next   = NULL;
	open->father = NULL;
	open->ts[0] = state_init[0];
	open->ts[1] = state_init[1];
	open->ts[2] = state_init[2];
	open->ts[3] = state_init[3];
	open->ts[4] = state_init[4];
	open->ts[5] = state_init[5];
	open->ts[6] = state_init[6];
	open->ts[7] = state_init[7];
	open->ts[8] = state_init[8];
	open->g = 0;
	open->h = CalcDiff(open->ts);
	open->f = open->g + open->h;
	close = NULL;

	start=clock();
	while (1) {
		if (open == NULL) {
			printf("can't find solution!\n");
		}
		else{
			spos = FindSpacePos(open);
			if (spos > 2) {//move top
				ret = AddSuccessor(open,close,0);
				if (ret) {
					printf("find solution!\n");
					break;
				}
			}
			if (spos < 6) {//move down
				ret = AddSuccessor(open,close,1);
				if (ret) {
					printf("find solution!\n");
					break;
				}
			}
			if (spos != 0 && spos != 3 && spos != 6) {//move left
				ret = AddSuccessor(open,close,2);
				if (ret) {
					printf("find solution!\n");
					break;
				}
			}
			if (spos != 2 && spos != 5 && spos != 8) {//move right
				ret = AddSuccessor(open,close,3);
				if (ret) {
					printf("find solution!\n");
					break;
				}
			}
			curr = open;
			//remove node from open
			open = open->next; 
			curr->next = NULL;
			//add node to close
			if (close == NULL) {
				close = curr;
			}
			else{
				tmp = close;
				while (tmp->next != NULL) {
					tmp = tmp->next;
				}
				tmp->next = curr;
			}
		}
//#define __Debug
#ifdef __Debug
{
	int i;
	int lists;

	printf("**** open list ****\n");
	lists = 0;
	tmp = open;
	while (tmp) {
		for(i=0;i<9;i++){
			printf("%d,",tmp->ts[i]);
			if ((i+1)%3 == 0) {
				printf("\n");
			}
		}
		printf("\n");
		lists++;
		tmp = tmp->next;
	}

	printf("-- open list element count %d \n\n",lists);

	printf("**** close list ****\n");
	lists = 0;
	tmp = close;
	while (tmp) {
		for(i=0;i<9;i++){
			printf("%d,",tmp->ts[i]);
			if ((i+1)%3 == 0) {
				printf("\n");
			}
		}
		printf("\n");
		lists++;
		tmp = tmp->next;
	}
	printf("-- close list element count %d \n\n\n\n",lists);
	lists = 0;
}
#endif
	}

	 finish=clock();
//回溯

	tmp = end_node;

	int steps = -1;
	//print node here
	while(tmp){
		for(int i=0;i<9;i++){
			printf("%d,",tmp->ts[i]);
			if ((i+1)%3 == 0) {
				printf("\n");
			}
		}
		printf("\n");
		tmp = tmp->father;
		steps++;
	}

	printf("\n\nTotal steps: %d\n",steps);
	double totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
    cout<<"\n此程序的运行时间为"<<totaltime<<"秒！"<<endl;

	int i=0;
	//free
	while(open){
		tmp = open;
		open = open->next;
		free(tmp);
		i++;
	}
	while(close){
		tmp   = close;
		close = close->next;
		free(tmp);
		i++;
	}
	cout<<"Malloc Node times "<< i <<endl<<endl;
}