骑士游历问题（C语言代码）

关于骑士游历问题，大家可以想到的方法是回溯法和贪心算法。回溯法的时间复杂度比较高，贪心算法的时间复杂度就好多了。

骑士游历问题

问题描述：

棋盘大小是8*8，骑士在棋盘任一方格开始游历。要求骑士游历棋盘的每一个方格且每个方格只游历一次。输出骑士的游历路径。

解决思路：

dir0、dir1…dir7由小到大排列，每次选择具有最少出口的方向，假设为dir0。如果骑士走到第n步时，没有出口可以选择，同时，骑士未完全遍历棋盘，那么骑士回溯到上一位置（（n-1）步），选择dir1方向。骑士游历依次进行下去。直至走到终点或回到原点。终点代表骑士游历完成，原点代表骑士游历失败（没有可以游历每个方格游历且只游历一次的路径）。这里假设当前位置的八个方向已经按照“具有出口”由小到大排列。

编写程序过程要解决的问题(先考虑简单的问题)：

一、每个位置最多有8个方向可以移动分别为：(-2,1)   (-1,2)   (1,2)   (2,1)   (2,-1)   (1,-2)   (-1,-2)   (-2,-1)；

主函数中骑士在初始位置时，对个变量进行初始化代码：

考虑到解决骑士游历需要用到多个函数。骑士前进、后退函数可能用到这八个方向移动的坐标。故将八个方向移动的坐标定义为全局变量，“int ktmove_x[max_dir],ktmove_y[max_dir];”。

二、判断骑士应该前进还是回溯：骑士在当前位置有可移动的方向则前进，反之，回溯到上一位置。八八棋盘上面的每个方格最多有八个方向可以移动。棋盘数组：“int chessboard[width][width];”，则可以定义一个三维数组来判断方格某一方向是否被访问过：“int is_visted[width][width][max_dir]={0};”，初始化为0，表示64个方格具有的出口方向（最多有八个）未被访问，两个数组同样是全局变量。

骑士前进函数：

 骑士回溯函数：

 三、确定骑士是完成游历还是回到原点：暂时使用“1” 与“0”分别表示完成游历与回到原点，无论骑士是完成游历或者回到原点都需要停止骑士的移动。骑士移动过程中，无法确定骑士到底需要前进多少次、回溯多少次。所以使用while()循环。但是，使用“1” 与“0”分别表示完成游历与回到原点，即while()循环进行下去的条件无论是0还是1都不符合。解决办法是将是否完成游历和是否回到原点分成2个功能函数：is_sucess()，1代表完成游历，0代表还未完成游历；int is_back_to_start()，1代表回到起始原点，0代表没有回到其实原点。那么，while()循环进行下去的条件就是：!is_end()&&!is_back_to_start()，既没有完成游历也没有回到原点。

判定骑士是否回到原点

判定骑士是否到达终点

四、这是最后一个也是最重要的问题：如何使用贪心法选定具有最少路径的方向

选定下一步是否有可以移动的方向，定义函数：select_dir()，定义局部变量count，使用两个for()循环分别计算当前位置周围的八个（最多有八个）位置的可移动方向。找出具有最小可移动方向的出口。

 代码中的关键是：变量count赋值给变量min_dir（count=min_dir）。

此外，还有一个函数，判定骑士是否游历成功的函数

到此为止，骑士游历问题结束。

优点：时间复杂度小，花费时间少。空间复杂度相对增加。
缺点：全局变量多，功能函数可移植性比较差。

其他：代码中step自加1和自减1的含义。158-160行为什么step赋值给chessboard[startx][starty]后，就要自加1自加1，当骑士回溯到原点（但是还有可以试探的方向），重新选择可移动的方向时，step等于1，这样，程序就会误判骑士已回溯到原点且无可移动方向。

写代码过程，务必仔细。 我在写select_dir()函数时，不小心将if(is_legal(try_x,try_y)==1&&!is_visted[cur_x][cur_y][i]) 的代码写成：if(is_legal(try_x,try_y)==1&&is_visted[cur_x][cur_y][i])，检查半天也没找到错误。最后，用了近三个小时调试程序才找到这个错误。完整代码我已经上传到我的资源了，下载就行，使用的编程软件是VS2010。

文章知识点与官方知识档案匹配，可进一步学习相关知识C技能树首页概览114866 人正在系统学习中