骑士巡游问题的回溯法分析

算法设计与分析课程论文

骑士巡游问题的回溯法分析

学院：信息工程学院

姓名： 学号： 指导老师：

问题描述：

骑士巡游（knight's tour）问题是指在有8×8 方格的国际象棋棋盘上进行奇异的骑士“L 型”（L-shaped）移动的问题。在国际象棋棋盘8×8 方格上的某个格子上放置一个骑士，然后这个骑士只能以马跳的方式前进，要求这个骑士相继地到达所有的64 个方格，进入每个方格一次且仅进入一次。

问题分析：

“L型”移动：

骑士的步进方式是按照“L型”移动的，即如下图所示，假设骑士的当前位于粉色格子的位置，那么它的下一步可能出现的合法位置为绿色格子的位置。

如此，我们定义坐标系，棋盘左上角格子为坐标原点（0，0），横坐标X轴以右为正方向，Y轴以下为正方向，当前骑士位置为（x，y），则可能出现的位置为(x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、(x-1,y-2)、(x-2,y-1)。

如此，骑士没进一步都按照此方式步进，直至整个棋盘都被“游走”一遍则完成。

边界情况分析：

在骑士“巡游”的过程中难免会游走到棋盘的边缘，那么此时下一步的坐标位置可能超出棋盘边界，此种情况下，需要相关的限定代码予以限制。

此外，因为要求棋盘每个位置要巡游且只巡游一次，所以当骑士巡游到某一位置时，可能会出现，棋盘没有被巡游完全，但不存在合法的下一步坐标点，此种情况下，则涉及到回溯的问题。

回溯算法的相关介绍：

回溯法总述：

回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法的深度优先搜索策略： 回溯法的基本做法是搜索，或是一种组织得井井有的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的主要思想：

回溯法在搜索解空间树时,通常采用两种策略避免无效搜索:其一是用约束函数在扩展结点处剪去不满足约束的子树;其二是用限界函数剪去得不到最优解的子树.这两类函数统称为剪枝函数。

回溯法的解题步骤：

(1)针对所给问题，定义问题的解空间；

(2)确定易于搜索的解空间结构；

(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

骑士巡游问题的回溯法分析：

骑士巡游问题中骑士每进一步都会面临下一步的多种选择，最终解也由N步的单步解构成，若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经做出的上一步，然后再继续向后步进。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。而边界情况是得到解的约束条件，即可据此获得剪枝函数。 由此问题分析我们发现，骑士巡游问题求解过程恰与回溯法求解问题的思路相符合，则此问题可以用回溯法来求解。

算法设计：

算法描述：

把棋盘左上角看作坐标原点，往右是x坐标正方向，往下是y坐标正方向。输入开始巡游的坐标，把每个格子初始化为没走过（visited[i][j]=false）。把初始坐标记做第1步（step=1），第1个格子标记为走过（visited[row-1][col-1]=true）。开始计算走法。首先计算每个格子下一步可能的走法，一共有8种，用循环把每一种走法都进行计算。判断是否超出棋盘和是否被标记走过（is_legal(x,y)&&(visited[cur_x][cur_y]==flase)），如不成立，则跳出判断语句；用select_direction()函数尝试下一步。如果成立，则标记此格走过（visited[cur_x][cur_y]=true）。并记录步数（step++）。判断是否已经走完所有格子（k=N*N）,如果成立，则说明没走完，递归到计算函数接着走棋盘；如果不成立，则说明已经走完所有格子，标记已经完成巡游。然后输出巡游结果。这样当所有方案都输出后，结束程序。如果从这某个格子开始，无法走遍所有格子，则巡游没完成，则程序判断从此点出发无法巡游棋盘的每一个位置。

回溯说明：

此程序的回溯关键在于递归上，根据递归算法的特性，函数中调用递归函数，则进入

递归，重新进入函数，当递归结束时，跳出，接着刚才函数的下面的语句运行。程序中，假设已经走到第K步，进入递归，走第K+1步，如果发现第K+1步走不下去，即是说，（is_legal(x,y)&&(visited[cur_x][cur_y]==tlase)）不成立，则跳出，接着刚才函数(第K步)运行，如果发现第K步也走不下去了，同样跳出，接着第K-1步运行。这样就实现了回溯的方法。

函数及变量说明： 函数或变量类型 常量 常量 Int型数组 Int型数组 Int型数组 Int型变量 Int型变量 Int型数组 Int型变量 无返回值函数 无返回值函数 无返回值函数 返回值Int型函数 返回值Int型函数 返回值Int型函数 无返回值函数 无返回值函数 返回值Int型函数 返回值Int型函数

程序流程图：

输入起始坐标 开始 变量或函数名 WIDTH MAX_DIR chessboard[WIDTH][WIDTH] direction[WIDTH][WIDTH] 意义 棋盘大小（8*8棋盘则值为8） 供选择方向数 棋盘数组（用来存储路径） 方向数组 visited[WIDTH][WIDTH][MAX_DIR] 棋盘标记数组（用来标记单元格是否被访问过） cur_x,cur_y step var_x[MAX_DIR]，var_y[MAX_DIR] last_direction; init_direction() init_status(int x, int y) print() is_legal(int x, int y) is_end() select_direction() forward() backward() tourist() main() 当前坐标 所走步数 下一步，坐标的变化情况 最近一次的方向 方位具体表示 初始状态 打印结果（包括格式控制） 判断点是否合法 判断是否巡游完毕 选择前进方向 前进至下一步 回溯至上一步 巡游函数（根据情况调用以上两函数） 主函数