文档介绍：《数字华容道问题的设计与实现》实验报告班级:计本四班学号:姓名:刘宝同一、问题描述重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”,后来流传到欧洲,将人物变成数字。原始的重排九宫问题是这样的:将数字1~8按照任意次序排在3×3的方格阵列中,留下一个空格。与空格相邻的数字,允许从上,下,左,右方向移动到空格中。游戏的最终目标是通过合法移动,将数字1~8按行排好序。在一般情况下,n2-1谜问题是将数字1~n2-1按照任意次序排在n×n的方格阵列中,留下一个空格。允许与空格相邻的数字从上,下,左,右4个方向移动到空格中。游戏的最终目标是通过合法移动,将初始状态变换到目标状态。n2-1谜问题的目标状态是将数字1~n2-1按从小到大的次序排列,最后一个位置为空格。二、问题求解分析编程任务:对于给定的n×n方格阵列中数字1~n2-1初始排列,编程计算将初始排列通过合法移动变换为目标状态最少移动次数。数据输入:。文件的第1行有1个正整数n。以下的n行是n×n方格阵列的中数字1~n2-1的初始排列,每行有n个数字表示该行方格中的数字,0表示空格。结果输出:。第1行是最少移动次数。从第2行开始,依次输出移动序列。三、源程序关键代码 #include<>#include<>#include<>#defineOverflow1#defineN3intgoal[N][N]={1,2,3,8,0,4,7,6,5};intzero[2],NodeQTY=0;int*z=zero;//记录0的位置,zero[0]:r行;zero[1]:c列typedefintPiece;structChessboard{//棋盘信息 Piecepos[N][N];//记录每个数码a的位置r行c列 intd,f,move;//d:深度;f:启发函数值;move:父节点移动到该节点的方式};structLNode{ Chessboardboard; LNode*parent,*next; boolflag;};typedefLNode*List;int*Findzero(LNode*&Node){ inti,j,zr[2]; int*z=zr; for(i=0;i<N;i++){ for(j=0;j<N;j++){ if(Node->[i][j]==0){ zr[0]=i+1; zr[1]=j+1; break; } } } returnz;}intWrong(LNode*Node){ intw=0,i,j; for(i=0;i<N;i++){ for(j=0;j<N;j++){ if(Node->[i][j]!=goal[i][j]&&Node->[i][j]!=0) w++; } } returnw;}intpick(LNode*Node){ intw=0,i,j,ii,jj; for(i=0;i<N;i++){ for(j=0;j<N;j++){ if(Node->[i][j]!=goal[i][j]&&No