题目描述

https://leetcode.com/problems/n-queens/description/

样例

方法

枚举N皇后的所有情况，在DFS过程中用剪枝函数排除（详见代码注释）

备注

本代码不能直接拿去粘贴

C++ 代码

//左上角原点（0,0）;已经放好的皇后（i，j）;下一个皇后（r,c) 
#include<bits/stdc++.h>
using namespace std;
int n,cnt=0;
int col[12]={0};
/* 
皇后剪枝规则
1.不同行
2.不同列
3.斜对角 abs(col[i]-c)==abs(i-r) 
*/ 
bool check(int c,int r)//剪枝函数   
{  
    for(int i=0;i<r;i++) 
        if(col[i]==c||(abs(col[i]-c)==abs(i-r)))//剪枝判断 
            return false;
    return true;
}
void DFS(int r)//轮到第r行 
{
    if(r==n)//递归返回 
    {
        cnt++;//统计个数 
        return;
    }
    for(int i=0;i<n;i++)
        if(check(i,r))//剪枝 
        {
            col[r]=i;//在第i行第c列放皇后 
            DFS(r+1);//接着来 
        }
}
int main(){
    int ans[12]={0};//答案数组 
    for(n=1;n<=10;n++)
    {
        memset(col,0,sizeof(col));//干完了初始化 
        cnt=0;
        DFS(0);
        ans[n]=cnt;//然后接着干...... 
    }
    while(cin>>n)
    {
        if(n==0)
            return 0;//干到0为止 
        cout<<ans[n]<<endl;
    }
    return 0;
}//yr