八数码问题

使用了A*算法

#include <stdio.h>

#include <stdlib.h>
#define TIME 50 //限定只搜索前50步，50步以后如果仍然没有搜索到结果，认为无解。
#define MAXSIZE 200
int n=1;
int* level=new int[10];//用来标志扫描的树的扩展次数
int* path=new int[10];//用来记录最佳路径
int pathLength=0;//用来记录最佳路径大小
int current,p=0;//回溯时用到的辅助变量


int k=0;
int result[9]={1,2,3,8,0,4,7,6,5};//所要达到的最终状态，0代表空格。
typedef struct{
int num[9];
char expension; //记录是否可以扩展，Y代表可以扩展，N代表不可以。
char banOperate; //表示不可以执行的操作，'L'代表不能左移，'R'代表不能右移，
//'U'代表不能上移，'D'代表不能下移，'C'代表可以任意移动。
int father; //记录父节点的下标。
}Node;
Node store[MAXSIZE]; //将搜索过的状态存储于该数组中。


int same(int temp) //判断是否达到了目标状态。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]!=result[j])
return 0;
return 1;
}




//---------------------------------------------------------A*算法------------------------------------------------------------------------

int index(int now ,int des){//两个位置相差的步数


int dif=abs(now-des);

if(dif==3){

return 1;

}
else if(dif==6||dif==2){
return 2;
}else if(dif==4){

if(now==3||now==7)
{


return 4;
}
else {return 2;}

}else if(dif==1){

if(now+des==5||now+des==11)

return 3;

else {
return 1;
}
}else if(dif==5)
{
return 3;
}else if(dif==7){
return 3;
}else if(dif==8)
{
return 4;
}



return 0;




}






int guess(int temp)//计算该状态的估价函数
{
int now;
int des;
int value=0;
for(int j=0;j<9;j++)
if(store[temp].num[j]!=result[j])
{
if(store[temp].num[j]==0)
continue;
now=j;
for(int i=0;i<9;i++){

if(store[temp].num[j]==result[i])
{des=i;
break;

}



}

value+=index(now,des);

}
return value;






}



//----------------------------------------------------------------------------




void cut(int m,int count){//根据估价函数剪枝
int min;
m-=count;
int temp;



int* gue=new int[count];


gue[0]=min=temp=guess(m);




for(int j=1;j<count;j++)
{
gue[j]=temp=guess(++m);

if(min>temp)
min=temp;
}
m-=count;
m++;

for(int j=0;j<count;j++)

{
if(gue[j]!=min)
{

store[m+j].expension='N';
//printf("dsfs");
}
}


}


















































void printResult() //输出搜索结果。
{
int count=1;
int r=0;

printf("从顶点开始第1次扩展---------------------------\n");
for(int j=1;j<=n;j++)
{


printf("第%d步搜索后：\n",j);
printf("\t%d\t%d\t%d\n",store[j].num[0],store[j].num[1],store[j].num[2]);
printf("\t%d\t%d\t%d\n",store[j].num[3],store[j].num[4],store[j].num[5]);
printf("\t%d\t%d\t%d\n",store[j].num[6],store[j].num[7],store[j].num[8]);
printf("\n\n");
if(j+1==level[r])
{
r++;
count++;
printf("第%d次扩展---------------------------------\n",count);
printf("\n");
}

}


printf("以下输出最佳路径及其大小---------------------------\n");




current= n;
path[0]=current;

p=1;
while(1){
if(store[current].father==-1)
break;


path[p]=store[current].father;
current=path[p];
p++;

}
pathLength=p-1;


for(int j=p-1;j>=0;j--){
printf("第%d步-------------------------------\n",p-j-1);
printf("\t%d\t%d\t%d\n",store[path[j]].num[0],store[path[j]].num[1],store[path[j]].num[2]);
printf("\t%d\t%d\t%d\n",store[path[j]].num[3],store[path[j]].num[4],store[path[j]].num[5]);
printf("\t%d\t%d\t%d\n",store[path[j]].num[6],store[path[j]].num[7],store[path[j]].num[8]);
printf("\n\n");


}
printf("最佳路径长度为：%d\n",pathLength);


}




int left(int temp) //将空格进行左移操作。
{
int j;
for(j=0;j<9;j++) //判断空格的位置。
if(store[temp].num[j]==0)
break;
if(j==0||j==3||j==6)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j-1]; //将移动后的状态赋给store[n]
store[n].num[j-1]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='R';
store[n].expension='Y';
store[n].father=temp;
if(same(n)) //判断store[n]是否为最终想得到的状态。
{
printResult();
exit(1);
}
n++;
return 1;
}


int right(int temp) //将空格进行右移操作。
{int j;
for(j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==2||j==5||j==8)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j+1];
store[n].num[j+1]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='L';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}


int up(int temp) //将空格进行上移操作。
{int j;
for(j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==0||j==1||j==2)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j-3];
store[n].num[j-3]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='D';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}


int down(int temp) //将空格进行下移操作。
{
int j;
for(j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==6||j==7||j==8)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j+3];
store[n].num[j+3]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='U';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}


void init()
{
Node start;
printf("请输入初始状态，用空格分开，0代表空格:\n");//输入初始的状态。
for(int i=0;i<9;i++)
scanf("%d",&start.num[i]);
for(int k=0;k<9;k++)
if(start.num[k]==0)
break;
start.banOperate='C';
start.expension='Y';
start.father=-1;
store[0]=start; //将初始状态赋于store[0]。
}
int main(){
init();


if(same(0))
{
printf("没有必要进行搜索，初始状态即为最终状态!");
exit(1);
}


for(int i=0;i<TIME;i++) //开始进行宽度搜索，限定搜索上限为50步。
{
if(store[i].expension=='Y')
{
if(store[i].banOperate=='L')
{
up(i);
right(i);
down(i);


cut(n,3);
level[k++]=n;



}
if(store[i].banOperate=='R')
{
left(i);
up(i);
down(i);


cut(n,3);
level[k++]=n;
}
if(store[i].banOperate=='U')
{
left(i);
right(i);
down(i);


cut(n,3);
level[k++]=n;
}
if(store[i].banOperate=='D')
{
left(i);
up(i);
right(i);


cut(n,3);
level[k++]=n;
}
if(store[i].banOperate=='C')
{
left(i);
up(i);
right(i);
down(i);



cut(n,4);
level[k++]=n;
}
}
if(n>=TIME) //50步以后仍然没有达到所要求的状态，认为无解。
{
n--;
printResult();
printf("Sorry，在所在搜索范围内没有搜索到结果！");
exit(1);
}
}



return 0;
}