用广度优先搜索解决八数码问题，没有语法错误，但调试的时候程序卡在for(i=0;n<40;i++)
{
if(base[n].extend=='Y')
{
没法运行～无法显示出结果，我看了半天也没找出问题，请大家帮忙下。在此拜谢～
/*用广度优先搜索*/
#include<stdio.h>
#include<conio.h>
int n,m;
typedef struct Node
{
char matrix[9];/*存储矩阵*/
char operate;/*存储不可以进行的操作，L代表不能左移,R代表不能右移,U代表不能上移,D代表不能下移*/
char extend;/*是否可以扩展，Y代表可以，N代表不可以*/
int father;/*指向产生自身的父结点*/
}Node;
Node base[40];
char start[9];
char end[9]; /*最终目标*/
int result[10];/*存放结果的base数组下标号，逆序存放*/
int match()/*判断是否为目标*/
{
int i;
for(i=0;i<9;i++)
{
if(base[n-1].matrix[i]!=end[i])
{
return 0;
}
}
return 1;
}
void show()/*显示矩阵的内容*/
{
int i=1;
while(m>=0)
{
int mm=result[m];
clrscr();
printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);
printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);
printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);
sleep(1);
m--;
i++;
}
}
void leave()/*推理成功后退出程序之前要执行的函数，主要作用是输出结果*/
{
n--;
while(base[n].father!=-1)
{
result[m]=n;
m++;
n=base[n].father;
}
result[m]=0;
result[m+1]='\0';
show();
clrscr();
printf("\n\n\n\n\n\n\n\n\n\t\t\t\tThe End\n\n\n\n\n\n\n\n\n\n");
getch();
exit(0);
}
int left(int x)/*把下标为X的数组中的矩阵的空格左移*/
{
int i,j;
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==0||i==3||i==6||i==9)
{
return 0;
}
/*for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}*/
ch=base[n].matrix[i-1];
base[n].matrix[i-1]=base[n].matrix[i];
base[n].matrix[i]=ch;
base[n].operate='R';
base[n].extend='Y';
base[n].father=x;
base[x].extend='N';
n++;
if(match(i))
leave();
return 1;
}
int right(int x)/*把下标为X的数组中的矩阵的空格右移*/
{
int i,j;
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==2||i==5||i==8||i==9)
{
return 0;
}
/*for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}*/
ch=base[n].matrix[i+1];
base[n].matrix[i+1]=base[n].matrix[i];
base[n].matrix[i]=ch;
base[n].operate='L';
base[n].extend='Y';
base[n].father=x;
base[x].extend='N';
n++;
if(match(i))
leave();
return 1;
}
int up(int x)/*把下标为X的数组中的矩阵的空格上移*/
{
int i,j;
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==0||i==1||i==2||i==9)
{
return 0;
}
/*for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}*/
ch=base[n].matrix[i-3];
base[n].matrix[i-3]=base[n].matrix[i];
base[n].matrix[i]=ch;
base[n].operate='D';
base[n].extend='Y';
base[n].father=x;
base[x].extend='N';
n++;
if(match(i))
leave();
return 1;
}
int down(int x)/*把下标为X的数组中的矩阵的空格下移*/
{
int i,j;
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==6||i==7||i==8||i==9)
{
return 0;
}
/*for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}*/
ch=base[n].matrix[i+3];
base[n].matrix[i+3]=base[n].matrix[i];
base[n].matrix[i]=ch;
base[n].operate='U';
base[n].extend='Y';
base[n].father=x;
base[x].extend='N';
n++;
if(match(i))
leave();
return 1;
}
main()
{
int i;
char a[9],b[9];
n=0;
textcolor(LIGHTGREEN);
clrscr();
/*以下是输入初始和目标矩阵，并把输入的0转换为空格*/
printf("Please input the start 9 chars:");
for(i=0;i<9;i++)
scanf("%s",&a[i]);
printf("Please input the end 9 chars:");
for(i=0;i<9;i++)
scanf("%s",&b[i]);
for(i=0;i<9;i++)
{
start[i]=a[i];
end[i]=b[i];
if(a[i]=='0') start[i]=' ';
if(b[i]=='0') end[i]=' ';
}
for(i=0;i<9;i++) /*是为第一个base数组元素赋值*/
{
base[0].matrix[i]=start[i];
}
base[0].operate='N';
base[0].extend='Y';
base[0].father=-1;
for(i=0;n<40;i++)
{
if(base[n].extend=='Y') /*运行到此处无法进行*/
{
if(base[n].operate=='L')
{
right(i);up(i);down(i);
}
if(base[n].operate=='R')
{
left(i);up(i);down(i);
}
if(base[n].operate=='U')
{
left(i);right(i);down(i);
}
if(base[n].operate=='D')
{
left(i);right(i);up(i);
}
if(base[n].operate=='N')
{
left(i);right(i);up(i);down(i);
}
}
}
}
[此贴子已经被作者于2006-6-7 21:29:10编辑过]
