算法|八皇后问题理解回溯法
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。