数据结构课程设计_马踏棋盘

杭州师范大学 钱江学院

课 程 设 计

题 目

教 学 院 专 业 班 级 姓 名 指导教师

马踏棋盘算法研究 信息与机电工程分院 计算机科学与技术 计算机1201 吴秋浩 王李冬

2013 年 12 月 21 日

目 录

一．概述 .................................................................................................... 3 二．总体方案设计 .................................................................................... 3 三．详细设计 ............................................................................................ 4 四．最终输出 ............................................................................................ 6 五．课程设计总结 .................................................................................. 10 参考文献 .................................................................................................. 13

一 概述

1. 课程设计的目的

（1） 课题描述

设计一个国际象棋的马踏遍棋盘的演示程序。

（2） 课题意义

通过“马踏棋盘”算法的研究，强化了个人对“栈”数据结构的定义和运用，同时也锻炼了自身的C语言编程能力。另一方面，通过对“马踏棋盘”算法的研究，个人对“迷宫”、“棋盘遍历”一类的问题，有了深刻的认识，为今后解决以此问题为基础的相关的问题，打下了坚实的基础。 （3） 解决问题的关键点说明

解决问题的关键首先要熟练掌握C语言编程技术，同时能够熟练运用“栈”数据结构。另外，态度也是非常重要的。在课程设计过程中，难免会遇到困难，但是不能轻易放弃，要肯花时间，能静得下心，积极查阅相关资料，积极与指导老师沟通。

2. 课程设计的要求

（1） 课题设计要求

将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，„，64依次填入一个8×8的方阵，输出之。

程序由回溯法和贪心法实现，比较两种算法的时间复杂度。

（2） 课题设计的思路

首先，搞清楚马每次在棋盘上有8个方向可走，定义两个一位数组，来存储马下一着点的水平和纵向偏移量。程序再定义一个8*8二维数组，初始所有元素置0，起始点元素置1。若为回溯法，初始方向数据（一维数组下标）入栈。随后，马从起始点开始，每次首先寻找下一可行的着点，然后记下方向，方向数据入栈，把该位置元素置为合适的序列号，若无下一可行着点，则回溯，寻找下一方向位置着点，以此类推，直到64填入数组中，则输出二维数组，即为马可走的方案。若为贪婪法，选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置。直到没有下一着点位置，若此时已标记到64，则找到可行方案，输出之。反之，改变初始寻找方向继续寻找，直到8种方向顺序都试过，若还是没有合适的方案，则说明以该起始 点开始马无法踏遍棋盘。

二 总体方案设计

1. 回溯法

算法思想

按深度优先策略，从一条路往前走，能进则进，不能进则退回来，换一条路再试，也就是说每当前进的路不通，我们总是返回到前一次的岔路口，选择下一条新的路线 。

（1）函数头文件定义和宏定义

#include #include #define N 8 （2）栈数据结构定义

typedef struct{

int b[N*N]; int top; }SqStack;

（3）定义探寻路径函数

Board[N][N]模拟N*N棋盘，填入1,2,3···64。 x、y传递初始位置。

