[算法]图算法之骑士遍历问题（象棋中马的遍历问题）分析，C语言实现
今天再讲点跟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:n",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*/ |
代码，天啊。别让我看到。累。
以后有问题就到博主这边留言等你解决 呵呵·！
好的，非常欢迎您的提问，我会尽快解决你的问题
代码有点小难看.. 可以改精炼些.
感谢，我这里的代码主要是提供给初学者使用，因而提供完整代码以便调试使用