8数码问题.cpp

本程序是用C++语言编写的

/*--------------------------------------------------说明------------------------------------------------*/
/*                         此程序为八数码问题求解                                                       */

/*                 本程序利用启发函数来实现A算法（实为A*算法），效率较高；                              */
/*                        具体思想请参考人工智能相关书籍；                                              */
/*                           启发函数为 深度+不在位数；                                                 */
/*                             作者：张莉           学号:040640203;                                     */
/*                                  日期：2008.06.21；                                                  */
/*                                   仅供学习使用。                                                     */
 

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

#define  UP    1                    //节点向上移
#define  DOWN  2                    //节点向下移
#define  LEFT  3                    //节点向左移
#define  RIGHT 4                    //节点向右移
#define MAXVEX  40320               //定义最大扩展节点数

/*---------------------------------------------部分参数--------------------------------------------------------*/
int origin_data[9];                 //初始节点
int target_data[9];                 //目标节点
typedef struct vex{                 //定义结构体节点
    int data[9];                    //此时的数据排列,等价于八数码状态
	int layer;                      //节点的层数
	int diff;                       //节点与目标节点相比不同的位数
	int point;                      //标志位，未被访问为0，被open表访问后为1，被close表访问时为1
	int weight;                     //weight=diff+layer,相当于A*算法中的f函数
	struct vex *next;
	struct vex  *prio;
	struct vex *father;
}vexnode;
vexnode *open_root;
vexnode*close_root;
/*------------------------------------------部分参数-----------------------------------------------------------*/

/*---------------------------------------------------主要函数------------------------------------------------------------*/



//函数名称：vexnode*create_vexnode()
//功能说明：新建一个结构体节点，返回节点指针
//入口参数：无
//出口参数：结构体节点的指针
vexnode*create_vexnode(){
	return(vexnode*)malloc(sizeof(vexnode));
}




//函数名称：check_inputnum(int data[]);
//功能说明：检查输入数据的正确性
//入口参数：一维数组
//出口参数：若数组正确，返回值为1，反之返回0，并输出错误原因
int check_inputnum(int data[]){
	int i=0,j;
	while(i<9){
		if(data[i]>8){
			printf("此输入数据中第%d行%d列 %d大于8\n",i/3+1,i%3+1,data[i]);
		    return 0;
		}//if
		if(data[i]<0){
			printf("此输入数据中第%d行%d列 %d小于0\n",i/3+1,i%3+1,data[i]);
				return 0;
		}//if
		i++;
	}
	for(i=0;i<9;i++)
		for(j=i+1;j<9;j++){
			if(data[i]==data[j]){
				printf("此输入数据中第%d行%d列与第%d行%d列数据%d相同.\n",i/3+1,i%3+1,j/3+1,j%3+1,data[i]);
				return 0;
			}//if
		}//for
		return 1;
}


//函数名称：ary_attr(int data[]);
//功能说明：判断一维数组的奇偶属性
//入口参数：一维数组
//出口参数：若数组属性为奇，返回值为1，为偶则返回为0
int ary_attr(int data[]){
	int i,j,attri;
	attri=0;
	for(i=1;i<9;i++)
		for(j=0;j<i;j++)
			if(data[i]!=0&&data[j]!=0&&data[j]<data[i])
				attri++;
			return   attri%2;
}


//函数名称：input_data(int data1[],int data2[]);
//功能说明: 输入初始节点和目标节点的八数码状态，并判断正确性，直到输入正确或退出程序为止
//入口参数：两个一维数组
//出口参数：如果输入正确，返回值为1，否则退出程序
int input_data(int data1[],int data2[]){
	int i;
	char choice1;
	printf("请输入初始节点数据: \n");
	printf("请输入3行从0到8的数据：\n");
	for(i=0;i<9;i++)
		scanf("%d",data1+i);
	while(!check_inputnum(data1)){
		
		printf("数据输入错误!\n");
		printf("要重新输入吗?(y/n)");

		scanf("%c",&choice1);
		if(choice1=='y'||choice1=='Y'){
			printf("\n请重新输入：");
			for(i=0;i<9;i++)
	        	scanf("%d",data1+i);
		}//if
		else if(choice1=='n'||choice1=='N'){
			printf("\n抱歉，数据输入错误，无法求解\n");
			printf("\n下面将退出程序。");
			exit(0);
		}//else if

	}//while

	printf("初始数据输入无误!\n");

	printf("\n下面请输入目标节点数据:\n");
	printf("请输入3行从0到8的数据：\n");
	for(i=0;i<9;i++)
		scanf("%d",data2+i);
	while(!check_inputnum(data2)){
		
		printf("数据输入错误!\n");
		printf("要重新输入吗?(y/n)");
		scanf("%c",&choice1);
		if(choice1=='y'||choice1=='Y'){
			printf("\n请重新输入：");
			for(i=0;i<9;i++)
	        	scanf("%d",data2+i);
		}//if
		else if(choice1=='n'||choice1=='N'){
            printf("\n抱歉，数据输入错误，无法求解\n");
			printf("\n下面将退出程序。\n");
			exit(0);
		}//else
	}//while
	printf("目标数据输入无误！\n");
	return 1;
}//end of program





