N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21779    Accepted Submission(s): 9744 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 分析：下过国际想象棋的都知道规则，题目要求是在n*n的棋盘上求有多少种摆法，用dfs。但是这个题目会超时必须得打表。

代码如下：

#include<stdio.h> #include<string.h> int vi[11]; int N,count; int ans[11];// a[x]=y表示x行y列已经放置了皇后 int judge(int ceng,int y) { for(int i=0;i<ceng;i++) { int data=vi[i]; if(data == y) //判断横竖方向上有没有放置 return 0; if(i+data == ceng+y) //判断一条对角线 return 0; if(i-data == ceng-y) //判断另一条对角线 return 0; } return 1; } void dfs(int ceng) { if(ceng==N) { count++; return ; } for(int i=0;i<N;i++) { if(judge(ceng,i)) { vi[ceng]=i; dfs(ceng+1); vi[ceng]=0; } } } int main() { int t; for(int i=1;i<=10;i++) { N=i; count=0; dfs(0); ans[i]=count; } while(scanf("%d",&t),t) { printf("%d\n",ans[t]); } return 0; }

2017/11/30 加入非递归版的代码：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int n,sum; int x[15],k; int ans[15]; int place() { for(int i=1;i<k;i++) //判定前k位上有没有冲突的 if( (abs(k-i)==abs(x[k]-x[i])) || (x[i]==x[k]) ) return 0; return 1; } void calc(){ sum=0; k=1; x[k]=1; do{ while(x[k]<=n && !place()) x[k]++; //在第k行上放的时候逐个位置试探 if(x[k]<=n){ if(k==n){//k放到最后一行且当前位置成立了 sum++; x[k]++;//继续下一个位置 } else x[++k]=1;//进行下一行，从第一个开始 } else{ //第k行放满了 x[--k]++; } }while(k>0); } int main() { for(int i=1;i<=10;i++){ n=i; calc(); ans[i]=sum; } while(scanf("%d",&n),n){ printf("%d\n",ans[n]); } return 0; }