回溯算法

蛮力法是对整个解空间树中的所有可能解进行穷举搜索的一种方法，但是只有满足约束条件的解才是可行解。在满足约束条件的前提下，只有满足目标函数的解才是最优解，因此结合目标函数进行搜索就有可能减少搜索空间。回溯法从根结点岀发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的(最优)解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝( pruning)。否则进入以该结点为根的子树，继续按照深度优先策略搜索。简单来说，回溯算法就是带有剪枝策略的蛮力法，回溯算法的时间复杂度是否能降低，取决于剪枝策略的设计。

骑士巡游问题

国际象棋为许多令人着迷的娱乐提供了固定的框架，这些框架独立于游戏本身。其中很多都是基于奇异的骑士 “L 型”（L-shaped）移动，一个经典的例子就是骑士巡游（knight's tour）问题。输入 n (1< = n < = 10) 代表棋盘的规模是 n * n 的规模，骑士从某个点出发。骑士按象棋中“马走日”的行走方式，要求骑士走遍所有棋盘的格子（遍历棋盘的所有格子），输出骑士巡游整张棋盘的走法。
例如对于 5×5 的棋盘(用黄颜色表示)，骑士位于坐标 (3,3) 的位置(用蓝色标出)，则骑士按照“日”字形可走的位置如下所示(用紫色标出)。

DFS 解法

求解思路

使用回溯法对问题进行求解，使用 DFS 暴力搜索出骑士从某个点出发的所有路径，所有的路径将构成一个解空间树。剪枝的方式是由于骑士从一个点行走有 8 个方向，若这 8 个方向都会出棋盘，或者走到已经走过的点上，则该点之下的解空间树必不存在可行解。

代码编写

首先先定义需要的辅助结构，需要定义一个二维数组作为骑士巡游的棋盘。

#define WIDTH 5
#define HEIGHT 5

int checkerboard[6][6] = {0};

接着需要 2 个一维数组分别存储骑士 8 个方向的走法，nextStepX[i] 和 nextStepY[i] 表示骑士在二维空间的位移。

int nextStepX[8] = {-1, -1, -2, -2, 1, 1, 2, 2};
int nextStepY[8] = {2, -2, 1, -1, 2, -2, 1, -1};

剪枝的方式是由于骑士从一个点行走有 8 个方向，若这 8 个方向都会出棋盘，或者走到已经走过的点上，则该点之下的解空间树必不存在可行解。剪枝函数如下：

bool judgePrune(int x, int y)
{
	return ((x >= 1 && x <= WIDTH && y >= 1 && y <= HEIGHT) && checkerboard[x][y] == 0);
}

DFS 搜索路径的函数如下：

void travel(int x, int y, int step)
{
	int next_x;
	int next_y;

        checkerboard[x][y] = step;
	if (step == WIDTH * HEIGHT)
	{
		print(checkerboard);
		return;
	}
	for (int i = 0; i < 8; i++)
	{
		next_x = x + nextStepX[i];
		next_y = y + nextStepY[i];
		if(judgePrune(next_x, next_y) == true){
			travel(next_x, next_y, step + 1);
		}
	}
	checkerboard[x][y] = 0;
	return; 
}

int main()
{
	travel(1,1,1);
	return 0;
}

结果分析

5×5 棋盘的骑士巡游可行解：

6×6 棋盘的骑士巡游可行解：

7×7 棋盘的骑士巡游可行解：

8×8 棋盘的骑士巡游可行解，使用上面的没有跑出来，由此可见直接 DFS 没有过多的剪枝策略，导致了算法的效率很低下。

剪枝策略优化

注意到上文使用的剪枝策略非常简单，只是把不可能有可行解的情况忽略掉，实践证明这样的策略非常低效，几乎等于是蛮力法。由于骑士巡游问题不需要得到最优解，只需要得到一种可行解即可，因此剪枝策略应该保证尽快地接近可行解。分析上文直接 DFS 的性能，会发现每一步巡游的尝试顺序都是依次把 8 个方向尝试一遍，但是 8 个方向中可能会存在可走的方向过多而导致决策树的解空间过大，导致搜索性能过慢。
例如当前骑士位于 5×5 棋盘上的 (1,1) 坐标处(绿色表示已巡游的位置)，并且骑士选择 (2,3) 为落点进行巡游，则下一步骑士可巡游的位置用紫色标注。

如果骑士选择坐标 (4,4)，则骑士的下一次巡游的选择有 (2,5)、(3,2)、(5，2) 3 种情况。

