1.cpp

人工智能实验题目——回溯算法解决8数码问题

#include<iostream>
#include<fstream>
using namespace std;

static int markall[9*8*7*6*5*4*3*2][9]={0};//标志数组
static int stack[9*8*7*6*5*4*3*2][11]={0};//九数码+空格所在位置+移动方向
int fbiao=0,sbiao=0;//标志数组和自定义栈的游标

ifstream infile;//声明输入流
	ofstream outfile;//声明输出流

//栈的基本操作
void push(int* g){
	for(int i=0;i<11;i++) stack[sbiao][i]=g[i];
	sbiao++;
}

void pop(int* g){
		for(int i=0;i<11;i++) g[i]=stack[sbiao][i];
		sbiao--;
}
//移动方向函数
int up9(int* g){ 
	if(g[9]<=2) return 0;
	int temp=g[g[9]];g[g[9]]=g[g[9]-3];g[g[9]-3]=temp;
	g[9]-=3;
	return 1;
}

int left9(int* g){
	if ((g[9]==0)||(g[9]==3)||(g[9]==6)) return 0;
	int temp=g[g[9]];g[g[9]]=g[g[9]-1];g[g[9]-1]=temp;
	g[9]-=1;
	return 1;
}

int down9(int* g){
	if (g[9]>=6) return 0;
	int temp=g[g[9]];g[g[9]]=g[g[9]+3];g[g[9]+3]=temp;
	g[9]+=3;
	return 1;
}

int right9(int* g){
	if ((g[9]==2)||(g[9]==5)||(g[9]==8)) return 0;
	int temp=g[g[9]];g[g[9]]=g[g[9]+1];g[g[9]+1]=temp;
	g[9]+=1;
	return 1;
}
//搜索空格位置的函数
int find9(int* g,int t){
	for(int i=0;i<9;i++) 
		if(g[i]==t) return i;
		return 0;
}
//相等判断函数
int equal9(int* g1,int* g2){
	for(int i=0;i<9;i++){
		if(g1[i]==g2[i]) continue;
		else break;
		 
	}
	if(i==9) return 1;
	return 0;
}
//显示函数
void display(int* g){
	for(int i=0;i<9;i++){
		if(i==0||i==3||i==6) outfile<<endl;
		outfile<<g[i]<<" ";
	}
outfile<<endl;
}
//标志动作函数
void mark(int* g){
	for(int i=0;i<9;i++) markall[fbiao][i]=g[i];
	fbiao++;
}
//检查标志函数
int checkmark(int* g,int &n){
	int i,j;
	for(j=fbiao;j>=0;j--){
		for(i=0;i<9;i++)
			if (markall[j][i]!=g[i]) break;
			if(i==9) {
				n=j;
				return 1;
			}
	}
	
	return 0;
}
//******************************************************************
//回溯过程
int hs(int* g1,int* g2){
	int i,temp,	nocontinue,wz;//nocontinue=1 有退栈的标志;wz的作用只用在退栈时的 markall操作
	for(i=0;i<9;i++)
		if(g1[i]==g2[i]) continue;
		else break;

		if(i==9) {
			outfile<<"success!\n";
			return 0;
		}
//0,1,2,3分别代表上下左右
		int sg1[11]={g1[0],g1[1],g1[2],g1[3],g1[4],g1[5],g1[6],g1[7],g1[8],find9(g1,9),0};
		push(sg1);
        mark(sg1);
        display(sg1);



		while(sbiao!=0){
//初始化方向，回溯的性质
			sg1[10]=0;	
					
			if(nocontinue==1){
				sg1[10]=temp+1;
	
			}
//判断操作
				for(i=0;i<9;i++)
		if(sg1[i]==g2[i]) continue;
		else break;

		if(i==9) {
			outfile<<"success!******************************************************\n";
			display(sg1);
			return 0;
		}
//后续循环操作，利用栈进行回溯，按上、左、下、右的顺序
		//////////////////////////////////////////////////////////////////////////////////////////////////
			if(sg1[10]==0){
			
			
				if(sg1[9]>=3){
				up9(sg1);
			if(!checkmark(sg1,wz)) {
				display(sg1);
				push(sg1);
				mark(sg1);
					nocontinue=0;//没有退栈，自动归零
			 continue;
			}
			else 
				down9(sg1);
				}
	if((nocontinue==0)||(sg1[10]<1)) 		sg1[10]++;//注意，这里不加一的情况是为了退栈后直接跳到上一个方阵的移动方向
			
			}
///////////////////////////////////////////////////////////////////////////////////////////
			if(sg1[10]==1){
			
			
				if(!(sg1[9]==0||sg1[9]==3||sg1[9]==6)){
				left9(sg1);
			if(!checkmark(sg1,wz)){
				display(sg1);
				push(sg1);
				mark(sg1);
				nocontinue=0;//没有退栈，自动归零

			 continue;
			}
			else
				right9(sg1);
				}
	if((nocontinue==0)||(sg1[10]<2))		sg1[10]++;//注意，这里不加一的情况是为了退栈后直接跳到上一个方阵的移动方向
			
			}
/////////////////////////////////////////////////////////////////////////////////////
			if(sg1[10]==2){
			
			
				if(sg1[9]<=5 ){
				down9(sg1);
				if(!checkmark(sg1,wz)) {
				display(sg1);
				push(sg1);
				mark(sg1);
					nocontinue=0;//没有退栈，自动归零
			 continue;
			}
				else
					up9(sg1);
				}
		if((nocontinue==0)||(sg1[10]<3))	sg1[10]++;//注意，这里不加一的情况是为了退栈后直接跳到上一个方阵的移动方向
				

			}
//////////////////////////////////////////////////////////////////////////////////////////////////
			if(sg1[10]==3){
			
			
				if(!(sg1[9]==2||sg1[9]==5||sg1[9]==8)){
				right9(sg1);
			if(!checkmark(sg1,wz)) {
				display(sg1);
				push(sg1);
				mark(sg1);
				nocontinue=0;//没有退栈，自动归零
			 continue;
			}
			else left9(sg1);//无操作时退栈
				}
			}
			temp=stack[sbiao][10];
			checkmark(stack[sbiao],wz) ;
			for(int i1=fbiao;i1>wz;i1--)
				for(int i2=0;i2<9;i++)
			markall[i1-1][i2]=markall[i1][i2];

			fbiao--;
			pop(sg1);
	nocontinue=1;//有退栈，自动归一
		}


	return 0;
}
	

int main(){

	infile.open(".\\s.txt");//打开输入的文件
   outfile.open(".\\data.txt");//打开输出的文件

	int a[9],i,b[9];
    outfile<<"first input:\n";
	for(i=0;i<9;i++) infile>>a[i];
	outfile<<"end input:\n";
	for(i=0;i<9;i++) infile>>b[i];
	hs(a,b);

	return 0;
}