数字华容道问题的设计与实现.doc

数字华容道问题的设计与实现实验报告班级：计本四班 学号：2012020386 姓名：刘宝同一、问题描述重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”，后来流传到欧洲，将人物变成数字。原始的重排九宫问题是这样的：将数字 18 按照任意次序排在 33 的方格阵列中，留下一个空格。与空格相邻的数字，允许从上，下，左，右方向移动到空格中。游戏的最终目标是通过合法移动，将数字 18 按行排好序。在一般情况下，n2-1 谜问题是将数字 1n2-1 按照任意次序排在 nn 的方格阵列中，留下一个空格。允许与空格相邻的数字从上，下，左，右 4个方向移动到空格中。游戏的最终目标是通过合法移动，将初始状态变换到目标状态。n2-1谜问题的目标状态是将数字 1n2-1 按从小到大的次序排列，最后一个位置为空格。二、问题求解分析编程任务：对于给定的 nn 方格阵列中数字 1n2-1 初始排列，编程计算将初始排列通过合法移动变换为目标状态最少移动次数。数据输入：由文件 input.txt 给出输入数据。文件的第 1 行有 1 个正整数 n。以下的 n 行是 nn 方格阵列的中数字 1n2-1 的初始排列，每行有 n 个数字表示该行方格中的数字， 0 表示空格。结果输出:将计算出的最少移动次数和相应的移动序列输出到文件 output.txt。第 1 行是最少移动次数。从第 2 行开始，依次输出移动序列。三、源程序关键代码#include#include#include#define Overflow 1#define N 3int goalNN=1,2,3,8,0,4,7,6,5;int zero2,NodeQTY=0;int *z=zero;/记录0的位置，zero0:r行；zero1:c列 typedef int Piece;struct Chessboard/棋盘信息 Piece posNN;/记录每个数码a的位置r行c列int d,f,move;/d:深度；f:启发函数值 ；move:父节点移动到该节点的方式 ;struct LNodeChessboard board;LNode *parent,*next;bool flag;typedef LNode* List;int* Findzero(LNode* &Node)int i,j,zr2;int *z=zr;for(i=0;iN;i+)for(j=0;jboard.posij=0)zr0=i+1;zr1=j+1;break;return z;int Wrong(LNode *Node)int w=0,i,j;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)w+;return w;int pick(LNode *Node)int w=0,i,j,ii,jj;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)for(ii=0;iiN;ii+)for(jj=0;jjboard.posij=goaliijj) w=w+abs(ii-i)+abs(jj-j);break; return w;LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)LNode* NewNode=new LNode;for(int i=0;iN;i+)for(int j=0;jboard.posij=Node-board.posij;switch(moveflag)case 1:/向左移，不能出界：zero1=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1-2;NewNode-board.poszero0-1zero1-2=0;break;case 2:/向右移，不能出界：zero1board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1;NewNode-board.poszero0-1zero1=0;break;case 3:/向上移，不能出界：zero0=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-2zero1-1;NewNode-board.poszero0-2zero1-1=0;break;case 4:/向下移，不能出界：zero0board.poszero0-1zero1-1=NewNode-board.poszero0zero1-1;NewNode-board.poszero0zero1-1=0;break;NewNode-board.d=depth+1;switch(Choose)case 1:NewNode-board.f=NewNode-board.d+Wrong(NewNode);break; case 2:NewNode-board.f=NewNode-board.d+pick(NewNode);break; NewNode-board.move=moveflag;NewNode-parent=Node;NodeQTY+; return NewNode;void InitList(LNode* &Open,LNode* &Close)Open=(List)malloc(sizeof(LNode);Close=(List)malloc(sizeof(LNode);if(!Open&!Close)exit(Overflow);Open-next=NULL;Close-next=NULL;int ListInsert(List &L,LNode* NewNode)List p=L;while(p-next)p=p-next;NewNode-next=p-next;p-next=NewNode;return true;LNode* Getminf(List &L)List p=L,q=L-next,r=L,min;min=q;/p,q寻找f最小值的指针，r指向表L中min前一个元素 if(!q)return NULL;while(q)if(min-board.fq-board.f)r=p;min=q;p=q;q=q-next;r-next=min-next;min-next=NULL;return min;int main()int i,j,choose;List Open,Close;LNode *Best,*current;LNode *Start=new LNode;printf(ttt八 数 码 问 题 求 解n); printf(n请输入初始状态：);for(i=0;iN;i+)for(j=0;jboard.posij);printf(注:The flag of movement-1:左移;2:右移;3:上移;4:下移)n);printf(初始棋盘状态：n); for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);InitList(Open,Close); printf(请选择(1:A算法;2:A*算法):); scanf(%d,&choose); Start-board.d=0;switch(choose)case 1:Start-board.f=Start-board.d+Wrong(Start);break; case 2:Start-board.f=Start-board.d+pick(Start);break; /Start-board.f=0+Wrong(Start);Start-board.move=0;Start-parent=NULL;Start-next=NULL;Start-flag=1;ListInsert(Open,Start);/将S加入到Open表中 while(Open-next)Best=Getminf(Open);ListInsert(Close,Best);if(!(Best-board.f-Best-board.d)printf($*有解！*$n); break;z=Findzero(Best);zero0=*(z+0);zero1=*(z+1);if(zero1=N-1&Best-board.move!=2)ListInsert(Open,extend(Best,Best-board.d,zero,1,choose);if(zero1board.move!=1)ListInsert(Open,extend(Best,Best-board.d,zero,2,choose);if(zero0=N-1&Best-board.move!=4)ListInsert(Open,extend(Best,Best-board.d,zero,3,choose);if(zero0board.move!=3)ListInsert(Open,extend(Best,Best-board.d,zero,4,choose);printf(本算法搜索图中总共扩展的节点数为：%dn,NodeQTY); printf(t最佳路径如下所示：n); if(Open-next)while(Best-parent)Best-flag=1;Best=Best-parent;List p=Close-next,q=Close-next;if(p=Start) q=p-next;else exit(1);int Step=0; while(p&q)/在Close表中依标记找到路径 if(q-flag=1&q-parent=p)printf(Step %d:0 move as the %d-flag of movement.n,+Step,q-board.move);for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);p=q;/记住父节点 q=q-next;prin