最近在學(xué)習(xí)深度優(yōu)先搜索算法，接觸到了馬踏棋盤(pán)，決定嘗試一下。
涉及算法：遞歸，回溯法，深度優(yōu)先搜索算法
題目需求:國(guó)際象棋的棋盤(pán)為8*8的方格，現(xiàn)將"馬"放在任意制定的方格中，按照"馬"走棋的規(guī)則將"馬"進(jìn)行移動(dòng)。要求每個(gè)方格只能進(jìn)入一次，最終使得"馬"走遍棋盤(pán)的64個(gè)方格。
編寫(xiě)代碼，實(shí)現(xiàn)馬踏棋盤(pán)的操作要求用1~64來(lái)標(biāo)注"馬"移動(dòng)的路徑。
國(guó)際象棋的馬在走法上與象棋有相似之處，但是國(guó)際象棋是站在在格子里邊的，而象棋站線(xiàn)的交界處，
具體的上圖吧
國(guó)際象棋馬的走法
圖中0-7八個(gè)位置就是馬可以行走的下一步，于是，體現(xiàn)在代碼上就是下面的next()函數(shù)horse()就是算法的核心了，運(yùn)用遞歸+回溯。
由于8*8的方格可能出現(xiàn)的情況真的是太多了，要找到馬踏遍整個(gè)棋盤(pán)而且不重復(fù)真是挺不容易的，需要很長(zhǎng)時(shí)間，心疼我的CPU啊。 在這里可以把X Y 的值改為5或者6去測(cè)試，這樣就快多了。調(diào)用time.h頭文件就可以測(cè)試出來(lái)程序運(yùn)行的用時(shí)
多說(shuō)無(wú)用，上代碼
#include
#include
#define X 8
#define Y 8
int chess[X][Y];
//找到基于(x,y)位置的下一個(gè)可走的位置
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;
}
//打印輸出棋盤(pán)
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("馬踏棋盤(pán)失?。n");
}
end = clock();
printf("共計(jì)用時(shí):%lf\n",(double)(end-begin)/CLOCKS_PER_SEC);
return 0;
}
6*6棋盤(pán)運(yùn)行結(jié)果截圖：
運(yùn)行結(jié)果
