马踏棋盘算法

最近在学习深度优先搜索算法，接触到了马踏棋盘，决定尝试一下。

涉及算法：递归，回溯法，深度优先搜索算法

题目需求:国际象棋的棋盘为8*8的方格，现将"马"放在任意制定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。

编写代码，实现马踏棋盘的操作要求用1~64来标注"马"移动的路径。

国际象棋的马在走法上与象棋有相似之处，但是国际象棋是站在在格子里边的，而象棋站线的交界处，

具体的上图吧

国际象棋马的走法

图中0-7八个位置就是马可以行走的下一步，于是，体现在代码上就是下面的next()函数horse()就是算法的核心了，运用递归+回溯。

由于8*8的方格可能出现的情况真的是太多了，要找到马踏遍整个棋盘而且不重复真是挺不容易的，需要很长时间，心疼我的CPU啊。 在这里可以把X Y 的值改为5或者6去测试，这样就快多了。调用time.h头文件就可以测试出来程序运行的用时

多说无用，上代码

#include
#include
#define X 8
#define Y 8
int chess[X][Y];
//找到基于(x,y)位置的下一个可走的位置
int next(int *x,int *y,int step){
switch(step){
case 0:
if( *y+2<=Y-1 && *x-1>=0 && chess[*x-1][*y+2] == 0 ){
*x-=1;
*y+=2;
return 1;
}
break;
case 1:
if( *y+2<=Y-1 && *x+1<=X-1 && chess[*x+1][*y+2]==0 ){
*x+=1;
*y+=2;
return 1;
}
break;
case 2:
if( *y+1<=Y-1 && *x+2<=X-1 && chess[*x+2][*y+1]==0){
*y+=1;
*x+=2;
return 1;
}
break;
case 3:
if( *y-1>=0 && *x+2<=X-1 && chess[*x+2][*y-1]==0){
*y-=1;
*x+=2;
return 1;
}
break;
case 4:
if( *y-2>=0 && *x+1<=X-1 && chess[*x+1][*y-2]==0){
*y-=2;
*x+=1;
return 1;
}
break;
case 5:
if( *y-2>=0&&*x-1>=0&& chess[*x-1][*y-2]==0){
*y-=2;
*x-=1;
return 1;
}
break;
case 6:
if( *y-1>=0&&*x-2>=0&&chess[*x-2][*y-1]==0){
*y-=1;
*x-=2;
return 1;
}
break;
case 7:
if( *y+1<=Y-1&&*x-2>=0&&chess[*x-2][*y+1]==0){
*y+=1;
*x-=2;
return 1;
}
break;
default:
break;
}
return 0;
}
//打印输出棋盘
void print(){
int i,j;
for(i=0;i
for(j=0;j
printf("%2d ",chess[i][j]);
}
printf("\n");
}
}
int horse(int x,int y,int tag){
int x1=x;int y1=y;
int flag =0,count=0;
chess[x][y]=tag;
if(tag==X*Y){
print();
return 1;
}
flag = next(&x1,&y1,count);
while(!flag && count<=7){
count++;
flag=next(&x1,&y1,count);
}
while(flag){
if(horse(x1,y1,tag+1)){
return 1;
}
x1 = x;
y1 = y;
count++;
flag=next(&x1,&y1,count);
while(!flag && count<=7){
count++;
flag=next(&x1,&y1,count);
}
}
if(!flag){
chess[x][y]=0;//回溯
}
return 0;
}
int main(){
int i,j;
for(i=0;i
for(j=0;j
chess[i][j]=0;
}
}

clock_t begin,end;
begin=clock();
if(!horse(2,0,1)){
printf("马踏棋盘失败！\n");
}
end = clock();
printf("共计用时:%lf\n",(double)(end-begin)/CLOCKS_PER_SEC);

return 0;
}

6*6棋盘运行结果截图：

运行结果