先说一段废话，前天开始看马哥的运维教程，才知道的51cto，于是速速落脚这里了，以后就让这里陪伴着自己一起学习把，就酱！先为自己加油！！！
现在开始 骑士旅游：
算法描述：
骑士旅游（Knight tour）在十八世纪备受数学家与拼图迷的注意，它什么时候被提出来已不可考，具体的方法为：在一个标准国际象棋棋盘上（8*8方格），骑士行走在格子内，行走规则为：先平动两格，再延与平动方向垂直的方向平动一个（即走出一个“日”）如图（1）走法，现有一骑士，置于棋盘的任意位置，要求列出骑士走遍整个棋盘的顺序。
图（1）（X即为马可以走的位置）
算法实现：
首先考虑到骑士需要走遍整个棋盘，创建一个8*8的二维数组，存储骑士走过的每一步。
int chess[8][8]={0}; //定义棋盘 其次需要遍历骑士下一步所走的位置，创建一个8*2的二维数组，存储骑士下一步所要走的位置变化量。
int move[8][2]={ {1,-2},{2,-1}, {2,1},{1,2}, {-1,2},{-2,1}, {-2,-1},{-1,-2}}; //遍历下一个日的位置 我们在棋盘的每个位置添加此位置为骑士走的第几步，在骑士走完整个棋盘后输出棋盘数组，即可得到骑士的行走路线，因此需要变量记录骑士走到第几步。 //记录马踏的每一步
int cnt=1; //记录马踏的每一步
递归实现骑士旅游（horse函数）：
在函数中直接将cnt赋值到了棋盘，因此函数无返回值，每次执行horse需要知道当前骑士所处位置，因此将骑士位置（X，Y）作为horse的参数。
void horse(int x,int y){} 遍历下一步所能走的每一个“日”的位置，将位置存储在（a,b）中，判断该位置是否位于棋盘上，并且该位置是否已经走过，如果条件为真，将cnt赋值到当前“日”的位置，cnt自加1，判断当前位置是否为最后一个位置
条件为真，则输出整个棋盘，同时将骑士最后的一步赋为0，cnt减一，返回第63步继续遍历。
条件为假，则执行递归，继续判断下一个“日”的位置，遍历所有位置均无可走位置时，则回溯到上一步，将该位置棋盘赋为0，cnt减一。
由于以上两个条件均有chess[a][b]=0; cnt--;则将这两步置于判断之外。
int a,b,i;for(i=0;i<8;i++){ a=x+move[i][0]; b=y+move[i][1]; if(a>=0&&a<8&&b>=0&&b<8&&!chess[a][b]) { chess[a][b]=++cnt; if(cnt<64) horse(a,b); else print(); chess[a][b]=0; //回溯 cnt--; } } 至此，只要算法思想已完成，完整代码放在最后：
//马踏棋盘 递归实现//2015/01/23//小磊#include#include int chess[8][8]={0}; //定义棋盘int move[8][2]={ {1,-2},{2,-1}, {2,1},{1,2}, {-1,2},{-2,1}, {-2,-1},{-1,-2}}; //遍历下一个日的位置int cnt=1; //记录马踏的每一步int sum=1 ; //记录解的个数void print(){ int i,j; printf("\n"); printf("%d:\n",sum++); for(i=0;i<8;i++) { for(j=0;j<8;j++) printf("%5d",chess[i][j]); printf("\n"); }}void horse(int x,int y){ int a,b,i; for(i=0;i<8;i++) { a=x+move[i][0]; b=y+move[i][1]; if(a>=0&&a<8&&b>=0&&b<8&&!chess[a][b]) { chess[a][b]=++cnt; if(cnt<64) horse(a,b); else print(); chess[a][b]=0; cnt--; } }}void Init(){ int i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) chess[i][j]=0; } cnt=1;}int main(void){ int i,j; for(i=0;i<8;i++) for(j=0;j<8;j++) { Init(); chess[i][j]=1; //直接将马置于该位置，该位置为第一步 horse(i,j); } return 0; }
2015年1月25日