题目链接：
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
Recommend
lcy | We have carefully selected several similar problems for you:
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~~~
代码如下：
1 #include2 #include 3 #include 4 using namespace std; 5 int n, vis[11], cnt, ans[11]; 6 void Search(int cur){ 7 if (cur == n) cnt++; 8 else for (int i = 0; i < n; i++){ 9 int flag = 1;10 vis[cur] = i;11 for (int j = 0; j < cur; j++){12 if (vis[cur] == vis[j] || cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]){13 flag = 0;14 break;15 }16 }17 if (flag) Search(cur + 1);18 }19 }20 int main(){21 memset(ans, -1, sizeof(ans));22 while (~scanf("%d", &n), n){23 //while (cin >> n, n){ 24 cnt = 0;25 if (ans[n] != -1){26 printf("%d\n", ans[n]);27 continue;28 }29 Search(0);30 printf("%d\n", cnt);31 ans[n] = cnt;32 //cout << cnt << endl;33 }34 return 0;35 }
如果要输出排列情况，代码如下：
1 #include2 #include 3 #include 4 using namespace std; 5 int n, vis[11], cnt,T=1, ans[11]; 6 void Show(){ 7 for (int i = 0; i < n; i++){ 8 for (int j = 0; j < n; j++){ 9 if (j) cout << ' ';10 if (j == vis[i]) cout << char(3);11 else12 cout << '.';13 }14 cout << endl;15 }16 }17 void Search(int cur){18 if (cur == n){19 cout << "Case:" << T++ << endl;20 Show();21 cnt++;22 }23 else for (int i = 0; i < n; i++){24 int flag = 1;25 vis[cur] = i;26 for (int j = 0; j < cur; j++){27 if (vis[cur] == vis[j] || cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]){28 flag = 0;29 break;30 }31 }32 if (flag) Search(cur + 1);33 }34 }35 int main(){36 memset(ans, -1, sizeof(ans));37 while (cout<<"请输入皇后数：",cin >> n, n){38 T = 1;39 cnt = 0;40 Search(0);41 cout << "总排列方式："< << endl;42 }43 return 0;44 }