e_puzzle_wides.cpp

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

/*8-puzzle 广度优先搜索 [e-mail]*/

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

int state_init[9] = {
	//2,8,3,1,6,4,7,0,5 //5 steps
	2,1,6,4,0,8,7,5,3   //18 steps, soulve time 13s!
};

int  spos;

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

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

int AddSuccessor(NODE *open, NODE *close, int dir)
{
	int  ts_next[9];
	int  tmp;
	NODE *node_tmp;
	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;
	}

	node_tmp = close;
	while (node_tmp) {
		for(i=0;i<9;i++){
			if(ts_next[i] != node_tmp->ts[i])
				break;
		}
		if (i==9) {
			return 0;//find node in close list
		}
		node_tmp = node_tmp->next;
	}
	
	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) {
			return 0;//find node in open list
		}
		node_tmp = node_tmp->next;
	}

	node_tmp = open;//as node_tmp is derived from open->first
	while (node_tmp->next) {
		node_tmp = node_tmp->next;
	}
	
	//add node here
	node_tmp->next = (NODE *)malloc(sizeof(NODE));
	node_tmp = node_tmp->next;
	node_tmp->next   = NULL;
	node_tmp->father = open;
	for(i=0;i<9;i++){
		node_tmp->ts[i] = ts_next[i];
	}

	if( ts_next[0] == 1 &&
		ts_next[1] == 2 &&
		ts_next[2] == 3 &&
		ts_next[3] == 8 &&
		ts_next[4] == 0 &&
		ts_next[5] == 4 &&
		ts_next[6] == 7 &&
		ts_next[7] == 6 &&
		ts_next[8] == 5 )
		return 1;

	return 0;
}

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];
	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 = open;
	while (tmp->next) {
		tmp = tmp->next;
	}

	int steps = 0;
	//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;
}