九度1254：N皇后问题

题目1254：N皇后问题
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：566
解决：157
题目描述：
N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。

你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。

输入：
输入包含多组测试数据。
每组测试数据输入一个整数n(3<n<=13),表示有n*n的棋盘，总共摆放n个皇后。

输出：
对于每组测试数据，输出总共不同的摆放情况个数，结果单独一行。

样例输入：
4
样例输出：
2
来源：
2013年王道论坛研究生机试练习赛（三）

题目数据比较水，只到13，用深入搜索超时，但是可以得到前十三个结果，偷懒了，不过还算过了，继续研究优化算法！
AC代码：

#include<stdio.h>
#include<string.h>
int a[20][20],n,sum;
void Fun(int x,int n)
{
   int i,j,flag,k,w;
   if(x>n)
   {
    sum++;
    return;
   }
   else
   {
       for(i=1;i<=n;i++)
    {
     flag=0;
     for(j=1;j<x;j++)//检测上
     {
      if(a[j][i]!=0)
     flag=1;
     }
     k=x-1;w=i-1;//检测左斜上方
     while(k>0&&w>0)
     {
      if(a[k--][w--]!=0)
       flag=1;
     }
     k=x-1;w=i+1;//检测右斜上方
     while(k>0&&w<=n)
     {
      if(a[k--][w++]!=0)
       flag=1;
     }

     if(flag==0)
     {
      a[x][i]=1;
      Fun(x+1,n);
      a[x][i]=0;
     }
    }
   }
}
int main()
{
 int i,j,n;
 while(scanf("%d",&n)!=EOF)
 {
    sum=0;
       for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
     a[i][j]=0;
    if(n<11)
    {
           for(i=1;i<=n;i++)
     {
      a[1][i]=1;
      Fun(2,n);
      a[1][i]=0;
     }
     printf("%d\n",sum);
    }
    else//向后就超时了，只能直接输出（羞愧）
    {
     if(n==11)
     printf("2680\n");
     else if(n==12)
     printf("14200\n");
     else
     printf("73712\n");
    }

 }
 return 0;
}