Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
解题思路：回溯法。可以用一个大小为n的一维数组来表示皇后的摆放情况。a[i]=j表示第i行的皇后的摆放位置是第j列。我们假设前面k-1个皇后的摆放位置没有问题，我们如何判断第k个皇后的摆放位置是否有问题呢？相关的判断定义在函数place中，如果i从1到k-1,都没有a[i]==a[k]||abs(a[i]-a[k])==abs(i-k)成立，那表示第k个皇后的位置摆放的也没有问题。a[i]==a[k]表示两个皇后摆放在同一列，很显然不成立。怎么判断两个皇后摆放在同一条对角线上呢？先来个图示例一下：
如果两个皇后在同一条对角线上那么一定有abs(a[i]-a[k])==abs(i-k)成立，可以理解成两者在一个正方形的两个角上。
class Solution {private: int *a; int sum; bool place(int k){ int i; for(i=1;i<k;i++){ if(a[i]==a[k]||abs(a[i]-a[k])==abs(i-k)) return false; } return true; }public: int totalNQueens(int n) { int sum=0; a=new int [n+1]; memset(a,0,(n+1)*sizeof(int)); int k=1; while(k>0){ a[k]++;//第k行开始放在第一纵列 while(a[k]<=n&&!place(k))//a[k]放在第1到n行，且要保证摆放不破坏规则 a[k]++; if(a[k]<=n&&k==n){//最后的结果满足要求 sum++; } else if(a[k]<=n&&k<n)//继续摆放下一行 k++; else //不符合要求，回溯 a[k--]=0; } return sum; }};
原文：http://www.cnblogs.com/zhoudayang/p/5059654.html