算法｜八皇后问题理解回溯法
2022-08-21 21:19·小智雅汇
回溯算法从空解开始，并逐步扩展该解。搜索递归地通过各种不同的构造解决方案的路径。

例如，考虑计算n皇后问题：在n*n的棋盘上放置彼此不受攻击的n个皇后。

（皇后可以攻击在同一行、同一列、同一斜线上的棋子）

按以上规则：同一行或同一列或同一斜线上只能有一个皇后，同一行或同一列上必须有一个皇后。

n皇后问题的解空间是一棵n叉树，树的深度为n。

当n为4时，有两种可能的解决方案：

八皇后问题对于每一行是否可以放置皇后，可用一个规模为8的循环去判断。每一行的判断操作相同，如果操作完成了8行（放置了8个皇后），便求出了一个解。所以该问题可以用递归去做。如果某一行全部位置无法放置皇后时，没必要继续深入，可以回溯到上一步，也就是使用回溯法。对于非尾递归，递归函数回退时，递归点后面的代码就是递归函数回退后执行的部分。对于八皇后问题，上述的循环可以判断某行下一列是否可以放置皇后，而上一列放置皇后的操作进行逆操作后便完成了回溯（递归有天然的回退阶段）。

八皇后问题的暴力枚举搜索或递归解法会形成一个棵8叉完全树，回溯解法可以通过约束条件避免一些搜索继续深入，形成一棵8叉不完全树。

为简便起见，我们可以用四皇后问题去理解，然后泛化到一般的情况。

在底层，前三种配置是非法的，因为皇后们互相攻击。然而，第四种配置是有效的，可以通过在棋盘上再放置两个皇后来扩展到完整的解决方案。只有一种方法可以放置剩下的两个皇后。

如下面左图所示：

从y=0,x=0开始，search(0)递归调用search(1)（x=2,y=1），递归调用search(2)

当y=2，x=3时，递归函数search(2)执行完毕，回退到search(1)，x=0，逆操作，循环到x=3……

code demo:
//代码效果参考：http://www.zidongmutanji.com/zsjx/226035.html

include

define n 4

int column[n2] = {0};
int diag1[n2] = {0};
int diag2[n*2] = {0};
int count = 0;

void search(int y) {
if (y == n) {
count++;
return;
}
for (int x = 0; x < n; x++) {
if (column[x] || diag1[x+y] || diag2[x-y+n-1])
continue;
column[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
search(y+1);
column[x] = diag1[x+y] = diag2[x-y+n-1] = 0; // 回退时的逆操作，下一轮循环x++
}
return;
}

main()
{
search(0);
printf("%d\n",count);
getchar();
}
/
n=4, 2
n=8, 92
n=16, 14772512 /
搜索从调用search(0)开始。棋盘的大小为n*n，代码计算要计数的解决方案数。

代码假设棋盘的行和列编号从0到n-1。当使用参数y调用函数搜索时，它会在行y上放置皇后，然后使用参数y-1调用自身。然后，如果y=n，则已找到解决方案，变量count增加1。

数组column跟踪包含皇后的列，数组diag1和diag2跟踪对角线。不允许在已包含皇后的列或对角线中添加其他皇后。例如，4*4棋盘编号如下，当x、y取不同的值时，对应列方向column[x]、"/"方向上diag1[x+y]、"\"方向上diag2[x-y+4-1]的取值为0时表示无皇后：

y＝2，x=3

回溯。

y＝1，x=3

……

count=1。

回溯到下面绿色点：

继续逐步回溯：

……

count=2。

继续逐步回溯，最后count=2。