从八皇后问题思考回溯法

article/2025/9/10 16:34:36

一、八皇后问题

八皇后是经典的回溯法问题，题目是说将八个皇后，放到8×8的国际象棋棋盘中中，使得任意两个皇后都不能在同一行、同一列以及同一条对角线上。下图是一个四皇后的搜索示意图。
在这里插入图片描述

八皇后问题可以通过暴力法求解，代码也很短：

代码1

for(solu[1] = 1; solu[1] <= 8; solu[1]++)for(solu[2] = 1; solu[2] <= 8; solu[2]++)for(solu[3] = 1; solu[3] <= 8; solu[3]++)for(solu[4] = 1; solu[4] <= 8; solu[4]++)for(solu[5] = 1; solu[5] <= 8; solu[5]++)for(solu[6] = 1; solu[6] <= 8; solu[6]++)for(solu[7] = 1; solu[7] <= 8; solu[7]++)for(solu[8] = 1; solu[8] <= 8; solu[8]++)if(不冲突)  output();

代码很好理解，但是问题在于：
1）这种写法本身不可取，因为如果皇后很多的话，这里的循环重数会很多，甚至如果皇后个数是未知数的话，程序更是没法写。

2）这种写法，时间复杂度极高（如果最开始两个皇后如果都放在第一列，那么后面6个皇后如论如何摆放都无济于事。虽然回溯法复杂度依然很高，但是可以通过剪枝的方法省去类似很多不必要的搜索。

为了解决上述问题，我们提出回溯法，回溯法的核心思想是：
1）如果发现错误立即改正，比如上面说到的，我们这里不可能让两个皇后出现在同一列的事情发生，如果有，则重新选择位置。

2）如果某一个皇后在一行没有任何位置可以放下去（无论如何都会跟前面的皇后冲突），那么我们有理由认为是前面的皇后放的位置不合理，因此回退到上一个皇后重新放置，这既是回溯。

代码2

const int n = 8;
int solu[n+1];bool NoConfilict(int k){for(int i = 1; i < k; i++)if(solu[i] == solu[k] || (k-i == abs(solu[i]-solu[k])))return false;return true;
}void PlaceQueue(int k){ //放置第k个皇后，因为不能在同一行，因此皇后k放在第k行if(k == n+1) //如果已经到第n+1行，则得到了一个正确的解Print();else for(int i = 1; i <= n; i++){solu[k] = i;if(NoConfilict(k)) //当前皇后跟之前皇后不冲突，放下一皇后，如果这一行都放不下，回溯。PlaceQueue(k+1);}
}

二、全排列问题

有了八皇后问题的解，其实很容易修改成全排列的问题，如下所示1 2 3的全排列棋盘。我们依然可以想象n×n的一个棋盘，如果不考虑冲突的话，第i行表示第i个数可以是1-n之间的所有数，但是因为是全排列，所以i之前选定的数字，i及后续的数不能跟之前重复。
在这里插入图片描述
这里定义冲突的方式跟八皇后问题不太一样，可以看到这里的冲突就是之后的数字跟之前不一样即可，怎么不一样呢？你很容易发现，只要不在同一列即可，相比之下，八皇后问题的冲突更为苛刻，因此我们只需要将八皇后问题的冲突判定方法的后半段删除即可。

代码3

bool NoConfilict(int k){for(int i = 1; i < k; i++)if(solu[i] == solu[k]) //注意这里的变化return false;return true;
}

然而判断在不在同一列只需要一个标记数组即可，因此一般我们有更简洁的写法：

代码4

const int n=3;
int solu[n+1], visit[n+1];void FillGrid(intk){if(k==n+1)Print();else for(inti=1;i<=n;i++){if(!visit[i]){solu[k]=i;visit[i]=1;FillGrid(k+1);visit[i]=0;}}
}

全排列的解法很多，比如字典序法、邻位交换等很多方法，读者可以参加组合数学。这里将另一种常见的递归全排列算法，代码很简短，但是却不是很好理解的一种写法，如下所示：

代码5

void solve(int k，int n){if(k==n+1)print(n);else for(int i=k;i<=n;i++){swap(a[k],a[i]);solve(k+1, n);swap(a[k],a[i]);}
}

我们注意到代码3和代码4中，我们每一行都会遍历n个位置，但实际上我们每一行并不是n个数都可以选择，那么我们是否可以每次给下一层限定一个区间呢？如果第1个数当然是n个数都可以选择，第2个数呢，加入第1个数选定为x后，那么第2位只能选取1~n之间除了x以外的其他数字，后续情况，以此类推。如下图所示：

第一个全排列：1 2 3 4 5 5 6 7 8
在这里插入图片描述

某一次全排列：3 4 5 6 8 7 1 2
注意每一行的交换情况，每一行的第一个与紫色框交换:
在这里插入图片描述

那么其实上述代码5就是这个思路，解读一下代码：

solve（k,n） ：求解[k,n]的全排列
for(int i=k;i<=n;i++) ：第k位的取值范围是[k,n]之间的所有数字
swap(a[k],a[i]) ：第k位是需要轮流[k,n]之间的数字，所以依次将第k位和后续的位交换
solve(k+1,n)：第k位确定后，自然可以考虑k+1位
swap(a[k],a[i]) ：我们注意到，后面还有一个交换，这一个交换是为了让之前交换的数字还原，使得下一次交换不受影响。

每一次得到一个[k,n]的排列，实际上包含了从第k位到第n位的n-k+1次交换，但是每次回溯的过程中，之前的交换全部换回来，保证了再次回溯到k的时候，[k,n]之间的所有数字跟最开始的序列完全一致，这也使得下一次我用第k位跟第i+1位交换的时候，a[i+1]能正确的放到a[k]的位置，同时a[k]放置于a[i+1]的位置。