hdu 2553 N皇后问题（dfs）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;

int col[15];//第i行的棋子位于col[i]列
bool vis[15];//每一列是否有棋子
int ans[15];//解的个数
int sum;//解的个数

void dfs(int r,int n){//第几行，棋盘大小

    if(r==n+1){//递归结束条件
        ++sum;
        return;
    }

    int i,j;
    bool flag;//每放入一个棋子，是否可行

    for(i=1;i<=n;++i){//从第1列枚举到n列
        if(!vis[i]){//2.列不重复
            flag=true;//假设可行
            col[r]=i;
            for(j=1;j<r;++j){//判断对角线，看第r行与前r-1行是否位于对角线上
                if(abs(col[r]-col[j])==r-j){//3.对角线不重复
                    flag=false;
                    break;
                }
            }
            if(flag){//如果可行
                vis[i]=true;//放置棋子
                dfs(r+1,n);//1.行不重复
                vis[i]=false;//拿走棋子
            }
        }
    }

}

int main(){
    int i,n;

    for(i=1;i<11;++i){//打表
        memset(vis,false,sizeof(vis));//棋盘清空
        sum=0;//初始化
        dfs(1,i);//从第一行开始，棋盘大小为i*i
        ans[i]=sum;
    }

    while(scanf("%d",&n)&&n){
         printf("%d\n",ans[n]);
    }

    return 0;
}