N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21808    Accepted Submission(s): 9748 Problem Description 在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。   Input 共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。   Output 共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。   Sample Input 1 8 5 0   Sample Output 1 92 10   Author cgf   Source 2008 HZNU Programming Contest   Recommend lcy //回溯算法 #include<iostream> #include<memory.h> #include<math.h> using namespace std; int a[101],b[101]; int n; int vis(int k)//判断是否在对角线，同行，同列 { for(int i=1;i<k;i++) { if(a[i]==a[k]||abs(i-k)==abs(a[i]-a[k])) return 0;//不满足条件返回0 } return 1;//满足条件返回1 } int huisu(int n) { int sum=0,k=1;//sum 计数 k代表第k行，k从1开始 memset(a,0,sizeof(a)); while(k>=1)//k>=1时循环开始 循环结束的条件是第一行的标记大于n { a[k]=a[k]+1;//每行的第一个为1 while(k<=n&&vis(k)==0)//不满足条件或者标记超出 n（同一行找不同的列） { a[k]=a[k]+1;//不满足两个条件的继续标记 } if(k==n&&a[k]<=n) { sum++; } else if(k<n&&a[k]<=n) { k++; } else { a[k]=0; k=k-1;//回溯返回上一层 } //cout<<k<<" "; } return sum; } int main() { for(int i=1;i<=10;i++) { b[i]=huisu(i); } while(cin>>n,n!=0) { cout<<b[n]<<endl; } } //标记最后是： // 1 2 3 4 // 2 // 4 //1 // 3