bool HorsePath(int Board[][N],int x,int y){ // 初始化栈 //定义方向数组

//int xx[8]={1,2,2,1,-1,-2,-2,-1}; //int yy[8]={2,1,-1,-2,-2,-1,1,2}; //初始方向下表入栈

//回溯法开始寻找合适方案（详见“详细设计”） }

（4）定义主函数

void main(){

//定义基本变量及Board[N][N]数组 //输入初始位置x0，y0

//调用HorsePath（Board,x0,y0）; //输出方案 }

//记录每次走的方向 //栈指针

//便于改变棋盘大小

2. 贪心法

算法思想

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题：

1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

（1）函数头文件定义和宏定义

#include #define N 8

//便于改变棋盘大小

（2）程序要用到的一些全局变量的定义

int xx[8]={1,2,2,1,-1,-2,-2,-1};

int yy[8]={2,1,-1,-2,-2,-1,1,2}; //控制马能走的8个方向 int Board[N][N]={0}; (3)定义FeassiblePath

//初始棋盘所有位置可走 //计算每个点的后续着点个数

int FeassiblePath(int x,int y,int start){ //函数体(详见“详细设计”) }

(4)定义NextPath

/*找出一个着点的后续着点中可走方位最少的，把着点到后续 点的方向记下返回主函数*/

int NextPath(int x,int y,int start){ //函数体(详见“详细设计”) } (5)定义主函数

void main(){

//输入初始位置x0，y0

//定义变量整型变量start控制起始8种方向 While(start

//循环调用NextPath（x0,y0,start） //找到方案，则输出之 start++; } }

三 详细设计

1.回溯法“马踏棋盘”演示程序

#include #include #define N 8

typedef struct{

int b[N*N]; //记录每次走的方向 int top; }SqStack;

bool HorsePath(int Board[][N],int x,int y) {

SqStack *s;

s=(SqStack*)malloc(sizeof(SqStack)); //初始化栈 s->top=-1;

int xx[8]={1,2,2,1,-1,-2,-2,-1};

int yy[8]={2,1,-1,-2,-2,-1,1,2}; //控制马能走的8个方向 int p=0; s->top++;

s->b[s->top]=p; while(s->top>-1){

Board[x][y]=s->top+1; //找到方案，则输出之 if(Board[x][y]==N*N) return true;

while(p=0&&(x+xx[p])=0&&(y+yy[p])top++;

s->b[s->top]=p; p=0; break; } p++; }

if(p==8){

Board[x][y]=0;

x-=xx[s->b[s->top]]; y-=yy[s->b[s->top]];

p=s->b[s->top]+1; s->top--; } }

return false; //循环结束，未找到合适方案 }

void main(){ bool flag; int x0,y0,i,j;

int Board[N][N]={0}; //设置开始每一格都可走 printf("请输入马的起始位置x,y\n注：(0==N||y0=N)

printf("位置输入有误，请重新输入："); else

break; }

flag=HorsePath(Board,x0,y0); if(flag==false) {

printf("无法遍历！\n"); } else{

printf("一种可行的方案为：\n"); for(i=0;i

printf("\t%d",Board[i][j]); printf("\n\n"); }z } }

2.贪心法“马踏棋盘”演示程序

#include #define N 8

int xx[8]={1,2,2,1,-1,-2,-2,-1}; int yy[8]={2,1,-1,-2,-2,-1,1,2}; int Board[N][N]={0};

//控制马能走的8个方向 //初始棋盘所有位置可走

//计算每个点的后续着点个数

int FeassiblePath(int x,int y,int start){ int count=0,i=0,p,k; k=start; while(i

//若下一着点可走且没有超出边界

if(Board[x+xx[k%8]][y+yy[k%8]]==0&&(x+xx[k%8]>=0&&x+xx[k%8]

&&(y+yy[k%8]>=0&&y+yy[k%8]

return count; }

//找出一个着点的后续着点中可走方位最少的，把着点到后续着点的方向记下返回主函数

int NextPath(int x,int y,int start){ int min=9,i=0,num,p,k,f; k=start; while(i

//若下一着点可走且没有超出边界

if(Board[x+xx[k%8]][y+yy[k%8]]==0&&(x+xx[k%8]>=0&&x+xx[k%8]

&&(y+yy[k%8]>=0&&y+yy[k%8]

num=FeassiblePath(x+xx[k%8],y+yy[k%8],start); if(min>num){ min=num; f=k%8; } } k++; i++; }

if(min==9) return -1;

return f; //后续着点的方向记下返回主函数 }

void main(){

int i,j,x0,y0,start=0,flag,sign=0;

printf("请输入马的起始位置x,y\n注：(0==N||y0=N)

printf("位置输入有误，请重新输入："); else

break; }

Board[x0][y0]=1;

while(start

for(int step=2;step

Board[i][j]=step; } else

break;

} //若找到一种方案，则输出之 if(step==N*N+1){ sign=1;

printf("一种可行的方案为：\n"); for(i=0;i

printf("%d\t",Board[i][j]); printf("\n\n"); } }

if(sign==1) break; start++; }

if(sign==0){

printf("此起始点下无法遍历，或许方案根本不存在！\n试改变起始点寻找方案！\n"); } }

四 最终输出

1.回溯法

（1）程序正确输入下运行结果

（2）回溯法求解的时间复杂度分析 设问题的规模为n，即棋盘的的大小为n*n。则棋盘初始化的时间复杂度为O（n^2）, 程序运行过程中，还有一个while（s->top>-1）循环，同时这个循环内部还有一个while（p

2.贪心法

（1）程序正确输入下运行结果

（2）贪心法求解的时间复杂度分析

设问题的规模为n，即棋盘的的大小为n*n。由贪婪算法可知选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置。显然，影响程序运行时间的基本运算是在寻找出口最少的位置。由程序我们可知T(n)= O(n^2)。

显然贪心算法的时间复杂度小多了，即使棋盘的大小是8*8，想要搜索任意起始点下的可行方案，一秒钟内就可以输出结果。

（3）回溯法和贪心法的比较

回溯法求解马踏棋盘，思想简单易懂，能够一次性得到所有可能的情况，但是算法时间复杂度过大，在棋盘大小过大时，不推荐采用。贪心法，思想也是比较容易让人理解的，同时，算法的时间复杂度为O(n^2),能够较快地找出一种复合要就的方案，但是利用贪心法不便于得到所有的可行方案。

五 课程设计总结

此次数据结构课程设计的课题是设计一个国际象棋的马踏遍棋盘的演示程序。在刚开始选课题时，我就被“马踏棋盘”这几个字深深地吸引了，虽然那是我第一次听说这个名词，但我还是选择了“马踏棋盘”。于是我便开始在网上搜集关于“马踏棋盘”的内容，然后我知道了“马踏棋盘”算法的要求。由于在数据结构课上学习过利用栈来求解迷宫问题，所以第一时间我就想到了利用栈来求解这个问题，也就是利用回溯法求解。虽然很快我写出了，回溯法求解的源程序，可是当我运行程序时，出现的现象使我很惊讶，对于一个8*8的棋盘，输入不同的起始点，得到结果的时间不同，例如输入（0,0）较快的得到了结果，但是输入（1,1）我等了几十分钟，依旧没有等到实验结果的出现。这时，我开始思考，一定有更优化的算法存在，为了较快得到实验结果，我又开始在网上搜索，然后我得知了利用贪心法能够大大提高程序运行的效率，因为该算法选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置。直到没有下一着点位置。于是，我又用贪心法实现了“马踏棋盘”演示程序。在此次课程设计中我一直想尝试一次输出所有的“马踏棋盘”方案，并记录方案的个数。虽然用回溯法实现了对5*5等小规模棋盘，马踏遍棋盘所有方案的输出，但是对于8*8的棋盘，问题规模过大，无法在短时间内得到所有的方案。我也曾想过用贪心法实现“马踏棋盘”所有方案的一次性输出，但是我觉得如果要用贪心法得到“马踏棋盘”所有方案，需要循环对每一着点的后继可行着点进行尝试遍历。这样就违背了贪心法“选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置”这一标准，这样做就会失去贪心法本身的优点，反而使程序时间复杂度加大，得不偿失。我将在今后的学习中继续探索，争取能够研究出一次性得到“马踏棋盘”所有方案，更快，更优化的算法。

虽然，这次课程设计持续的时间不长，但是通过这次课程设计，很好的锻炼了自己解决问题的能力，相信在今后的学习研究中，遇到更大的困难，只要像这次课程设计一样，井然有序地规划好自己的任务，遇到难题不退缩，冷静思考，积极查阅相关资料，一定能够解决难题。

参考文献

[1] 谭浩强，C程序设计（第四版），北京，清华大学出版社，2010年6月。

[2] 李春葆，数据结构教程（第4版），北京，清华大学出版社，2013年1月。