马踏棋盘数据结构实践报告
重阳节的图片-郑州绿博园
_
马踏棋盘问题
摘要：
马踏棋
盘就是在国际象棋8X8棋盘上面，按照国际象
棋规则中马的行进规则，实现从任意初始位置，每个方格
只进入一次，走遍棋盘上全部64个方格。理解栈的 “后
进先出”的特性以及学会使用回溯。
关键字：马踏棋盘、递归、栈、回溯
1．引言
马踏棋盘就是在国际象棋8X8棋盘
上面，按照国际象
棋规则中马的行进规则，实现从任意初始位置，每个方格
只进入一次，走遍棋
盘上全部64个方格。
编制程序，求出马的行走路线，并按求出的行走路线，
将数字1，2…
.64依次填入一个8X8的方阵，并输出它的
行走路线。输入：任意一个起始位置；输出：无重复踏<
br>遍棋盘的结果，以数字1-64表示行走路线。
2．需求分析
（1）需要输出一个8X8的棋盘，可以采用二维数
组的方法实现。
（2）输入马的
起始位置，必须保证输入的数字在
规定范围内，即0<=X<=7,0<=Y<=7。
（3）保证马能走遍整个棋盘，并且不重复。
_
（4）在棋盘上输出马的行走路线,标记好数字1、2、
3直到64。
3．数据结构设计
采用栈数组为存储结构。
#define maxsize
100
struct
{
int i;
int j;
int director;
}stack[maxsize];
4．算法设计
4.1 马的起始坐标
void location(int x,int y)
始化
{
top++;
stack[top].i=x;
栈
stack[top].j=y;
栈
stack[top].director=-1;
马的位置坐标的初
起始位置的横坐标进
起始位置的竖坐标进
_
a[x][y]=top+1;
标记棋盘
Try(x,y); 探寻的马的行走路
线
}
4.2 路径探寻函数
void Try(int i,int j)
{ int count,find,min,director;
int
i1,j1,h,k,s;
int
b[8]={-2,-2,-1,1,2,2,1,
-1},c[8]={1,-1,-2,-2,-1,1,2,2}
;
存储马各个出口相对当前位置行、列坐标的增量数
组
int
b2[8],b1[8];
for(h=0;h<=7;h++)
用数组b1[8]记录当前位置的下一个位置的可行路
径的条数
{
count=0;
i=stack[top].i+c[h];
j=stack[top].j+b[h];
if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0)
如果找到下一个位置
{
for(k=0;k<=7;k++)
{
i1=i+c[k];
j1=j+b[k];
if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&a[i1]
_
[j1]==0) 如果找到下一个位置
count++;
记录条数
}
b1[h]=count;
将条数存入b1[8]
中
}
}
for(h=0;h<=7;h++)
根据可行路径条数的大小，从小到大排序，并放入
数组b2[8]中
{min=9;
for(k=0;k<=7;k++)
if(min>b1[k])
{
min=b1[k];
b2[h]=k;
s=k;
}
b1[s]=9;
}
find=0;
director=stack[top].director;
for(h=director+1;h<=7;h++)向8个方向进
行寻找
{
i=stack[top].i+c[b2[h]];
j=stack[top].j+b[b2[h]];
if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]=
=0)
{stack[top].director=h; 存储栈的寻找
方向
_
top++; 进栈
stack[top].i=i;
stack[top].j=j;
stack[top].director=-1;重新初始化下一栈的
方向
a[i][j]=top+1;
find=1;
找到下一位置
break;
}
}
if(find!=1)
{a[stack[top].i][stack[top].j]=0; 清除棋盘的
标记
top--; 退栈
}
if(top<63)
Try(i,j); 递归
}
4.3输出函数
void display()
{
int i,j;
for(i=0;i<=7;i++)
{
for(j=0;j<=7;j++)
printf(
输出马的行走
路线
printf(
_
}
printf(
}
5.程序实现
5.1 主函数
void
main()
{
int i,j,x,y;
for(i=0;i<=7;i++) 棋盘的初始化
for(j=0;j<=7;j++)
a[i][j]=0;
printf(输入X
Y (0=
if(x>=0&&x<=7&&y>=0&&y<=7)
判断输入的起始位子是否正确
{
location(x,y);
display();
}
else printf(错误n
}
_
5.2运行结果
（1）当输入不符合要求时
（2）正确输入时
_
5.3 算法分析
（1）马的起始坐标
一开始先建立一个栈数组，里面包括横坐标和
竖坐标还有方向。输入马的起始位置，进入坐标起
始
化函数，让输入的横坐标和竖坐标进栈，并初始化方
向，并且标记棋盘，指示此位置已走过，
此时的位置
是栈的第一个元素，进入路径探寻函数。
（2）路径探寻函数
路径探寻函数中有两个分别存储马各个出口相
对当前
位置行、列坐标的增量数组。要使马走遍所有
的棋盘，必须要有一定的行走规律。我使用的是记录
当前位置的下一个位置的可行路径的条数，并对它们
进行排序，按从小到大的顺序存储在一个一维数组
中。
_
开始进行探寻，分别向8个方向探寻，如果找到一个
方向可
行，则存储栈的寻找方向，再进栈，重新初始
化栈的寻找方向，并用二维数组标记此位置，再使用
递归进入下一次新的探寻。如果在某一次探寻中，没
能找到方向，则清除该位置的标记，并退栈，再次
递
归，回到上次的寻找方向（之前已经存储过栈的寻找
方向），跳过已经寻找过的方向，再进行
探寻，直到全
部棋盘都被走遍。
（3）输出函数
当马走遍所有的棋盘时
，输出马的行走路线，
因为之前已经把马的行走路线记录在二维数组中了，
所以此时只需把二维
数组中的标记输出即可。
6.设计体会
本次课程设计让我学会了很多东西，使
得我对于栈
的理解更深入了，使用更加熟练。是此之前，我对于
回溯并不是特别了解，但是这次
设计让我学会了回溯
的基本概念以及基础的用法。当一件事情有很多种方
法进行时，我们要将所
有的方法集合起来形成一个集
合，再用一定的规律去调用这个集合内的方法。
刚开始的时候
，我并不能让马走遍所有的棋盘，但
当我知道了回溯的思想之后，我修正了我的算法，最
终使马
走遍所有的棋盘。
我还考虑了递归与非递归的问题，在试验了两种方
法之后，发现两种都可
以，在时间的复杂度上也没有
太大的差别（显示棋盘的时间上），但我还是使用的是
递归的方法
来完成本次设计。
_
参考文献：
[1]
严蔚敏、吴伟民编著．数据结构（C语言版）．北
京：清华大学出版社，２００７
[2]
谭浩强主编．C程序设计（第三版）．北京：清华
大学出版，2005
[3]
张蕊、吕涛主编．C程序设计教程.
出版，2012
华中科技大学