N皇后问题

       Time limit  1000 ms  

         Memory limit  32768 kB  

         

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 

你的任务是，对于给定的N，求出有多少种合法的放置方法。 

Input共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。Output共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。Sample Input

1850

Sample Output

19210 分析：搜索，每次检查一下该列是否已经放了皇后，同时检查主副对角线，主副对角线参考了别人数学的处理方法，即：在对角线上的两点坐标满足横纵坐标之差的绝对值相等！我刚开始是每一次输入一个查询的数据就搜索一次，然后交上去的代码超时了，后来用自己写的代码输出结果打了个表就AC了，参考了别人的博客，发现他们用的记忆化搜索的方式，就避免了重复搜索！我还是太菜啊！ AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 15using namespace std;int ans;int Queen[N];int n;void dfs(int k){ if (k==n+1) { ans++; return ; } int i,j; for ( i=1;i<=n;i++) { for (j=1;j
           
            =k) { Queen[k]=i; dfs(k+1); } }}int sum[N];int main(){ for (int i=1;i<=10;i++) { n=i; ans=0; dfs(1); sum[i]=ans; } while (cin>>n&&n!=0) { cout << sum[n] << endl; } return 0;}