马踏棋盘问题初始版

本文主要是介绍马踏棋盘问题初始版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

#include<iostream>
#include<ctime>
using namespace std;
#define X 8
#define Y 8int chess[X][Y];
//判断下一步是否越界，注意case顺序不同，效率不同，可以考虑优化。
int nextxy(int *x,int *y,int count)
{switch(count){case 0:if(*x+2<X&&*y-1>=0&&chess[*x+2][*y-1]==0){*x+=2;*y-=1;return 1;}break;case 1:if(*x+2<X&&*y+1<Y&&chess[*x+2][*y+1]==0){*x+=2;*y+=1;return 1;}break;case 2:if(*x+1<X&&*y-2>=0&&chess[*x+1][*y-2]==0){*x+=1;*y-=2;return 1;}break;case 3:if(*x+1<X&&*y+2<Y&&chess[*x+1][*y+2]==0){*x+=1;*y+=2;return 1;}break;case 4:if(*x-2>=0&&*y-1>=0&&chess[*x-2][*y-1]==0){*x-=2;*y-=1;return 1;}break;case 5:if(*x-2>=0&&*y+1<Y&&chess[*x-2][*y+1]==0){*x-=2;*y+=1;return 1;}break;case 6:if(*x-1>=0&&*y-2>=0&&chess[*x-1][*y-2]==0){*x-=1;*y-=2;return 1;}break;case 7:if(*x-1>=0&&*y+2<Y&&chess[*x-1][*y+2]==0){*x-=1;*y+=2;return 1;}break;default:break;}return 0;
}
//打印棋盘
void print()
{for(int i=0;i<X;i++){for(int j=0;j<Y;j++)printf("%2d\t",chess[i][j]);printf("\n");}
}int TraverseChessBoard(int x,int y,int tag)
{int x1=x,y1=y,flag=0,count=0;chess[x][y]=tag;if(X*Y==tag)//tag==64，遍历结束{print();return 1;}flag=nextxy(&x1,&y1,count);while(flag==0&&count<7)//下一步有8个选项，一个不行再换一个{count++;flag=nextxy(&x1,&y1,count);}while(flag){if(TraverseChessBoard(x1,y1,tag+1)){return 1;}//如果一条路走不通，换一条x1=x;y1=y;count++;flag=nextxy(&x1,&y1,count);while(flag==0&&count<7){count++;flag=nextxy(&x1,&y1,count);}}//没路了，回溯。if(flag==0)chess[x][y]=0;return 0;
}void main()
{int i,j;clock_t start,finish;start=clock();for(i=0;i<X;i++)for(j=0;j<Y;j++)chess[i][j]=0;if(!TraverseChessBoard(2,0,1))printf("抱歉，马踏棋盘搜索失败！\n");finish=clock();printf("一共用时%f秒\n",double(finish-start)/CLOCKS_PER_SEC);//CLOCKS_PER_SEC每秒滴答数。
}

运行结果：