请回答,八数码问题在什么情况下有解?
本篇文章给大家谈谈《请回答,八数码问题在什么情况下有解?》对应的知识点，希望对各位有所帮助。
本文目录一览：
如何用c++编程实现8数码难题
八数码问题 有一个3*3的棋盘，其中有0-8 9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态 1 2 3 4 5 6 7 8 0 到达目标状态步数最少的解。 其典型算法是广度优先搜索，具体算法是： struct 类名 m_ar[可能结点数]; int h,r main() ...
人工智能的八数码问题，过程化的c语言编程方法，求解，好的话要多少分给多少分！！！
#include stdio.h
#include stdlib.h
#define TIME 50 //限定只搜索前50步，50步以后如果仍然没有搜索到结果，认为无解。
#define MAXSIZE 200
int n=1;
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;j9;j++)
if(store[temp].num[j]!=result[j])
return 0;
return 1;
}
void printResult() //输出搜索结果。
{
for(int j=1;j=n;j++)
{
printf("第%d步搜索后：n",j);
printf("t%dt%dt%dn",store[j].num[0],store[j].num[1],store[j].num[2]);
printf("t%dt%dt%dn",store[j].num[3],store[j].num[4],store[j].num[5]);
printf("t%dt%dt%dn",store[j].num[6],store[j].num[7],store[j].num[8]);
printf("nn");
}
}
int left(int temp) //将空格进行左移操作。
{
for(int j=0;j9;j++) //判断空格的位置。
if(store[temp].num[j]==0)
break;
if(j==0||j==3||j==6)
return 0;
for(int k=0;k9;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) //将空格进行右移操作。
{
for(int j=0;j9;j++)
if(store[temp].num[j]==0)
break;
if(j==2||j==5||j==8)
return 0;
for(int k=0;k9;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) //将空格进行上移操作。
{
for(int j=0;j9;j++)
if(store[temp].num[j]==0)
break;
if(j==0||j==1||j==2)
return 0;
for(int k=0;k9;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) //将空格进行下移操作。
{
for(int j=0;j9;j++)
if(store[temp].num[j]==0)
break;
if(j==6||j==7||j==8)
return 0;
for(int k=0;k9;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;i9;i++)
scanf("%d",start.num[i]);
for(int k=0;k9;k++)
if(start.num[k]==0)
break;
start.banOperate='C';
start.expension='Y';
start.father=-1;
store[0]=start; //将初始状态赋于store[0]。
}
void main(){
init();
if(same(0))
{
printf("没有必要进行搜索，初始状态即为最终状态!");
exit(1);
}
for(int i=0;iTIME;i++) //开始进行宽度搜索，限定搜索上限为50步。
{
if(store[i].expension='Y')
{
if(store[i].banOperate=='L')
{
up(i);
right(i);
down(i);
}
if(store[i].banOperate=='R')
{
left(i);
up(i);
down(i);
}
if(store[i].banOperate=='U')
{
left(i);
right(i);
down(i);
}
if(store[i].banOperate=='D')
{
left(i);
up(i);
right(i);
}
if(store[i].banOperate=='C')
{
left(i);
up(i);
right(i);
down(i);
}
}
if(n=TIME) //50步以后仍然没有达到所要求的状态，认为无解。
{
n--;
printResult();
printf("Sorry，在所在搜索范围内没有搜索到结果！");
exit(1);
}
}
}
八数码会不会无解
会的。八数码问题本身就有可能是无解的，这和用什么算法什么语言无关。
如果从初始状态成为下面的状态：
1
2
3
4
5
6
8
7
而通常的目标状态如下:
1 2 3
4 5 6
7 8
就是无解的。
关于《请回答,八数码问题在什么情况下有解?》的介绍到此就结束了。
