今天再講點跟 N 皇后有關的問題，騎士遍歷問題，或者象棋中馬的遍歷問題，當然這裡的馬是國際象棋了，兩者有著很多相似點，同時又有很多不同點，主要還是限制路徑的區別，N 皇后主要是自由放置只要滿足條件就好，馬的遍歷則跟上下遍歷的路徑有關了，主要運用了圖算法之深度廣度遍歷，以及圖的建立等演算法。
要求：實現棋盤上任意位置的一個棋子馬，使它不重複的走過棋盤上的每一個棋盤格
分析：首先知道馬在棋盤是怎麼走的，根據國際象棋規則，馬在一個起始位置共有 8 個可用的行動位置，當然邊界方面需要另外考慮，我們的馬的行走必須考慮這 8 種類可能性，排除不能使用的位置，走可用的位置，當 8 個位置不可以使用的時，需要考慮返回上一步，這點有點像圖的廣度優先遍歷相同，當馬走完所有位置，同時沒有可用的位置用於行走的時候遍歷結束。
分析完畢，代碼如下，如果各位有疑問，請留言：
/* 騎士遍歷問題
*2008 12 28 CG
**/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
int f[11][11] ;
int adjm[121][121];
long fgf;
int n,m;
int es(int i1,int j1,int i2,int j2){
adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
return;/* 建立路徑連接 */
}/*es*/
int creatadjm (){/* 繪製可用路徑圖 */
int i,j;
for(i=1;i< =n;i++)
for(j=1;j<=n;j++)
f [i][j]=0;/* 初始化路徑記錄 */
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
adjm [i][j]=0;/* 初始化棋盤 */
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (f [i][j]==0){/* 設置有效路徑 */
f[i][j]=1;
if((i+2<=n)&&(j+1<=n)) es(i,j,i+2,j+1);
if((i+2<=n)&&(j-1>=1)) es(i,j,i+2,j-1);
if((i-2>=1)&&(j+1< =n)) es(i,j,i-2,j+1);
if((i-2>=1)&&(j-1>=1)) es(i,j,i-2,j-1);
if((j+2< =n)&&(i+1<=n)) es(i,j,i+1,j+2);
if((j+2<=n)&&(i-1>=1)) es(i,j,i-1,j+2);
if((j-2>=1)&&(i+1< =n)) es(i,j,i+1,j-2);
if((j-2>=1)&&(i-1>=1)) es(i,j,i-1,j-2);
}/*if*/
return 1;
}/*createadjm*/
int travel (int p,int r){/* 騎士遍歷 */
int i,j,q;
for(i = 1 ; i < = n ; i++)
for(j = 1 ; j <= n ;j++)
if (f [i][j] > r)/* 符合要求？*/
f[i][j]=0;
r = r + 1;
i=((p-1) / n) + 1;
j=((p-1) % n) + 1;
f[i][j] = r;
fgf++;/* 記錄路徑選擇記錄 */
for(q = 1 ; q < = m ; q++){
i=((q-1) / n) + 1;
j=((q-1) % n) + 1;
if((adjm[p][q] == 1) && (f[i][j] == 0))
travel (q , r);/* 遞迴遍歷 */
}/*for*/
return 1;
}/*travel*/
int main(){
int i,j,k,l;
clrscr();
printf ("Input chessboard size n:");scanf ("% d",&n);/* 輸入棋盤大小，最大 11*/
m = n * n;
creatadjm ();/* 繪製可用路徑 */
/* 輸出可用路徑
for (i=1;i<=m;i++){/* 輸出 */
for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
printf("n");
}
getchar();
*/
printf ("Input a start post i,j:");/* 輸入開始遍歷的起點 */
scanf("%d %d",&i,&j);
l = (i - 1) * n + j;
while ((i> 0) || (j > 0)){/* 循環直到輸入 0 0*/
for(i = 1 ; i < = n ; i++)
for(j = 1 ; j <= n ; j++)
f [i][j] = 0;/* 初始化路徑記錄 */
k = 0;
travel (l , k);/* 遍歷 */
printf("select: %d pathnfinal path",fgf);/* 輸出路徑選擇次數 */
fgf=0;/* 清零 */
for (i = 1 ; i <= n ; i++){/* 輸出遍歷路徑 */
for(j = 1 ; j <= n ; j++)
printf("%4d",f[i][j]);
printf("n");
}
printf ("Input a start post i,j:");scanf ("% d % d",&i,&j);/* 繼續輸入 */
l = (i - 1) * n + j;
}/*while*/
return 0;
}/*main*/