算法学习之路|N皇后问题

N皇后问题，在棋盘上放n个皇后，要求互相之间不能攻击，求问有多少种情况
输入格式：
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
输出格式：
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
输入样例：
1
8
5
0
输出样例：
1
92
10

八皇后问题的拓展，回溯法

#include<stdio.h>  
#include<string.h>  
  
int map[11][11],n,cnt;  
bool pan(int x,int y)  
{  
    int i,j;  
    for(i=0;i<y;i++)  
        if(map[x][i])  
            return false;  
    for(i=x-1,j=y-1;i>=0&&j>=0;i--,j--)  
        if(map[i][j])  
            return false;  
    for(i=x+1,j=y-1;i<n&&j>=0;i++,j--)  
        if(map[i][j])  
            return false;  
    return true;  
}  
  
void dfs(int size)  
{  
    if(size==n)  
        cnt++;  
    for(int i=0;i<n;i++)  
    {  
        if(!map[i][size]&&pan(i,size))  
        {  
            map[i][size]=1;  
            dfs(size+1);  
            map[i][size]=0;  
        }  
    }  
    return ;  
}  
  
int main()  
{  
    int i;  
    int result[11];  
    for(i=0;i<11;i++)  
    {  
        memset(map,0,sizeof(map));  
        n=i+1;  
        cnt=0;  
        dfs(0);  
        result[i]=cnt;  
    }  
    while(~scanf("%d",&n)&&n)  
    {  
        printf("%d\n",result[n-1]);  
    }  
    return 0;  
}