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

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