西安交通大学实验报告
课程数据结构专题实验系别__专业班级姓名实验名称马踏棋盘
实验日期第1页共9页
自动化
自动化43班
2140504066
2015年11月8日
实验报告日期2015年11月15日报告退发订正、重做
李欣阳学号无
同组人
教师审批签字
一、实验目的
通过本次试验，熟练掌握抽象数据类型栈和队列的实现，学会用栈和队列解决具体应用问题，从而体会栈和队列的特点。
二、实验内容与要求
设计一个国际象棋的马踏棋盘的演示程序，满足：将马随机放在国际象棋8×8棋盘Broad88的某方格中，马按走棋规则进行移动。可以允许回溯，最终成功走遍棋盘上64个方格。编制非递归程序，求出马的行走路线，按求出的行走路线，将数字1，2，3，，64依次填入一个8×8方阵，并输出该方阵。
三、问题分析
31下一个位置的确定一般来说当马处于位置i，j时，可以走到下列八个位置之一，这些位置称之为该位置的邻接位置：i2，j1，i1，j2，i1，j2，i2，j1i2，j1，i1，j2，i1，j2，i2，j1给以上八个位置依次编号，在棋盘上显示如下图：⑧⑦①②
Δ
⑥⑤④③
图1某位置的八个邻接位置但是如果i，j靠近棋盘边缘，八个邻接位置中可能有些位置超出棋盘范围，
1
f那些不允许的位置就不能成为下一步的选择。这八个邻接位置可以用两个一维数组HTry18和HTry28来表示：HTry182，1，1，2，2，1，1，2HTry281，2，2，1，1，2，2，1位于i，j的马可以走到的新位置是在棋盘范围内的iHTry1h，jHTry2h，其中h0，1，，7。每次在所有可走的位置中选择一个进行试探，已经走过的位置标记为步数（比如第5步走到该格，则该格标记为5），未走过的位置标记为0。为了使马能最大可能性的走完整个棋盘并且减小计算次数，应该让马优先走难走的地方，即邻接位置最少的那些位置（主要指四角和边缘）。在棋盘上标记出每个位置的邻接位置，如下图：2344443232回溯的方法如果仅仅是搜索邻接位置最小的位置作为走棋的下一步，仍然有很大几率不能把棋盘走遍，因此当棋子走到的位置其八个邻接位置全部之前已经走过，就要设计回溯算法，使得棋子能够退回上一步转而寻求另一个方向。为了满足这种需求，需要定义一个栈结构，每当成功走一步，就把所走位置的坐标和这次移动的步数入栈，当走到某一位置无法进行下一步时，就要把原来栈顶的元素Pop出来，转而换一条路径继续探索，如果还是无法找到正确路径，r