数据结构
课程设计报告
设计题目： 马踏棋盘
院 系 计算机学院
年 级 11 级
学 生 xxxxxxx
学 号指导教师 xxxxxxxxx
起止时间 9-6/9-13
2013年9月10日星期二
目 录
一、 课程设计目的 ------------------------------------------------------3
二、 需求分析-------------------------------------------------------------3
三、程序源代码------------------------------------------------------------ 4
四、调试分析----------------------------------------------------------------7
五、问题总结----------------------------------------------------------------8
六、参考资料-----------------------------------------------------------------9
一、 课程设计目的
(1) 熟练使用 C 语言编写程序，解决实际问题;
(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;
(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
二、 需求分析
问题描述:将马随机放在国际象棋的 8X8 棋盘中的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部 64 个方格。编制递归程序，求出马的行走路线 ，并按求出的行走路线，将数字 1，2，…，64 依次填入 8X8 的方阵输出之。测试数据:由读者指定可自行指定一个马的初始位置。实现提示:每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”悔棋使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。
背景介绍：
国际象棋为许多令人着迷的娱乐提供了固定的框架，而这些框架常独立于游戏本身。其中的许多框架都基于骑士奇异的L型移动规则。一个经典的例子是骑士漫游问题。从十八世纪初开始，这个问题就引起了数学家和解密爱好者的注意。简单地说，这个问题要求从棋盘上任一个方格开始按规则移动骑士，使之成功的游历国际象棋棋盘的64个方格，且每个方格都接触且仅接触一次。
可以用一种简便的方法表示问题的一个解，即将数字1，……，64按骑士到达的顺序依次放入棋盘的方格中。
一种非常巧妙的解决骑士漫游地方法由J.C.Warnsdorff于1823年给出。他给出的规则是：骑士总是移向那些具有最少出口数且尚未到达的方格之一。其中出口数是指通向尚未到达方格的出口数量。在进一步的阅读之前，你可以尝试利用Warnsdorff规则手工构造出该问题的一个解。
实习任务：
编写一个程序来获得马踏棋盘即骑士漫游问题的一个解。
您的程序需要达到下面的要求：
棋盘的规模是8*8；
对于任意给定的初始化位置进行试验，得到漫游问题的解；
对每次实验，按照棋盘矩阵的方式，打印每个格被行径的顺序编号。 技术提示：
解决这类问题的关键是考虑数据在计算机中的存储表示。可能最自然的表示方法就是把棋盘存储在一个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)的位置离某一条边较近，有些可
能的移动就会把骑士移到棋盘之外，而这当然是不允许的。骑士的八种可能的移动可以用一个数组MoveOffset方便地表示出来：
MoveOffset[0]=(-2,1)
MoveOffset[1]=(-1,2)
MoveOffset[2]=(1,2)
MoveOffset[3]=(2,1)
MoveOffset[4]=(2,-1)
MoveOffset[5]=(1,-2)
MoveOffset[6]=(-1,-2)
MoveOffset[7]=(-2,-1)
于是，位于(x,y)的骑士可以移动到(x+MoveOffset[k].x, y+MoveOffset[k].y)，其中k是0到7之间的某个整数值，并且新方格必须仍位于棋盘上。
扩展需求：可以考虑将结果图形化。(b)考察所有初始化的情况，测试是否都能够得到解。
三、程序源代码
#include
#include
#define MAXSIZE 100
#define N 8
int board[8][8]; //定义棋盘
int Htry1[8]={1,-1,-2,2,2,1,-1,-2};
/*存储马各个出口位置相对当前位置行下标的增量数组*/
int Htry2[8]={2,-2,1,1,-1,-2,2,-1};
/*存储马各个出口位置相对当前位置列下标的增量数组*/ struct Stack{ //定义栈类型
int i; //行坐标
int j; //列坐标
int director; //存储方向
}stack[MAXSIZE]; //定义一个栈数组
int top=-1; //栈指针
void InitLocation(int xi,int yi); //马在棋盘上的起始位置坐标
int TryPath(int i,int j); //在每个方向进行尝试，直到试完整个棋盘 void Display(); //输出行走的路径
void InitLocation(int xi,int yi)
{
int x,y; //定义棋盘的横纵坐标变量
top++; //栈指针指向第一个栈首
stack[top].i=xi; //将起始位置的横坐标进栈
stack[top].j=yi; //将起始位置的纵坐标进栈
stack[top].director=-1; //将起始位置的尝试方向赋初值
board[xi][yi]=top+1; //标记棋盘
x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标
y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标
if(TryPath(x,y)) //调用马探寻函数，如果马探寻整个棋盘返回1否则返回0 Display(); //输出马的行走路径
else
printf("无解");
}
int TryPath(int i,int j)
{
int find,director,number,min; //临时变量
int i1,j1,h,k,s; //临时变量
int a[8],b1[8],b2[8],d[8]; //临时数组
while(top>-1) //栈不空时循环
{
for(h=0;h
{
number=0;
i=stack[top].i+Htry1[h];
j=stack[top].j+Htry2[h];
b1[h]=i;
b2[h]=j;
if(board[i][j]==0&&i>=0&&i=0&&j
for(k=0;k
{
i1=b1[h]+Htry1[k];
j1=b2[h]+Htry2[k];
if(board[i1][j1]==0&&i1>=0&&i1=0&&j1
//如果找到下一位置
number++; //记录条数
}
a[h]=number; //将条数存入数组a[8]中 }
}
for(h=0;h
min=9;
for(k=0;k
if(min>a[k])
{
min=a[k];
d[h]=k; //将下表存入数组d[8]中
s=k;
}
a[s]=9;
}
director=stack[top].director;
if(top>=63) //若走完整个棋盘返回1
return (1);
find=0; //没有找到下一个位置
for(h=director+1;h
{
i=stack[top].i+Htry1[d[h]];
j=stack[top].j+Htry2[d[h]];
if(board[i][j]==0&&i>=0&&i=0&&j
find=1; //表示找到下一个位置
break;
}
}
if(find==1) //如果找到下一个位置进栈
{
stack[top].director=director; //存储栈结点的方向
top++; //栈指针前移进栈
stack[top].i=i;
stack[top].j=j;
stack[top].director=-1; //重新初始化下一栈结点的尝试方向 board[i][j]=top+1; //标记棋盘
}
else //否则退栈
{
board[stack[top].i][stack[top].j]=0; //清除棋盘的标记 top--; //栈指针前移退栈
}
}
return (0);
}
void Display()
{
system("color 1e");
int i,j;
for(i=0;i
{
for(j=0;j
printf("\t%d ",board[i][j]); //输出马儿在棋盘上走过的路径 printf("\n\n");
}
printf("\n");
}
void main()
{
system("cls");
system("color 0d");
printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃㊣ 选做题，骑士漫游 ㊣┃\n"); printf("┃ 姓名：xxxx ┃\n"); printf("┃ 学号：xxxxxxxxx ┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); printf(" >>>\n");
printf("╔═════════════╗\n");
printf("║欢迎进入骑士漫游小游戏!!! ║\n");
printf("╚═════════════╝\n");
int i,j;
int x,y;
for(i=0;i
for(j=0;j
board[i][j]=0;
for(;;)
{
printf(">>>...请输入初始位置坐标(x,y) 注:(1,1)-(8,8)\n"); printf("Input x = ");
scanf("%d",&x); //输入起始位置的横坐标
printf("Input y = ");
scanf("%d",&y); //输入起始位置的纵坐标
if(x>=1&&x=1&&y
printf("\n输入有误,请重新输入!\n\n");
}
printf("骑士从第%d行，第%d列开始漫游:\n",x,y);
InitLocation(x-1,y-1); //调用起始坐标函数
}
四、调试分析
1. 开始界面
2.输入坐标
五、问题总结
此次数据结构课程设计我组设计的是一个利用栈递归得到的马踏遍棋盘的演示程序，刚看题目时候觉得还比较困难，根本没一点思绪，但通过在网上查找相关资料，对这个问题才有了一定的思绪。在组员的分工合作中，我们终于把程序写出来了。在这个过程中，我收获颇多，不仅理论知识掌握的
更牢，实际动手能力也有所提高，再次让我感受到语言强大的功能，更激发了我语言的兴趣。如果说以前的编程仅仅是按照课本的要求进行的，那这个课程设计难度就提高了一个级别，它让我们将所知道的知识联系到了一起，更加显示了程序的强大。
六、参考资料
1.
2.
3.
《数据结构（C语言版）》 严蔚敏 吴伟民 编著，清华大学出版社 《数据结构（C语言版）》相配套的课本源代码 《C++程序设计》谭浩强 编著 清华大学出版社