如果骑士选择坐标 (1,5)，则骑士的下一次巡游的选择仅有 (3,4) 1 种情况。可见如果骑士选择下一次巡游的可走方向较少的位置进行移动，则骑士的下一次巡游的解空间树的规模会大幅度减小，就可以更快地逼近可行解。

如果能让骑士尽可能选择下一次可走的方向较少的坐标进行巡游，则呈现的效果就是骑士先绕着棋盘的外围巡游，然后再逐层到棋盘的内层巡游。因为当骑士位于棋盘外围时，由于有棋盘的边界限制，会有大部分的方向直接处于不可走的状态。当骑士巡游到内层时，由于棋盘外层已经被巡游过了，可以认为是棋盘的大小收缩了，即外层变为了棋盘新的边界，使得骑士在内层巡游时仍然可以大量剪枝。

代码编写

首先除了定义棋盘及其大小，还有两个一维数组表示骑士巡游的方向，方便起见定义结构体 Point 表示骑士的下一个落点。成员 dir 为骑士下一个落点的方向，取值范围 0 ~ 7，可以使用 “y + nextStepX[dir]” 和 “y + nextStepY[dir]” 得到下一个落点的坐标。成员 moves 是一个 vector 容器，存储下一个落点下一次可巡游的方向，如果 “moves.size() == 0” 则表示下一个落点没有可走的方向。
由于后面需要从所有可走的方向中，选择下一次巡游可走方向数最少的方向先走，因此需要对 Point 对 moves.size() 按照升序排序。此处可以重载 “<” 运算符，然后调用泛型算法 sort() 实现排序。

typedef struct Point
{
      int dir;    //巡游方向 
      vector<int> moves;    //下一次巡游可走方向 
      //重载“<”运算符 
      inline bool operator < (const Point &x) const 
      {
            return moves.size() < x.moves.size() ;
      }
} Point;

由于需要选择下一次巡游可走方向数最少的方向先走，因此就需要先获取下一次可走的所有方向，以此定义 getMoves() 函数获取。getMoves() 函数返回一个 vector，其中存储数字 0 ~ 7 表示可走的方向，若方向经 judgePrune() 函数判读可行就加入该容器中。

vector<int> getMoves(int x, int y)    //获得8个方向中可走的方向 
{
	vector<int> next_moves;
	for (int i = 0; i < 8; i++)
	{
		if(judgePrune(x + nextStepX[i], y + nextStepY[i]))
		{
			next_moves.push_back(i);
		}
	}
	return next_moves;
}

根据上文的剪枝策略，设计出新的搜索函数如下。

void travel(int x, int y, int step, Point pre)    //巡游函数 
{
	vector<Point> next_point;
	
        checkerboard[x][y] = step;    //标记当前位置已走过 
        //求出可行解，输出棋盘后回溯 
	if (step == WIDTH * HEIGHT)
	{
		print();
		return;
	}
	//当前位置无法继续巡游，回溯 
	if(pre.moves.size() == 0) 
	{
		return;
	}
	//依次获取下一个可行的位置的可走方向数 
	for (int i = 0; i < pre.moves.size(); i++)
	{
		Point a_point;
		a_point.dir = pre.moves[i];
		a_point.moves = getMoves(x + nextStepX[a_point.dir], y + nextStepY[a_point.dir]);
		next_point.push_back(a_point);
	}
	//选择下一次可走方向最少的方向先走 
	sort(next_point.begin(), next_point.end());    //对 next_point 根据 Point.moves.size() 做升序排序
	for (int i = 0; i < next_point.size(); i++)
	{
		travel(x + nextStepX[next_point[i].dir], y + nextStepY[next_point[i].dir], step + 1, next_point[i]);
	}
	//恢复状态，回溯 
	checkerboard[x][y] = 0;
	return;
}

最后初始化骑士的第一个落点，并获取其所有可走的方向，即可开始搜索。

int main()
{
	Point a_point;
	int x, y; 
	
	cout << "请输入起始位置的x坐标："; 
	cin >> x;
	cout << "请输入起始位置的y坐标："; 
	cin >> y;
	a_point.moves = getMoves(x, y);    //初始化初始点 
	travel(x, y, 1, a_point);
	return 0;
}

结果分析

8×8 棋盘的骑士巡游可行解：

9×9 棋盘的骑士巡游可行解：

15×15 棋盘的骑士巡游可行解：

经测试剪枝策略优化后，算法的性能大幅度提升，在 DFS 策略下无法快速找出 8×8 棋盘的可行解也可以求出，而且对于规模更大的棋盘也可以求解。