N皇后问题(深搜板子题)

本文主要是介绍N皇后问题(深搜板子题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$N$皇后问题(以洛谷P1219为例)

在$n\times n$大小的棋盘上给出$n$个皇后，寻找使得所有皇后不同处一行、一列或一条斜线上的摆放方案总数。

本题难点在于考虑剪枝条件：

• 对广度进行剪枝(列)
• 对副对角线进行剪枝：$i+j$
• 对主对角线进行剪枝：$i-j+n$​(为避免出现负数)

#include<bits/stdc++.h>
using namespace std;
int n;
const int MAX=100;
int ans[MAX],sum;
bool lie[MAX],diag1[MAX],diag2[MAX];
void dfs(int h){if(h>=n){sum++;if(sum<=3){for(int i=0;i<n;i++) cout<<ans[i]+1<<' ';cout<<endl;}else return;}for(int i=0;i<n;i++){//对列广度，确保每一列都能分配到首个皇后if(!lie[i]&&!diag1[h+i]&&!diag2[h-i+n]){ans[h]=i;lie[i]=1;//占据本列diag1[h+i]=1;//占据副对角线diag2[h-i+n]=1;//占据主对角线dfs(h+1);//进入下一行进行搜素，已经确保不会出现在同一行lie[i]=0;diag1[h+i]=0;diag2[h-i+n]=0;}}
}
int main(){cin>>n;dfs(0);cout<<sum<<endl;return 0;
}

思考：本题与POJ-1321:棋盘问题的不同点

二者最大的不同点在于在for循环后，棋盘问题需要再次调用dfs进入下一列进行深搜，而$N$皇后问题则不需要。
造成这种差异的核心原因在于：

• $N$皇后问题：确保在$n\times n$的棋盘上需要摆$n$个皇后，即第一个皇后一定会出现在第一行
• 棋盘问题：在$n\times n$的棋盘上实际放置棋子的数量可能$\le$可放置棋子数量(即可能有摆不满的情况)，因此第一个棋子放置的位置可能不会从第一行(列)开始。

这篇关于N皇后问题(深搜板子题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---