(dfs+ pruning + checkerboard problem +dood) acwing 843 N-queen problem

843. n- queens problem

Topic link https://www.acwing.com/problem/content/845/
subject ：

Complexity ：0（n!）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
int n;
char a[10][10];
bool c[10],dj[30],udj[30];
void dfs(int u){
    
    if(u==n){
    
        for(int i=0;i<n;i++)
            puts(a[i]);
        puts("");
        return ;
    }
    for(int i=0;i<n;i++){
    
        if(!c[i]&&!dj[u+i]&&!udj[n-u+i]){
    
            c[i]=dj[u+i]=udj[n-u+i]=true;
            a[u][i]='Q';
            dfs(u+1);
            a[u][i]='.';
            c[i]=dj[u+i]=udj[n-u+i]=false;
        }
    }
}
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[i][j]='.';
    dfs(0);
    return 0;
}