马步遍历问题和骑士巡游问题的回溯算法
马步遍历问题和骑士巡游问题的回溯算法 马步遍历问题与骑士巡游(knight"s tour)问题是指在有8 8方格的国际象 棋棋盘上进行奇异的骑士“L型”(L-shaped)移动的问题。而骑士巡游问题实际是带 有约束条件的马步遍历问题,因此在用程序求解的时候可以一并求解。本文给出 求解这一问题的回溯算法之C++语言程序。论文关键词:骑士巡游,回溯算法,C++语言 一般地说,我们用如下方法表示一个解:即把数字0,1,…,63放入棋盘中的方 格来表示到达这些方格的顺序。解决骑士巡游问题更具创意的方法之一是由J. C. Warnsdorff在1823年提出的。其规则是:骑士总是移向具有最少出口且没有到达过 的方格之一。
由于骑士巡游问题实际是带有约束条件的马步遍历问题,因此在用程序求 解的时候可以一起求解。程序算法依然是回溯法,和皇后问题有相似之处。马步 遍历和骑士巡游问题的复杂度较高,求出一个解相对容易,但要求出所有的解是要 花一定时间的。
一、回溯算法的实现 1.为解决这个问题,我们把棋盘的横坐标定为i,纵坐标定为j。i和j的取值范 围是从1到SIZE。当某个骑士占了位置(i,j)时,其在这个位置上可以向8个方向以“L 型”移动,它们分别是: 方向1:i+2,j+1;
方向2:i+1,j+2;
方向3:i-1,j+2;
方向4:i-2,j+1;
方向5:i-2,j-1;
方向6:i-1,j-2;
方向7:i+1,j+2;方向8:i+2,j-1。
2.棋盘以二维数组表示,其下标最大值8,将骑士的每一步按1,2,3 … 64填入 数组相应单元。其过程如下: ……… for(int i=0;i8;i++) for(int j=0;j8;j++) trajKT[i][j]=0;