N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1757 Accepted Submission(s): 772
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
8
5
0
Sample Output
1
92
10
92
10
//经典的N皇后问题
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std; int ch[][];
int n, num, result[]; void dfs(int x, int y)
{
if(ch[x][y]) return; //如果该点已经被攻击，则返回
int i, xx, yy;
if(x == n) //如果
{
num++;
return;
} //下面个人觉得比较巧妙，因为会有重复的地方很难分析是属于哪个皇后
//若用了下面位置的 ++ or -- ，则巧妙地避免上述情况
//一共八个方向进行标记：上、下、左、右、左上、左下、右上、右下
xx = x; yy = y;
while(xx>) ch[xx--][y]++;
xx = x; yy = y;
while(yy>) ch[x][yy--]++;
xx = x; yy = y;
while(xx<=n) ch[xx++][y]++;
xx = x; yy = y;
while(yy<=n) ch[x][yy++]++;
xx = x; yy = y;
while(xx<=n && yy<=n) ch[xx++][yy++]++;
xx = x; yy = y;
while(xx> && yy<=n) ch[xx--][yy++]++;
xx = x; yy = y;
while(xx<=n && yy>) ch[xx++][yy--]++;
xx = x; yy = y;
while(xx> && yy>) ch[xx--][yy--]++; for(i = ; i <= n; i++)
{
dfs(x+, i);
} //若这个皇后深搜后的结果不成功，则要返回原来的情况，八个方向都 --
xx = x; yy = y;
while(xx>) ch[xx--][y]--;
xx = x; yy = y;
while(yy>) ch[x][yy--]--;
xx = x; yy = y;
while(xx<=n) ch[xx++][y]--;
xx = x; yy = y;
while(yy<=n) ch[x][yy++]--;
xx = x; yy = y;
while(xx<=n && yy<=n) ch[xx++][yy++]--;
xx = x; yy = y;
while(xx> && yy<=n) ch[xx--][yy++]--;
xx = x; yy = y;
while(xx<=n && yy>) ch[xx++][yy--]--;
xx = x; yy = y;
while(xx> && yy>) ch[xx--][yy--]--;
} void init() //初始化函数
{
int i, j;
for(i = ; i < ; i++)
for(j = ; j < ; j++)
ch[i][j] = ;
} void set()
{
int i, k;
for(k = ; k <= ; k++)
{
num = ; n = k; //初始化
for(i = ; i <= k; i++)
{
init(); //初始化
dfs(, i); //继续dfs寻找
}
result[k] = num;
}
} int main()
{
set();
while(scanf("%d", &n), n)
{
printf("%d\n", result[n]);
} return ;
}