N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12279 Accepted Submission(s): 5535
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
Author
cgf
Source
知识点:DFS 回溯法（可见http://www.cnblogs.com/ZP-Better/p/4649694.html）
题意：见题目描述(obviously)
思路：DFS 先找状态(目前所在第几行，目前所在第几列，目前已经放置的皇后数量）扩展方式：从第一列到最后一列搜索到合适的位置，最终状态：目前放置的皇后数量等于题目所要求的皇后数量。
重点:1.如何判断2个皇后不允许不允许处在与棋盘边框成45角的斜线上。将棋盘看成坐标图，row1+column1=row2+column2=c(x1+y1=x2+y2=c) or row1-column1=row2-column2=c(x1-y1=x2-y2=c)来判断2个皇后是否在棋盘边框成45角的斜线上。为了满足这个条件还需要将目前这个点与已经放置过的点(需要遍历前面的点）判断才满足。
2.这题卡时间，又由于数字较小所以要打表将这10种情况用数组存下。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,cnt;
int vis[];//标记数组
int picture[];//用下标来表示行号，自身存储列号。
bool judge(int r,int r2,int c2)//判断2个皇后是否在棋盘边框成45角的斜线上
{
for(int i=;i<=r;i++)//遍历已经放置皇后的点
{
if(i+picture[i]==r2+c2||i-picture[i]==r2-c2)
return false;
}
return true;
}
void dfs(int row,int column,int num)
{
if(num==n)
{
cnt++;
return;
}
for(int i=;i<n;i++)
if(!vis[i]&&judge(row,row+,i))
{
picture[row+]=i;
//printf("%dorz%dorz%d\n",row+1,i,num);
vis[i]=;
dfs(row+,i,num+);
vis[i]=;
}
}
int main()
{
while(~scanf("%d",&n))
{
cnt=;
memset(vis,,sizeof(vis));
memset(picture,,sizeof(picture));
for(int i=;i<n;i++)
{
vis[i]=;
picture[]=i;
dfs(,i,);
vis[i]=;//回溯法：还原标记
}
printf("%d\n",cnt);
}
return ;
}
通过上面代码得到10种情况答案。下面是AC代码
#include <cstdio>
#include <iostream>
int a[]={,,,,,,,,,,};
int n;
int main()
{
while(~scanf("%d",&n))
{if(n==)
break;
printf("%d\n",a[n]);}
return ;
}