1、 1 / 9 数据结构 课程设计报告 设计题目： 马踏棋盘 院 系 计算机学院 年 级 11 级 学 生 xxxxxxx 学 号 xxxxxxxxx 指导教师 xxxxxxxxx 起止时间 9-6/9-13 2013 年 9 月 10 日星期二 2 / 9 目目 录录 一、一、 课程设计目的课程设计目的 -3 3 二二、 需求需求分析分析-3 三、程序源代码、程序源代码- 4 四四、调试分析、调试分析-7 五、问题五、问题总结总结-8 六、六、参考资料参考资料-9 3 / 9 一、一、 课程设计目的课程设计目的 (1) 熟练使用 C 语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算
2、法的设计方法，具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法 和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 二、二、 需求分析需求分析 问题描述问题描述: :将马随机放在国际象棋的 8X8 棋盘中的某个方格中， 马按走棋规 则进行移动。要求每个方格上只进入一次，走遍棋盘上全部 64 个方格。编制递 归程序，求出马的行走路线 ，并按求出的行走路线，将数字 1，2，64 依 次填入 8X8 的方阵输出之。测试数据:由读者指定可自行指定一个马的初始位 置。实现提示:每次在多个可走位置中选择一个进行试探，其余未
3、曾试探过的可 走位置必须用适当结构妥善管理，以备试探失败时的“回溯”悔棋使用。并探讨 每次选择位置的“最佳策略” ，以减少回溯的次数。 背景介绍：背景介绍： 国际象棋为许多令人着迷的娱乐提供了固定的框架， 而这些框架常独立于游 戏本身。其中的许多框架都基于骑士奇异的 L 型移动规则。一个经典的例子是骑 士漫游问题。 从十八世纪初开始， 这个问题就引起了数学家和解密爱好者的注意。 简单地说，这个问题要求从棋盘上任一个方格开始按规则移动骑士，使之成功的 游历国际象棋棋盘的 64 个方格，且每个方格都接触且仅接触一次。 可以用一种简便的方法表示问题的一个解，即将数字 1，64 按骑士到 达的顺序依次
4、放入棋盘的方格中。 一种非常巧妙的解决骑士漫游地方法由 J.C.Warnsdorff 于 1823 年给出。 他 给出的规则是：骑士总是移向那些具有最少出口数且尚未到达的方格之一。其中 出口数是指通向尚未到达方格的出口数量。在进一步的阅读之前，你可以尝试利 用 Warnsdorff 规则手工构造出该问题的一个解。 实习任务：实习任务： 编写一个程序来获得马踏棋盘即骑士漫游问题的一个解。 您的程序需要达到下面的要求： 棋盘的规模是 8*8； 对于任意给定的初始化位置进行试验，得到漫游问题的解； 对每次实验，按照棋盘矩阵的方式，打印每个格被行径的顺序编号。 技术提示：技术提示： 解决这类问题的关键
5、是考虑数据在计算机中的存储表示。 可能最自然的表示 方法就是把棋盘存储在一个 8*8 的二维数组 board 中。以(x,y)为起点时骑士可 能进行的八种移动。一般来说，位于(x,y)的骑士可能移动到以下方格之一： (x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、 (x-1,y-2)、(x-2,y-1)。但请注意，如果(x,y)的位置离某一条边较近，有些可 4 / 9 能的移动就会把骑士移到棋盘之外，而这当然是不允许的。骑士的八种可能的移 动可以用一个数组 MoveOffset 方便地表示出来： MoveOffset0=(-2,1) MoveOffset1=(-1,2) MoveOffset2=(1,2) MoveOff
