马踏棋盘程序设计 完美
1．问题描述设计一个国际象棋的马踏棋盘的演示程序
2．需求分析
(1)将马随即放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。
(2)编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,……,64依次填入一个8×8的方阵，输出之。
(3)程序执行命令为：
1)输入起始方格坐标(X,Y)
2)求解第一组路径并显示,按Q键退出系统，按其他任意键求解并显示下一组路径。
(4)测试数据:(0,0),(1,2)
3概要设计
3.1[程序设计思路].
按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否。如新路点可用，则入栈，并执行下一步，每次按照上一路点的位置生成新路点。如一个路点的可扩展路点数为0，则走不下去了，进行回溯。
3.2[存储结构设计]
8个可能位置可以用两个一维数组表示：
数组1： 0 1 2 3 4 5 6 7
-2 -1 1 1
2
2
1
-1 -2
数组2： 0 1 2 3 4 5 6 7
1 2 2 1 -1 -2 -2 -1
位于（i,j）的马可以走到的新位置是在棋盘范围内的（I+数组1[h],j+数组2[h]）,其中h=0，1，…7。
每次在多个可走位置中选择其中一个进行试探，其中未曾试探过的可走位置用适当栈结构妥善管理，也备试探失败时的“回溯”（悔棋）使用，即用栈结构存储试探的路径来进行路径试探操作。
3.3[主要算法设计]
3.3.1栈类的定义和接口:
template <class Type>
class MyStack
{private:Type *bottom; // 元素存放的动态数组
int size,ptr; // 堆栈大小和当前栈顶元素索引
inline int extent(){…}; //当栈满时,自动扩充
public:
//构造函数
MyStack() {bottom=new Type[BASESIZE];ptr=-1;size=BASESIZE;};//用默认大小初始化
MyStack(int i) {bottom=new Type[i];ptr=-1;size=i;}; //用指定大小初始化
//析构函数
~MyStack(){if(bottom!=NULL) delete []bottom;};
//清栈
inline void clear(){…};
//判栈空
inline bool IsEmpty(){…};
//入栈
int push(Type e);
//出栈
int pop(Type &e);
//获得栈顶元素
int top(Type &e);
//直接修改栈定元素
int settop(Type e);
// 用callback函数对栈从栈底向上遍历
void traverse(void callback(Type *),Type *);
};
3.3.2本程序的结构
1)主程序模块:
void main()
{
初始化；
向屏幕输出输入提示；
接受输入起始坐标(X,Y)；
输出第一组解的路径和回溯情况；
while(1)
{
接受命令；
处理命令
{
if(命令==退出)
退出；
其他命令
{
输出下一组解的路径及回溯情况；
}
}
}
异常处理{}；
正常退出；
}
2)路径求解模块---求解所有可行的路径
3)可行路径求解的核心算法:
bool Result(int start_x, int start_y, int board[][8])
{初始化路径栈 sPath;
初始化方向栈 sDir;
初始化当前步数序号和当前方向 step = 1, d = 0
将点(start_x,start_y)入路径栈,将该点方向d入方向栈；
while(1)
{将当前的路径栈中点出栈并保存，将该点方向出栈并保存；//为上一次的目标点和目标方向
if(方向=>8)
{ 抹去该点痕迹；步数序号-1；
调用MyStack的traverse函数演示退栈情况；
退栈；
方向栈中的方向++；
continue;
}
if(方向<8)//方向未走完
{if(目标点在棋盘内且未被走过)
{ 记录序号，目标点入栈，目标点方向初始为0入栈；
continue;
}
else(目标点已被走过或目标点不在棋盘内)
{方向++；
continue;//继续
}
}
//enf if(d<8)
if (步数序号已满)
{向屏幕输出路径
if（查看下一路径）
{回退一步；方向++；
continue;
}
}
} //end while(1)
}
3.4[测试用例设计]
依次输入（0，0）（1，2）
4详细设计
4.1堆栈类MyStack
参见文件 base 中MyStack模板类的定义和实现。
4.2求解出所有路径
为了快速求解出所有路径，使用了优化策略，即计算各个点的可以行走的下一个点的个数作为点的权值存放在权值矩阵weight[8][8]中；然后根据这个矩阵对各点的8方向各方向按权设置优先级，保存于各点方向矩阵序列map[8][8][8]，权值小的优先行走。
详见horse.cpp文件中的 setweight,setmap函数。
4.3求解路径核心算法函数
bool Result(int myx, int myy, int board[][8])
{ MyStack<MyPoint> sPath; // 栈,记录路径点
MyStack<int> sDir; // 栈,记录方向选择
MyPoint p,dest_p; // 当前点和目标点
int step = 1, d = 0; // 当前序号,方向
p.x = myx; p.y = myy;
sPath.push(p); sDir.push(d);//起始点的坐标和首选方向入栈,
//map[x][y][0]未必是(x,y)点的offset[0]方向,而是到该点可到的权值最小的点的方向即offset[map[x][y][0]]
board[p.x][p.y] = 1;//起始点标记已走且序号为1
MyPoint pTemp;int iTemp;
while(1)
{if (step==N*N) //路径完成
{ void(*pFun)(MyPoint *) ;
pFun=&TraverseOut;MyPoint *e=NULL;
cout<<"\n起始点为 ("<<myx<<","<<myy<<")的解空间\n";
cout<<"依次走以下坐标(按行顺序)[第 "<<num<<" 组] \n";
sPath.traverse(TraverseOut,e);
output();//输出路径矩阵
if(ch=='q')
break;
else//回退前一步
{ sPath.pop(p);sDir.pop(d);//退栈;
sDir.top(d);sDir.settop(d+1);step--;
continue;
}
}
if(sPath.top(p)==-1||sDir.top(d)==-1) break;
int x=p.x;
int y=p.y;
if(d>=8)//该点所有方向已走完，退栈
{ board[x][y]=0;//初始化;
step--;
sPath.pop(pTemp);sDir.pop(iTemp);//退栈
sDir.top(iTemp);
sDir.settop(iTemp+1);//更改方向
continue;
}//end if (d>=8)
if(d<8)//方向未走完
{int off=map[x][y][d];
dest_p.x=x+offset[off].x;dest_p.y=y+offset[off].y;
if(check(dest_p.x,dest_p.y)&&board[dest_p.x][dest_p.y]==0)//目标点在棋盘内且未被走过,则将目标点入栈同时标记为已走过
{ board[x][y]=step;//记录序号
step++;
sPath.push(dest_p);//存入目标点
sDir.push(0); //存入方向栈初始0;
continue;
}
else//i目标点已被走过或目标点不在棋盘内,换方向
{ d++;//取下一个方向
sDir.settop(d);//换方向
continue;//继续
}
} //enf if(d<8)
} //end while(1)
}
4.4main和其他UI函数核心代码
/*horse.cpp 马踏棋盘算法实现文件文件 base 是自定义的数据结构类的定义和实现文件*/
#include <iostream>
#include "base"
using namespace std;
/*全局宏，常量，变量，函数声明*/
#define N 8 //棋盘大小
int map[N][N][8]; //按各点权值递升存放待走方向,每点8个
int weight[N][N]; //各点的权值
int board[N][N]; //表示棋盘的数组
static MyPoint offset[8] = // 8个候选方向的偏移
{ -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1 };
char ch;int num=1;
void setweight();//求各点权值
void setmap(); //各点的8个方向按权值递增排列
bool Result(int x, int y, int board[][8]); //主算法函数
/*主函数*/
void main()
{ for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
board[i][j]=0;
setweight();
setmap();
char x,y;
while(1)
{ cout<<"请输入起始点坐标 X (可取0~7):";
cin>>x;
cout<<"请输入起始点坐标 Y (可取0~7):";
cin>>y;
if(x<'0'||x>'7'||y<'0'||y>'7')
cout<<"起始坐标错误,重新输入！\n\n";
else
break;
}
bool re=Result(x-'0',y-'0',board);
cout<<endl<<endl;
if(re=false)
cout<<"Bye!\n\n";
else
cout<<"Good Bye!\n\n";
}
//end main()
/*求各点权值:可走的方向数.该值越小,则被上一点选中的可能性越大*/
void setweight()
{for(int i=0;i<N;i++)//for 1
{ for(int j=0;j<N;j++)//for 2
{ weight[i][j]=0;
for(int k=0;k<N;k++)// for 2
{ int x,y;
x=i+offset[k].x;
y=j+offset[k].y;
if(x>=0&&x<N&&y>=0&&y<N)
{weight[i][j]++;//即在8个方向中，（i，j）点有几个方向可以移动
}
}
}
}
//end of for 1
}
//end setweight()
/*检查(i,j)是否在棋盘内*/
int check(int i,int j)
{ if(i<0||i>=8||j<0||j>=8)
return 0;
return 1;
}
/*标准输出*/
void output()
{ cout<<"求解结果矩阵 [第 "<<num<<" 组] \n";
num++;
for(int i=0;i<8;i++)
{ for(int j=0;j<8;j++)
if(board[i][j]==0)
cout<<64<<"\t";
else cout<<board[i][j]<<"\t";
cout<<endl;
}
cout<<"\n";
cout<<"输入q to quit,其他字符查看其他路径:";
cin>>ch;
}
/*将各点的8个方向按该方向下的目标点的权值递增排列，不可到达的目标点(超出棋盘)的方向放在最后面*/
void setmap()
{ for(int i=0;i<N;i++)//for 1
{ for(int j=0;j<N;j++)//for 2
{ for(int k=0;k<8;k++)
map[i][j][k]=k;//设置默认方向索引
for(int k=0;k<8;k++)//for 3 与 for 4 两个循环 对方向索引按 点的权值升序排列，不能到达的方向排在最后
{ for(int m=k+1;m<8;m++) //for 4
{ int d1=map[i][j][k];
int x1=i+offset[d1].x;
int y1=j+offset[d1].y;
int d2=map[i][j][m];
int x2=i+offset[d2].x;
int y2=j+offset[d2].y;
int n1=check(x1,y1);
int n2=check(x2,y2);
if( ( n1==0 && n2 ) || /*k方向不可达到，而m方向可达到*/
( n1 && n2&&weight[x1][y1]>weight[x2][y2] )/*都可到但达m方向权值小*/)
{ map[i][j][k]=d2;
map[i][j][m]=d1; /*向交换两个方值*/
}
//end if
}
//end for 4
}
//end for 3
}
//end for 2
}
//end for 1
}
//end setmap()
void TraverseOut(MyPoint *e)
{ static iEndl=1;
cout<<"("<<e->x<<","<<e->y<<") ";
iEndl%=8;
if(iEndl==0)
cout<<endl;
iEndl++;
}
bool Result(int myx, int myy, int board[][8])// bool (*callback)(MyStack<Type>&, bool)=NULL)
{ MyStack<MyPoint> sPath; // 栈,记录路径点
MyStack<int> sDir; // 栈,记录方向选择
MyPoint p,dest_p; // 当前点和目标点
int step = 1, d = 0; // 当前序号,方向
p.x = myx; p.y = myy;
sPath.push(p); sDir.push(d);//起始点的坐标和首选方向入栈,
// map[x][y][0]未必是(x,y)点的offset[0]方向,而是到该点可到的权值最小的点的方向即offset[map[x][y][0]]
board[p.x][p.y] = 1;//起始点标记已走且序号为1
MyPoint pTemp;int iTemp;
while(1)
{ if (step==N*N)
{ /*void(*pFun)(MyPoint *) ;
pFun=&TraverseOut;MyPoint *e=NULL;
cout<<"\n起始点为 ("<<myx<<","<<myy<<")的解空间\n";
cout<<"依次走以下坐标(按行顺序)[第 "<<num<<" 组] \n";
sPath.traverse(TraverseOut,e);*/
output();
if(ch=='q')
break;
else//回退前一步
{ sPath.pop(p);sDir.pop(d);//退栈;
sDir.top(d);sDir.settop(d+1);step--;
continue;
}
}
if(sPath.top(p)==-1||sDir.top(d)==-1) break;
int x=p.x;
int y=p.y;
if(d>=8)//该点所有方向已走完，退栈
{ //cout<<endl<<"back:("<<x<<" ,"<<y<<")#"; //debug info
board[x][y]=0;//抹去痕迹;
step--;
sPath.pop(pTemp);sDir.pop(iTemp);//退栈
sDir.top(iTemp);
sDir.settop(iTemp+1);//更改方向
continue;
}
//end if (d>=8)
if(d<8)//方向未走完
{ int off=map[x][y][d];
dest_p.x=x+offset[off].x;dest_p.y=y+offset[off].y;
if(check(dest_p.x,dest_p.y)&&board[dest_p.x][dest_p.y]==0)//目标点在棋盘内且未被走过,将目标点入栈并标记当前点为已走过
{ //cout<<"\n"<<"in :("<<dest_p.x<<","<<dest_p.y<<") step="<<step<<" d:"<<d;//debug info
board[x][y]=step;//记录序号
step++;
sPath.push(dest_p);//存入目标点
sDir.push(0); //存入方向栈初始0;
continue;
}
else//i目标点已被走过或目标点不在棋盘内,换方向
{ d++;//取下一个方向
sDir.settop(d);//换方向
continue;//继续
}
}
//enf if(d<8)
}
//end while(1)
}
5调试分析
程序中的指针操作多次出现错误，尤其发生在操作栈中的方向分量时，由于操作的失误，开始实际未保存此数据，导致多次循环需要回溯时进入死循环。后改用Visual Studio 2003中VC++.net中的调试工具发现栈内的所有dir分量值均为-1，后改正即可。因为这个问题，我重改了一次整个程序。
6程序说明
1)输入起始方格坐标(X,Y)
2)求解第一组路径并显示,按Q键退出系统，按其他任意键求解并显示下一组路径
7经验和体会
由于一开始没有使用优化算法，使得路径计算很慢，采用了各点加权然后对各方向按权设置行走优先级的策略后求解速度很快，可以在极短的时间内求出一组解。本程序可以求出所有的可行解。
在本实验中，用MyStack堆栈类的traverse方法可以演示堆栈回溯情形，不过在字符界面下不够直观，图形界面正在开发中。该C++堆栈模板类是自定义的通用模板类。
路径求解核心算法Result的效率与很多因数有关，比如起始点，优化策略等，本程序使用的优化策略效率很高。
通过该实验，对基于堆栈的算法设计更深的认识，在刚开始调试的时候由于没有给MyStack堆栈类定义一个直接修改栈顶元素的函数settop,所以要修改方向有点麻烦，必须先出栈，然后+1，然后再入栈，在定义了该函数后可以直接修改栈定元素。
在设计MyStack类的时候，对C++的通用模板类设计有了深的理解
8程序结果
8.1INPUT
输入的起始坐标:(0,0)
OUTPUT:
输出的第一组路径矩阵:
1 4 37 20 59 6 45 22
38 19 2 5 50 21 60 7
3 36 51 58 53 44 23 46
18 39 54 63 56 49 8 61
35 14 57 52 43 62 47 24
40 17 64 55 48 27 30 9
13 34 15 42 11 32 25 28
16 41 12 33 26 29 10 31
其他组解略
8.2INPUT
输入的起始坐标:(1，2)
OUTPUT:
输出的第一组路径矩阵:
2 29 48 15 12 31 56 17
47 14 1 30 49 16 11 32
28 3 50 13 62 57 18 55
51 46 61 58 39 54 33 10
4 27 52 63 60 37 40 19
45 24 59 38 53 64 9 34
26 5 22 43 36 7 20 41
23 44 25 6 21 42 35 8
其他组解略
9附 录
文件base 含有自定义的MyStack模板堆栈类的定义和实现，为各个项目共用文件；
文件 horse.cpp为本程序设计的主测试文件含有setmap，setweight，路径算法Result和main和其他UI接口函数。
支持一下
