N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3072 Accepted Submission(s): 1419
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 code:
1 #include<iostream>
2 using namespace std;
3
4 #define MAX 12
5
6 int vst[MAX];
7 int cnt[MAX];
8 int ans;
9 int n;
10 bool flag;
11
12 void DFS(int row)
13 {
14 int i,j;
15 if(row==n+1)
16 ans++;
17 else
18 for(i=1;i<=n;i++)
19 {
20 flag=true;
21 vst[row]=i;
22 for(j=1;j<row;j++)
23 {
24 if(vst[row]==vst[j]||vst[row]-row==vst[j]-j||vst[row]+row==vst[j]+j) //关键
25 {
26 flag=false;
27 break;
28 }
29 }
30 if(flag)
31 DFS(row+1);
32 }
33 }
34
35 int main()
36 {
37 int i;
38 for(n=1;n<11;n++)
39 {
40 ans=0;
41 DFS(1);
42 cnt[n]=ans;
43 }
44 while(~scanf("%d",&n),n)
45 {
46 printf("%d\n",cnt[n]);
47 }
48 return 0;
49 }
转载于:https://www.cnblogs.com/XBWer/archive/2012/07/15/2592743.html