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 1221-1 -2数组2：0 1 2 3 4 5 6 71 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;//起始点标记已走且序号为1MyPoint 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;//记录序号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";break;}bool re=Result(x-'0',y-'0',board);cout<<endl<<endl;if(re=false)cout<<"Bye!\n\n";elsecout<<"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<<"\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)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;//起始点标记已走且序号为1MyPoint 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 infoboard[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 infoboard[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调试分析程序中的指针操作多次出现错误，尤其发生在操作栈中的方向分量时，由于操作的失误，开始实际未保存此数据，导致多次循环需要回溯时进入死循环。