eight-puzzle.txt

这个程序是A*算法的简单实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int factor[3][3]={1,2,6,40320,1,24,5040,720,120};    //计算状态hash值时对每位赋予的权重（阶乘形式）
static int pos[9][2]={{0,0},{0,0},{0,1},{0,2},{1,2},{2,2,},{2,1},{2,0},{1,0}};//计算曼哈顿距离时用来表示数码的相应目标位置
static int f_state[3][3]={1,2,3,8,0,4,7,6,5};//终止状态
int state[362880]={0};//hash判重

struct Node{                           //定义节点结构体
	int NO[3][3];              //八数码位置
	int depth;                 //节点所处搜索深度
	int cost;                  //估价结果
	struct Node * parent;     //指向父节点的指针
};
typedef struct Node node;

struct queue{                            //存放open表的队列
	node * h;
	struct queue * next;
};
typedef struct queue Queue;

int h(node n){      //启发函数f*(n)的计算
	int sum=0;
	int i,j;
	int t;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(t=n.NO[i][j]){
				sum+=(i>pos[t][0])?(i-pos[t][0]):(pos[t][0]-i);
				sum+=(j>pos[t][1])?(j-pos[t][1]):(pos[t][1]-j);                 //曼哈顿距离
			}
	return sum;
}

int solved(node n){                     //判断是否完成搜索
	int i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(n.NO[i][j]!=f_state[i][j])
				return 0;
	return 1;
}
	
int hash(node n){      //hash值的计算
	int i,j;
	int hashnum=0;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			hashnum+=(n.NO[i][j]*factor[i][j]);    //对应位与相应权重相乘
	return hashnum;
}

void findspace(node n,int a[2]){   //找到空格的位置
	int i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(!n.NO[i][j]){
				a[0]=i;
				a[1]=j;
				return ;
			}
}

void exchange(node * &n,int a[2],int i,int j){    //空格移动，移动的方向由i,j控制
	int m,l;
	m=a[0];
	l=a[1];
	n->NO[m][l]=n->NO[m+i][l+j];
	n->NO[m+i][l+j]=0;
	m=hash(*n);                      
	if(state[m])                    //hash判重
		n=NULL;
	else
		state[m]=1;
}

void EnQueue(Queue * &head,Queue * &tmp){   //采用插入排序向open表队列中加入子节点
	Queue *p,*q;
	int t;
	t=tmp->h->cost;
	p=head->next;
	q=head;
	while(p&&p->h->cost<t){    //使得代价最小的节点排在队列首部
		p=p->next;
		q=q->next;
	}
	if(p){
		tmp->next=p;
		q->next=tmp;
	}
	else{
		tmp->next=NULL;
		q->next=tmp;
	}
}

void nodeprint(node n){                                                       //打印节点信息
	int i,j;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++)
			if(n.NO[i][j])
				printf("%d",n.NO[i][j]);
			else
				putchar(' ');
		printf("\n");
	}
	printf("*******\n");
}
void print(node n,node s0){    //递归打印搜索过程
	if(memcmp((const void *)(n.NO),(const void *)(s0.NO),36)){
		print(*(n.parent),s0);
		nodeprint(n);	
	}
	else
		nodeprint(n);
}

void addopen(node * current,Queue * &head,int position[],int i,int j){      //生成子节点，并加入到open表中
	node * temp;
	Queue * tmp;
	temp=(node *)malloc(sizeof(node));
	*temp=*current;
	temp->parent=current;
	temp->depth=current->depth+1;
	exchange(temp,position,i,j);
	if(temp){
		temp->cost=temp->depth+h(*temp);
		tmp=(Queue *)malloc(sizeof(Queue));
		tmp->h=temp;
		tmp->next=NULL;
		EnQueue(head,tmp);
	}
}

int main(void){
	node *s0,*current;
	int i,j;
	int flag=0;
	Queue * head;
	printf("请从上至下，从左至右输入八数码图中各位置的数值，空格用0表示：\n");
	s0=(node *)malloc(sizeof(node));                                //初始状态节点
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			scanf("%d",&(s0->NO[i][j]));
	s0->depth=0;    
	s0->cost=s0->depth+h(*s0);
	s0->parent=NULL;
	state[hash(*s0)]=1;
	head=(Queue *)malloc(sizeof(Queue));                  //初始化open表队列
	head->next=NULL;
	current=s0;
	while(!solved(*current)){
		int position[2];
		findspace(*current,position);                            //找到空格位置
		if(position[0]>=1)                                       //空格向四个方向移动生成子节点，向上
			addopen(current,head,position,-1,0);
		if(position[0]<=1)                                       //向下
			addopen(current,head,position,1,0);
		if(position[1]<=1)                                       //向右
			addopen(current,head,position,0,1);
		if(position[1]>=1)                                       //向左
			addopen(current,head,position,0,-1);
		if(head->next!=NULL){
			current=head->next->h;                            //取出队列首部节点，继续下一次循环
			head->next=head->next->next;
		}
		else{
			flag=1;                                    //若队列空，则无解
			break;
		}
	}
	if(flag)
		printf("无解！！！\n");
	else
		print(*current,*s0);
	return 0;
}