//函数名称：copy(int data1[],int data2[])
//函数功能：复制数组
//入口参数：复制数组和被复制数组指针
//出口参数：无
void copy(int data1[],int data2[]){
		int i=0;
		for(i=0;i<9;i++)
			data1[i]=data2[i];
	
}

//函数名称：data_solution(int data1[],int data2[])
//函数功能：判断目标节点到初始节点是否有解
//入口参数：连个一维数组（初始节点和目标节点八数码状态）
//出口参数：有解返回值1，无解重新输入或退出
int data_solution(int data1[],int data2[]){
	char choice2;
	while(ary_attr(data1)!=ary_attr(data2)){
		printf("\n抱歉，此8数码无解!\n");
		printf("需要重新输入吗？(y/n)");
		scanf("%c",&choice2);
		if(choice2=='y'||choice2=='Y'){
			printf("\n下面请重新输入数据:\n");
			input_data(data1,data2);

		}
		else if(choice2=='N'||choice2=='n'){
			printf("\n--下面将退出程序--\n");
			exit(0);
		}
	}
	return 1;
}



//函数名称：insert_open(vexnode*root,vexnode*p);
//函数功能：将节点有序插入open表中
//入口参数：open表入口指针，插入节点指针
//出口参数：节点指针为空，则返回0，否则，插入open表返回值1
int insert_open(vexnode*root,vexnode*p){
	if(p==NULL)
		return 0;
	vexnode*p1,*p2;
	p1=root->next;
	p2=root;
	while(p1!=NULL&&p->weight>p1->weight){
		p2=p1;
	    p1=p1->next;
	}
	p2->next=p;
	p->prio=p2;
	p->next=p1;
	if(p1!=NULL)
		p1->prio=p;
	return 1;
}



//函数名称：insert_close(vexnode*root,vexnode*p);
//函数功能：将节点插入close表中
//入口参数：close表入口指针，插入节点指针
//出口参数：节点指针为空，则返回0，否则，插入close表返回值1
int ADD_close(vexnode*closeroot,vexnode*p){
	if(p==NULL)
		return 0;
	p->next=closeroot->next;
	p->prio=closeroot;
	closeroot->next=p;
	if(p->next!=NULL)
		p->next->prio=p;
	return 1;
}


//函数名称：*first_open(vexnode*root)
//函数功能：删除open表中第一个节点
//入口参数：open表的入口指针
//出口参数：若open表为空，则返回NULL，否则返回删除节点指针
vexnode*remove_open(vexnode*openroot){
	vexnode *p;
	if(openroot->next==NULL)
		return NULL;
	p=openroot->next;
	openroot->next=p->next;
	if(p->next!=NULL)
		p->next->prio=openroot;
	p->prio=NULL;
	p->next=NULL;
	return p;
}


//函数名称：swap(int *data1,int *data2)
//函数功能：交换一维数组中的两个数
//入口参数：一维数组中两个数的指针
//出口参数：无
void swap(int *data1,int *data2){
	int data;
	data=*data1;
	*data1=*data2;
	*data2=data;
}



//函数名称：do_direct(int m[],int op)
//函数功能：对八数码中的数进行移动
//入口参数：一维数组(视为八数码)，移动方向 
//出口参数：移动成功返回值为1，否则为0
int do_direct(int m[],int op){
	int blank;
	blank=0;
	while(m[blank]!=0&&blank<9)
		blank++;
	if(blank>=9)
		printf("");
	switch(op){
	case UP:
		if(blank>2)
			swap(m+blank,m+blank-3);
		break;
	case DOWN:
		if(blank<6)
			swap(m+blank,m+blank+3);
		break;
	case LEFT:
		if(blank%3!=0)
			swap(m+blank,m+blank-1);
		break;
	case RIGHT:
		if(blank%3!=2)
			swap(m+blank,m+blank+1);
		break;
	default:return 0;
	}
	return 1;
}

