马踏棋盘_试验报告重点讲义资料

1 西安交通大学实验报告课程数据结构专题实验实验名称马踏棋盘第 1 页共 9 页系别 __ 自动化实验日期 2015 年 11 月 8 日专业班级自动化 43 班实验 报 告 日 期 2015 年 11 月 15 日姓 名李欣阳学号2140504066 报告退发 ( 订正、 重做 ) 同 组 人无教 师 审 批 签 字一、实验目的通过本次试验， 熟练掌握抽象数据类型栈和队列的实现，学会用栈和队列解决具体应用问题，从而体会栈和队列的特点。二、实验内容与要求设计一个国际象棋的马踏棋盘的演示程序，满足：将马随机放在国际象棋8×8 棋盘 Broad[8][8] 的某方格中，马按走棋规则进行移动。可以允许回溯，最终成功走遍棋盘上64 个方格。编制非递归程序，求出马的行走路线，按求出的行走路线，将数字 1，2，3，···，64 依次填入一个 8×8 方阵，并输出该方阵。三、问题分析3.1 下一个位置的确定一般来说 , 当马处于位置 ( i ，j )时，可以走到下列八个位置之一，这些位置称之为该位置的邻接位置：( i-2，j+ 1 )，( i-1，j+2 )，( i+ 1，j+ 2 )，( i + 2，j+ 1 ) ( i+ 2，j+ 1 )，( i+ 1，j - 2)，( i-1，j-2 )，( i-2，j -1 ) 给以上八个位置依次编号，在棋盘上显示如下图：⑧①⑦②Δ⑥③⑤④图 1 某位置的八个邻接位置但是如果 ( i ，j )靠近棋盘边缘，八个邻接位置中可能有些位置超出棋盘范围，2 那些不允许的位置就不能成为下一步的选择。这八个邻接位置可以用两个一维数组 HTry1[8] 和 HTry2[8] 来表示：HTry1[8]={ -2，-1，1，2，2，1，-1，-2} HTry2[8]={ 1，2，2，1，-1，-2，-2，-1} 位于 ( i ，j )的马可以走到的新位置是在棋盘范围内的(i+ HTry1[h] ，j+ HTry2[h]) ，其中 h=0，1，· · ·，7。每次在所有可走的位置中选择一个进行试探，已经走过的位置标记为步数（比如第 5 步走到该格， 则该格标记为 5），未走过的位置标记为0。为了使马能最大可能性的走完整个棋盘并且减小计算次数，应该让马优先走难走的地方， 即邻接位置最少的那些位置（主要指四角和边缘）。在棋盘上标记出每个位置的邻接位置，如下图：2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 图 2 每个位置的临接位置数3.2 回溯...