AYOJ N皇后问题

题目描述

 1 #include<cstdio>
 2 #include<cstring>
 3 int count, N;
 4 int vis[3][40];
 5 void dfs(int c)
 6 {
 7     if(c == N){count++;return ;}
 8     for(int i=0; i<N; i++){//c行i列是否能放入
 9         if(vis[0][i] == 0 && vis[1][c+i] == 0 && vis[2][c-i+N] == 0){
10             vis[0][i] = vis[1][c+i] = vis[2][c-i+N] = 1;
11             dfs(c+1);
12             vis[0][i] = vis[1][c+i] = vis[2][c-i+N] = 0;
13         }
14     }
15 }
16 int main()
17 {
18     int a[]={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184,14772512};
19     while(~scanf("%d", &N))
20     {
21         if(N==0)break;
22         //count = 0;
23         //memset(vis, 0, sizeof(vis));
24         //dfs(0);
25         //printf("%d
", count);
26         printf("%d
",a[N]);
27     }
28     return 0;
29 }

View Code

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

输入格式

共有若干行，每行一个正整数N≤16，表示棋盘和皇后的数量；如果N=0，表示结束。

输出

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

样例输入

1
8
5
0

样例输出

1
92
10