//函数名称：compare(int data1[],int data2[])
//函数功能：比较当前节点和目标节点，得出当前节点不在位数
//入口参数：两个一维数组(视为八数码当前状态) 
//出口参数：返回节点不在位数
int compare(int data1[],int data2[]){
	int i,diff;
	diff=0;
	for(i=0;i<9;i++)
		if(data1[i]!=data2[i])
			diff++;
		return diff;
}





//函数名称：has_appear(vexnode*open,vexnode*close,vexnode*p)
//函数功能：判断移动后节点是否已经在open表或在close表中出现过
//入口参数：open表和close表入口指针，当前节点指针 
//出口参数：出现过返回值为1，否则为0

int has_appear(vexnode*open,vexnode*close,vexnode*p){
        vexnode *p1;
		int i,same=1;
		p1=open->next;
		while(p1!=NULL){
			for(i=0;i<9;i++)
				if(p1->data[i]!=p->data[i])
					same=0;
				if(same)
					return 1;
				p1=p1->next;
		}
		p1=close->next;
		while(p1!=NULL){
			same=1;
			for(i=0;i<9;i++)
				if(p1->data[i]!=p->data[i])
					same=0;
				if(same)
					return 1;
				p1=p1->next;
		}
		return 0;
}


//函数名称：vexnode *copy(vexnode *p);
//函数功能：复制节点
//入口参数：被复制节点指针
//出口参数：返回复制节点指针
vexnode *copy_vexnode(vexnode*p){
	vexnode*p1;
	p1=create_vexnode();
	int i;
	for(i=0;i<9;i++)
		(p1->data)[i]=(p->data)[i];
	p1->layer=p->layer;
	p1->diff=p->diff;
	p1->weight=p->weight;
	return p1;
}


//函数名称：print_vexdata(int data[])
//函数功能：打印节点的八数码数据
//入口参数：一维数组(视为八数码)
//出口参数：无
void print_vexdata(int data[]){
	int i=0;
	for(i=0;i<9;i++){
		if((i%3)==0)
			printf("\n");
		printf("%d  ",data[i]);
	}
}


//函数名称：print_allvex(vexnode *p)
//函数功能：采用递归，输出从目标节点到初始节点路径
//入口参数：一维数组(视为八数码)，移动方向 
//出口参数：当前输出节点的层数
int print_allvex(vexnode*p){
	vexnode*p1=p;
	int layer;
	if(p1!=NULL){
		layer=print_allvex(p1->father);
		printf("\n");
		print_vexdata(p1->data);
		return layer+1;
	}
		else
			return -1;
}



//函数名称：free_stru(vexnode*root)
//函数功能：释放节点表
//入口参数：表入口指针
//出口参数：无
void free_stru(vexnode*root){
	vexnode*p1,*p2;
	p1=root->next;
	while(p1!=NULL){
		p2=p1->next;
		free(p1);
        p1=p2;
	}
	free(root);
}







			
//函数名称:mian()
//函数功能：主程序执行
//入口参数：无
//出口参数：无
void main(){
	vexnode *p1,*p2;
	int op;
	int node_num,total_step;
	open_root=create_vexnode();
    close_root=create_vexnode();
	open_root->prio=open_root->next=NULL;
	close_root->prio=close_root->next=NULL;

	p1=create_vexnode();
	p1->father=NULL;
	p1->layer=0;
	input_data(origin_data,target_data);
	data_solution(origin_data,target_data);
	
	copy(p1->data,origin_data);
    insert_open(open_root,p1);
    node_num=1;
	p1=remove_open(open_root);
while(p1!=NULL){
	if(node_num<=MAXVEX){
		ADD_close(close_root,p1);
		for(op=1;op<=4;op++){
			p2=copy_vexnode(p1);
			do_direct(p2->data,op);
			if(has_appear(open_root,close_root,p2)!=1){
				p2->father=p1;
				p2->layer=p1->layer+1;
				p2->diff=compare(p2->data,target_data);
				p2->weight=p2->layer+p2->diff;
				if(compare(p2->data,target_data)==0){
					total_step=print_allvex(p2);
					printf("\n总步数为：%d\n",total_step);
					free_stru(open_root);
					free_stru(close_root);
				}//if(compare)
				else{
			     node_num++;
				 insert_open(open_root,p2);
				}//else
			}//if(has_appear)
			else{
				free(p2);
			}//else
		}//for
		p1=remove_open(open_root);
	}//if(node_num)
    else {
		printf("\n抱歉，此八数码无解！\n");
	}//else
}//while
	
	printf("\n无解!\n");
}