二○○七～二○○八 学年第 二 学期
课程设计报告书
课程名称： 马踏棋盘
班 级：
学 号：
姓 名：
1
指导教师：
2008 年 7 月 2 日 星期三
马踏棋盘
一．需求分析
1．问题描述
设计一个国际象棋的马踏遍棋盘的演示程序。
2．基本要求
将马随机放在国际象棋的 8X8 棋盘 Board[8][8]的某个方格中，马
按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部 64
个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线 ，
将数字 1，2,。。。， 64 依次填入一个 8X8 的方阵，输出之。
3．测试数据
由读者指定。可自行指定一个马的初始位置。1<=i<=8, 1<=j<=8.即输入行
数和列数。
4．选作内容
（1）求出从某一起点出发的多条以至全部行走路线。
（2）探讨每次选择位置的“最佳策略”，以减少回溯的次数。（本程序完成）
（3）演示寻找行走路线的回溯过程。（本程序完成）
二．概要设计
1．总体思路以及改进算法
a.前期想法以及遇到困难：
一开始，我是按照题目要求，用最基本的算法，就是每次走一步
都将其信息放进栈中，以便回溯的时候调用其它出口。而每次走的下
一步都是没有经过一定的挑选，而是固定着 8 个位置中的某个位置开
始绕。以至造成回溯次数超多，当马初始位置为某个位置时甚至无法
运行，于是宣告了这个算法的失败。
b．后期算法改进：
在前面的基础上，我认识到了，这个算法改进的关键就在于对出
口的 挑选，才能更多的减少回溯次数，于是有了这个完美的‘贪婪法’。
2
即每次都走下一个位置中出口数最少的那个位置，实现过程基本不用
回溯。时间复杂度大大降低，由于是一个for循环，时间复杂度跟棋盘数组大小
成正比。程序运行所需要的空间也大大减少。
2．本程序中用到的函数
void initarray()
操作结果：初始化棋盘,将棋盘内的空格置为 0
int nextgo(int i,int j)
操作结果：计算出某个位置的出口数
int nextplace(int i,int j)
操作结果：找出当前位置的所有下一个位置中出口数最少的位置
void print()
操作结果： 输出棋盘
3．主函数流程以及各模块间的关系
3
评论0
最新资源