八皇后问题 dfs/递归

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
int ans=0;
int vis_Q[maxn];
int book_col[maxn];
int n;
bool judge(int r,int c)//能否放在r行c列判断
{
    if(book_col[c]==1) return false;//如果这列已经被占用，不行
    for(int i=1;i<r;i++)
    {
        if(abs(c-vis_Q[i])==abs(r-i)) return false;//如果和前面已将摆放好的在同一个对角线上，也不行
    }
    vis_Q[r]=c;//都不冲突，就让第r行标记为c，代表第r行的皇后放在c位置
    return true;
}
void show_Q()//output
{
    ans++;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vis_Q[i]==j)
            cout<<"Q ";
            else
            cout<<". ";
        }
        cout<<endl;
    }
    cout<<"_______________"<<endl;
}
void dfs_Q(int r)//核心代码，递归搜索，dfs
{
    if(r==n+1)
        show_Q();
    for(int j=1;j<=n;j++)
    {
        if(judge(r,j))
        {
            book_col[j]=1;
            dfs_Q(r+1);
            book_col[j]=0;
        }
    }
    return;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
       memset(book_col,0,sizeof(book_col));
       memset(vis_Q,0,sizeof(vis_Q));
       vis_Q[1]=i;
       book_col[i]=1;
       dfs_Q(2);
    }
    cout<<ans<<endl;//解的数目
    return 0;
}