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

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

算法设计与分析课程论文

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

学院：信息工程学院

姓名： 学号： 指导老师：

问题描述：

骑士巡游（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步运行。这样就实现了回溯的方法。

函数及变量说明：

程序流程图：

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

程序代码：

#include<stdio.h> #include<memory.h>

#define WIDTH 8

#define MAX_DIR 8 //表示没有方向可选 int

N

N

chessboard[WIDTH][WIDTH]={0}; //棋盘数组

int direction[WIDTH][WIDTH]; int

visited[WIDTH][WIDTH][MAX_DIR] = {0};//初始时为0表明各个位置的各个方向都未访问过 int cur_x,cur_y; //当前坐标 int step; //已走的步数

int last_direction; //上一次走的方向

// 下面两个数组用来记住选择某个方向后，推进到下一位置时x方向和y方向的值的变化 int var_x[MAX_DIR];

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

int var_y[MAX_DIR];

//八个方向的坐标变化情况 void init_direction() { var_x[0] = -2; var_y[0] = -1; var_x[1] = -1; var_y[1] = -2; var_x[2] = 1; var_y[2] = -2; var_x[3] = 2; var_y[3] = -1; var_x[4] = 2; var_y[4] = 1; var_x[5] = 1; var_y[5] = 2; var_x[6] = -1; var_y[6] = 2; var_x[7] = -2; var_y[7] = 1; }

//设置初始状态

void init_status(int x, int y) { step = 1; chessboard[x][y] = step; step ++; cur_x = x; cur_y = y; direction[x][y] = MAX_DIR; //每个位置都没有选择方向 last_direction = MAX_DIR; //上一次方向也没有 init_direction(); }

//输出巡游结果 void print() { int x, y; printf(" +"); for (x = 0; x < WIDTH; x++) printf("----+"); printf("\n"); for (x = 0; x < WIDTH; x++) { printf(" |"); for (y = 0; y < WIDTH; y++) printf("%3d |",chessboard[x][y]); printf("\n"); printf(" +"); for (y = 0; y < WIDTH; y++) printf("----+"); printf("\n"); } } //判断走这一步是否可行 int is_legal(int x, int y) { if( x < 0 || x >= WIDTH) return 0; if( y < 0 || y >= WIDTH) return 0; if( chessboard[x][y] != 0 ) return 0; return 1; }

//判断是否遍历完成 int is_end() { if( step > WIDTH * WIDTH ) return 1; else return 0; }

//判断是否回到起点 int is_back_to_start() { if (step == 1) return 1; else return 0; }

int select_direction() { int try_x, try_y, next_x, next_y; int i,j; int count,min_dir; min_dir = MAX_DIR; last_direction = MAX_DIR; for( i = 0; i < MAX_DIR; i++ ) { try_x = cur_x + var_x[i]; try_y = cur_y + var_y[i]; if(is_legal( try_x, try_y ) == 1 && !visited[cur_x][cur_y][i])//找出可选方向最少的方向 { count = 0; for( j = 0; j < MAX_DIR; j++ ) { next_x = try_x + var_x[j];

next_y = try_y + var_y[j]; if(is_legal(next_x, next_y) && !visited[cur_x][cur_y][j]) count ++; } if( count < min_dir ) { last_direction = i; min_dir = count; } } } if(last_direction == MAX_DIR) return 0; //没有方向可选 else return 1; //有方向可选 }

void forward() { // 该位置的这个方向已经试探过了 visited[cur_x][cur_y][last_direction] = 1; cur_x += var_x[last_direction]; cur_y += var_y[last_direction]; chessboard[cur_x][cur_y] = step; step ++; direction[cur_x][cur_y] = last_direction; last_direction = MAX_DIR; }

void backward() { int i; step --; chessboard[cur_x][cur_y] = 0;

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

// 将last_direction置为上一位置到(curr_x, curr_y)所选择的方向 last_direction = direction[cur_x][cur_y]; //把这个位置的各个方向都置为未访问过 for( i = 0; i < MAX_DIR; i++ ) visited[cur_x][cur_y][i] = 0; // 根据这个方向回溯到上一位置，同时回溯到上一位置之后，在上一位置再试探时应该从 // last_direction+1的方向开始。 cur_x -= var_x[last_direction]; cur_y -= var_y[last_direction]; }

部分执行结果截图：

int tourist() { do { if (select_direction()) forward(); else backward(); } while (!is_back_to_start() && !is_end()); if (is_back_to_start()) return 0; else return 1; }

int main() { int start_x = 1,start_y = 1;//起始位置坐标 printf("棋盘的大小为：%d×%d\n",WIDTH,WIDTH);

printf("请输入起始位置的行列数（两者之间用逗号隔开）："); scanf("%d,%d",&start_x,&start_y);

init_status( start_x, start_y ); //

memset(chessboard,0,sizeof(chessboard)); if(tourist()) { printf("遍历结果如下：\n"); print(); } else printf("找不到遍历路径!\n");

system("pause"); return 0; }

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

本文来源：https://www.bwwdw.com/article/mdhj.html