人工智能 实验报告 专 业： 姓 名： 实验地点： 指导老师： 实验日期： 1 

《八数码》实验报告 姓 名 题 目 目 的 班 级 学 号 基于人工智能研究 ——八数码问题求解 熟悉对八数码问题的建模、求解及编程语言的应用。 程序主要功能： 八数码问题：在 3×3 的方格棋盘上，摆放着 1 到 8 这八个数码，有 1 个方格是空的，其初始状 态如图 1 所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初 始状态到目标状态。 实验步骤 （1） 分析算法基本原理和基本流程； （2） 确定对问题描述的基本数据结构； （3） 编写算符运算、目标比较等函数； （4） 编写算符运算、目标比较等函数； （5） 编写输入、输出接口； （6） 撰写实验报告。 收获与体会： 这次作业让我的编程能力有了很大的提高，查阅资料等能力也有很大的提升，并且写出双向宽度 遍历，深度遍历以及启发式搜索算法。我对人工智能技术有了进一步的认识，在解决问题和算法设计 上的能力也极大地提高。 附源程序。 #include #include int n,m; typedef struct Node { char matrix[10];/*存储矩阵*/ char operate;/*存储不可以进行的操作，L 代表不能左移 R 代表不能右移 U 代表不能上移 D 代表不能 下移*/ 2 

father;/*指向产生自身的父结点 char extend;/*是否可以扩展，Y 代表可以，N 代表不可以*/ int */ }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; } } i++; } } //clrscr(); return 1; } void show()/*显示矩阵的内容*/ { int i=1; while(m>=0) { int mm=result[m]; printf("\n\n\n 状态方格\t\t 步骤 %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--; 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\t 搜索结束\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) { 3 

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; } 4 

continue; } if(b[i]=='0') { end[i]=' '; 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); } } } } 5