题解 | #N皇后问题#

dfs问题

1、把棋盘看作一个g[n][n]数组,我们一行一行的放，例如我们第一个肯定放g[1][1]这里，然后看下一行，下一行放哪呢？这就需要判断，从题目得知要满足三个条件（因为一行一行放所以行不重复这一条不用考虑，减去）：

1.1：同一列不能有重复 ---------
1.2：同一对角线不能有重复。这里我们右分为左对角线跟右对角线 ，为什么？-----------左对角线上i-j的结果都相同，右对角线上i+j的结果都相同。我们等会以此判断这个皇后是否满足条件

根据上面的规则我们判断下一个皇后放在哪，但是有的时候，会出现皇后没位置可放的情况（这一整行都不满足条件），说明上一个皇后的位置放错了，那就返回上一个皇后，如果上一个皇后也没位置可放了，那就再上上个皇后。

当放的皇后超过n个后，说明这种放法是成立的，总数加一，把所有的方法试完后，输出总数。

下面引用雨巨老师的代码，因为老师写的比自己的简单明了太多

```#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=30;
int n;
int g[N][N];
bool vis[N],l[N],r[N];
int cnt =0;
void dfs(int dep)
{
    if(dep == n){
        cnt++;
        return;
    }
    for(int i=0;i<n;i++){
        if(!vis[i]&& !l[dep+i] && !r[n-dep+i]){
            vis[i] = l[dep+i] = r[n-dep+i] = 1;
            dfs(dep+1);
            vis[i] = l[dep+i] = r[n-dep+i] = 0;
        }
    }
}
int main(){
    IOS;
    cin>>n;
    dfs(0);
    cout<<cnt;
    return 0;
}