c语言算法骑士 [算法]C语言实现 骑士旅游（递归）

先说一段废话，前天开始看马哥的运维教程，才知道的51cto，于是速速落脚这里了，以后就让这里陪伴着自己一起学习把，就酱！先为自己加油！！！

现在开始 骑士旅游：

算法描述：

骑士旅游(Knight tour)在十八世纪备受数学家与拼图迷的注意，它什么时候被提出来已不可考，具体的方法为：在一个标准国际象棋棋盘上(8*8方格)，骑士行走在格子内，行走规则为：先平动两格，再延与平动方向垂直的方向平动一个(即走出一个“日”)如图(1)走法，现有一骑士，置于棋盘的任意位置，要求列出骑士走遍整个棋盘的顺序。

图(1)(X即为马可以走的位置)

算法实现：

首先考虑到骑士需要走遍整个棋盘，创建一个8*8的二维数组，存储骑士走过的每一步。

intchess[8][8]={0};//定义棋盘

其次需要遍历骑士下一步所走的位置，创建一个8*2的二维数组，存储骑士下一步所要走的位置变化量。

intmove[8][2]={{1,-2},{2,-1},

{2,1},{1,2},

{-1,2},{-2,1},

{-2,-1},{-1,-2}};//遍历下一个日的位置

我们在棋盘的每个位置添加此位置为骑士走的第几步，在骑士走完整个棋盘后输出棋盘数组，即可得到骑士的行走路线，因此需要变量记录骑士走到第几步。 //记录马踏的每一步

intcnt=1;//记录马踏的每一步

递归实现骑士旅游(horse函数)：

在函数中直接将cnt赋值到了棋盘，因此函数无返回值，每次执行horse需要知道当前骑士所处位置，因此将骑士位置(X，Y)作为horse的参数。

voidhorse(intx,inty){}

遍历下一步所能走的每一个“日”的位置，将位置存储在(a,b)中，判断该位置是否位于棋盘上，并且该位置是否已经走过，如果条件为真，将cnt赋值到当前“日”的位置，cnt自加1，判断当前位置是否为最后一个位置

条件为真，则输出整个棋盘，同时将骑士最后的一步赋为0，cnt减一，返回第63步继续遍历。

条件为假，则执行递归，继续判断下一个“日”的位置，遍历所有位置均无可走位置时，则回溯到上一步，将该位置棋盘赋为0，cnt减一。

由于以上两个条件均有chess[a][b]=0; cnt--;则将这两步置于判断之外。

inta,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);

elseprint();

chess[a][b]=0;//回溯

cnt--;

}

}

至此，只要算法思想已完成，完整代码放在最后：

//马踏棋盘递归实现

///01/23

//小磊

#include

#include

intchess[8][8]={0};//定义棋盘

intmove[8][2]={{1,-2},{2,-1},

{2,1},{1,2},

{-1,2},{-2,1},

{-2,-1},{-1,-2}};//遍历下一个日的位置

intcnt=1;//记录马踏的每一步

intsum=1;//记录解的个数

voidprint()

{

inti,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");

}

}

voidhorse(intx,inty)

{

inta,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);

elseprint();

chess[a][b]=0;

cnt--;

}

}

}

voidInit()

{

inti,j;

for(i=0;i<8;i++)

{

for(j=0;j<8;j++)

chess[i][j]=0;

}

cnt=1;

}

intmain(void)

{

inti,j;

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

Init();

chess[i][j]=1;//直接将马置于该位置，该位置为第一步

horse(i,j);

}

return0;

}

1月25日