文档介绍：《数字华容道问题的设计与实现》实验报告
班级:计本四班 学号:201２02０386 姓名：刘宝同
一、问题描述
重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事
“关羽义释曹操”而设计的智力玩具“华容道”,后来流传到欧洲,将人物变成数字。原始
的重排九宫问题是这样的:将数字 １～8 按照任意次序排在 3×3 的方格阵列中,留下一个空格。与空格相邻的数字，允许从上，下,左,右方向移动到空格中。游戏的最终目标是通过合法移动,将数字 1～8 按行排好序。在一般情况下,n２-1 谜问题是将数字 1~ｎ２-１ 按照任意次序排在 n×n 的方格阵列中,留下一个空格。允许与空格相邻的数字从上，下,左,右 4个方向移动到空格中。游戏的最终目标是通过合法移动,将初始状态变换到目标状态。ｎ2-1谜问题的目标状态是将数字 １~n２-1 按从小到大的次序排列，最后一个位置为空格。
二、问题求解分析
编程任务:对于给定的 n×ｎ 方格阵列中数字 1~n２-1 初始排列,编程计算将初始排列通过合法移动变换为目标状态最少移动次数。
数据输入:由文件 给出输入数据。文件的第 1 行有 1 个正整数 n。以下的 n 行是 n×n 方格阵列的中数字 1~n2-１ 的初始排列，每行有 n 个数字表示该行方格中的数字, ０ 表示空格。
结果输出:将计算出的最少移动次数和相应的移动序列输出到文件 ｏutput．txt。第 １ 行是最少移动次数。从第 2 行开始，依次输出移动序列。
三、源程序关键代码
 
#ｉｎcｌuｄｅ<＞
#inｃlｕdｅ<mａｌloc．h＞
#inｃｌｕｄｅ＜ｓtdlib．h＞
#define Ovｅrｆlow １
#defｉne N 3
int gｏal[N]［N］=｛１,2，３,8,０,4,7,6,5};
ｉnt ｚero[2],NｏdeQＴＹ=0;
int *z=zｅro；／／记录0的位置，ｚero[0］:r行;ｚeｒo[1]:c列
typeｄef ｉnt Piｅce;
struct Cｈesｓboarｄ｛／/棋盘信息
ﻩPiｅcｅ pｏs[N］[N］;／/记录每个数码a的位置r行ｃ列
ﻩint ｄ,ｆ,moｖe;/／ｄ:深度;ｆ:启发函数值 ;move：父节点移动到该节点的方式
};
ｓtrucｔ ＬNoｄe{
ﻩＣhessｂｏａrd ｂoarｄ;
ﻩＬＮode ＊parenｔ，*ｎｅxt;
ｂｏｏｌ flag;
};
tｙpｅｄｅf ＬNoｄe＊ Lｉst;
int* Fiｎdｚero(ＬＮodｅ* &Node）
{
ﻩint ｉ,j，ｚｒ[2]；
ﻩint ＊ｚ=ｚr;
ﻩfoｒ(i=0；ｉ<Ｎ；i＋+){
ﻩﻩfor(j=0;j<Ｎ;j＋+){
ﻩ ﻩｉｆ（Ｎoｄｅ->[i][j]==０){
ﻩﻩﻩﻩzr[0]=ｉ＋１；
ﻩﻩﻩﻩｚr［1］=j+1;
ﻩﻩﻩﻩｂreak;
ﻩﻩﻩ}
ﻩﻩ}
｝
ﻩｒetｕrn z;
}
ｉｎt Wroｎｇ(LNodｅ ＊Ｎoｄｅ）
{
ﻩint ｗ=0,ｉ,j；
ﻩfor(i＝０;i<Ｎ；ｉ++)｛
ﻩﻩｆor(j=０；j