问题描述
在一个8*8的棋盘上 放置八个皇后 , 使得他们互相不攻击(皇后攻击范围为 同行同列同对角线)
方法一 :
从64个格子中 选一个子集 , 使得 " 子集 中恰好有八个元素 , 且任意选出的两个格子都不是同一行,同一列同,一对角线" ,
这是子集枚举问题 , 然而 , 64个格子的自己有2^64个 , 所需处理数据过大 !
方法二:
从64个格子中 选八个格子 , 称为组合生成问题 , 根据组合数学 有4.426*10^9中方案 , 虽然比第一种好 , 但是数据量依旧大.
最终方法
我们发现每一行每一列恰好会放一个皇后 , 所以可以从第一行开始放 , 然后考虑第二行 , 依次进行 下去 !这样就变成了全排列生成问题 , 这样的排列有 8! = 40320个 , 枚举量不会超过该数字
然而 如果每次都枚举这么多次的话 也会超时的 , 所以我们可以采用回溯+递归的方法.
实现代码1(递归)
#include<iostream> using namespace std; int C[50],tot = 0,n = 8,nc = 0;//nc:递归的次数. void search(int cur)//cur:第几行 { int i,j; nc++; if(cur==n){//如果皇后放置完,则结束. tot++; }else{ for(int i = 0; i < n;i++){//依次将皇后尝试放在该行的每一列 int ok=1;//用于标记该位置是否可行. C[cur] = i; for(int j = 0; j < cur; j++){ if(C[cur]==C[j]||C[cur]-cur==C[j]-j||C[cur]+cur==j+C[j]) {//判断是否纵向 和 斜向(主对角线和次对角线) 攻击 ok = 0; break;//如果 } } if(ok){// 递归回来后 就会尝试在下一个位置放置.. search(cur+1);//在下一行放置皇后. } } } } int main() { scanf("%d",&n); search(0); printf("%d\n",tot); printf("%d\n",nc); return 0; }
实现代码2(递归+回溯)
#include<iostream> #include<cstdio> #include<string.h> using namespace std; int C[50],vis[3][50],tot = 0,n = 0,nc = 0;//vis用于 vis[0]标记列是否已放置皇后 vis[1] 用于标记副对角线是否已存在节皇后点. vis[2]标记主对角线上是否存在皇后节点. //C:用于存放皇后的位置,如果不需要保存则可以忽略. void search(int cur){ nc++;//递归次数统计 if(cur==n){ tot++; }else{ for(int i = 0;i < n; i++){ if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]){//由于 横纵坐标相减可能出现赋值所以加上n 虽然有负值但不会出现重复的现象. C[cur] = i;// 保存皇后节点. vis[0][i] = vis[1][cur+i]=vis[2][cur-i+n] = 1;//更新vis search(cur+1); // 继续进行摆放下一个皇后节点 //为啥这里需要回溯呢? //因为当递归回到这里说明沿着之前的继续走已经没有路了,我们得去掉这个标记重新做出选择,即用C[cur]尝试其他的值... vis[0][i] = vis[1][cur+i]=vis[2][cur-i+n] = 0;//进行回溯,看当前行是否可以 在其他位置摆放皇后. } } } } int main() { scanf("%d",&n); memset(vis,0,sizeof(vis)); search(0);//从第一行开始进行递归 printf("%d\n",tot); printf("%d\n",nc); return 0; }
算法分析
以上这两种的递归次数一样.
但时间复杂度,第二种明显低于第一种(以空间换时间),第一种在进行判断时采用了循环,而第二种则使用三个标记,
总体来看递归+回溯的话时间复杂度会很低. 但空间复杂度会高点.
通俗的谈递归和回溯的区别:
我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。
我们选择了一个方向，后来发现又有一个多岔路口，这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上，再做一次尝试，即在函数内部再调用一次函数，这就是递归的过程。
这样重复了若干次之后，发现这次选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。
