题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2553
N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
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 | We have carefully selected several similar
problems for you: 1016 1312 1241 1010 2614
N皇后问题可以说是一个经典的回溯问题，看看下面的动画对皇后问题的求解有了一个大致的想法；
这里采用逐行放置的办法，那么就可以不用考虑皇后的横向攻击问题，只需要检查是否纵向和斜向攻击即可。
斜向判断条件"cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]"，原理用一下两个表来说明
格子(x,y)的y-x标识了主对角线
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
| -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 |
| -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 |
| -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 |
| -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 |
| -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
格子(x,y)的x+y标识了副对角线
然后有一点特别坑的就是，这里虽然N<=10，但是是多组输入，刚开始一直超时，我习惯性的用cin输入，以为是这里的问题，
改了还是超时，各种改各种超时，最后想到也许输入100组N<=10，有重复的N,如果把每个值存贮了就不用算第二次了，改了下
总算过了。Orz~~~
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, vis[], cnt, ans[];
void Search(int cur){
if (cur == n) cnt++;
else for (int i = ; i < n; i++){
int flag = ;
vis[cur] = i;
for (int j = ; j < cur; j++){
if (vis[cur] == vis[j] || cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]){
flag = ;
break;
}
}
if (flag) Search(cur + );
}
}
int main(){
memset(ans, -, sizeof(ans));
while (~scanf("%d", &n), n){
//while (cin >> n, n){
cnt = ;
if (ans[n] != -){
printf("%d\n", ans[n]);
continue;
}
Search();
printf("%d\n", cnt);
ans[n] = cnt;
//cout << cnt << endl;
}
return ;
}
如果要输出排列情况，代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, vis[], cnt,T=, ans[];
void Show(){
for (int i = ; i < n; i++){
for (int j = ; j < n; j++){
if (j) cout << ' ';
if (j == vis[i]) cout << char();
else
cout << '.';
}
cout << endl;
}
}
void Search(int cur){
if (cur == n){
cout << "Case:" << T++ << endl;
Show();
cnt++;
}
else for (int i = ; i < n; i++){
int flag = ;
vis[cur] = i;
for (int j = ; j < cur; j++){
if (vis[cur] == vis[j] || cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]){
flag = ;
break;
}
}
if (flag) Search(cur + );
}
}
int main(){
memset(ans, -, sizeof(ans));
while (cout<<"请输入皇后数：",cin >> n, n){
T = ;
cnt = ;
Search();
cout << "总排列方式："<<cnt << endl;
}
return ;
}
