#include<stdio.h> #include<conio.h>
int n,m; typedef struct Node { char matrix[10];/*存储矩阵*/ char operate;/*存储不可以进行的操作,L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/ char extend;/*是否可以扩展,Y代表可以,N代表不可以*/ int father;/*指向产生自身的父结点*/ }Node; char start[10]={"83426517 "};/*此处没有必要初始化*/ char end[10]={"1238 4765"};/*此处没有必要初始化*/ Node base[4000]; int result[100];/*存放结果的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 http://www.zhensoft.com ZHEN SHI LEI\t\tStep %d",i); 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[20],b[20]; n=1;
textcolor(LIGHTGREEN); clrscr();
/*以下是输入初始和目标矩阵,并把输入的0转换为空格*/ printf("Please input the start 9 chars:"); scanf("%s",a); printf("Please input the end 9 chars:"); scanf("%s",b); for(i=0;i<9;i++) { if(a[i]=='0') { start[i]=' '; continue; } if(b[i]=='0') { end[i]=' '; continue; } start[i]=a[i]; end[i]=b[i]; } start[9]='\0'; end[9]='\0';
for(i=0;i<9;i++) { base[0].matrix[i]=start[i]; } base[0].operate='N'; base[0].extend='Y'; base[0].father=-1; /*以上是为第一个base数组元素赋值*/
for(i=0;n<4000;i++) { if(base[i].extend=='Y') { if(base[i].operate=='L') { right(i);up(i);down(i); } if(base[i].operate=='R') { left(i);up(i);down(i); } if(base[i].operate=='U') { left(i);right(i);down(i); } if(base[i].operate=='D') { left(i);right(i);up(i); } if(base[i].operate=='N') { left(i);right(i);up(i);down(i); } } } }

|