N皇后问题
N皇后问题
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
解题思路
这道题主要考察的是回溯的思想。
我们以5个皇后为例讲这道题
首先我们把第一个皇后放在（1,1）处。那么很显然，第一行第一列以及（i，i）点所处位置即45度斜线方向都不可以放皇后了
我们看下一个皇后应该放在那里。（先看列再看行），很显然第一列不可以放了，第二列第一行即（1,2）不可以。第二列第二行（2,2）可以。那么我们放第二个皇后，同时按要求把他锁在的行列和45度角方向画上斜线
同上面的步骤一样，我们再找下一个皇后位置（2,3）。
我们可以看出来，这样放过（2,3）之后就在也放不下下一个皇后了。所以这种方法一共只能放三个皇后。是不合法的。
此时我们就用到了回溯。就是恢复到上一个放的皇后（2,2）哪里。重新找下一个皇后，而且我们知道在找到（2,3）皇后之前我们已经判断过哪些点了，所以我们紧接着判断（2,3）后面的点（2,4）就可以了，并且我们一定要把（2,3）位置恢复成没有标记过的点。
找到下一个皇后（第三个皇后）位置为（5,3）.
找第四个皇后位置（2,4）
找到第五个皇后位置
我们可以看出5个皇后已经都安排好位置了。我们再重新从空表开始，确定第一个皇后的位置就是（2,1）。按以上步骤找就可以了
代码
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int n;
int erwei[12][12]; //标记是否可以放皇后
int hang[12]; //标记行是否可以放皇后
int lie[12]; //标记列是否可以放皇后
int sum; //一共有几种方法
int table[12]; //几个皇后对应的有几种方法
bool check(int i, int j)
{
int s,t;
if(hang[i]) return false; //这一行已有皇后，该位置不合法。
if(lie[j]) return false; //这一列已有皇后，该位置不合法。
for(s=i-1,t=j-1;s>=0&&t>=0;s--,t--) //判断左上角有没有皇后。
{
if(erwei[s][t]) return false;
}
for(s=i+1,t=j+1;s<n&&t<n;s++,t++) //判断右下角有没有皇后。
{
if(erwei[s][t]) return false;
}
for(s=i-1,t=j+1;s>=0&&t<n;s--,t++) //判断右上角有没有皇后。
{
if(erwei[s][t]) return false;
}
for(s=i+1,t=j-1;s<n&&t>=0;s++,t--) //判断左下角有没有皇后。
{
if(erwei[s][t]) return false;
}
return true;
}
void dfs(int j)
{
if(j==n)
{
sum++;
return;
}
for(int i=0;i<n;i++)
{
bool flag=check(i,j); //判断该位置是否可以放皇后
if(flag) //如果该位置可以放
{
erwei[i][j]=1;
hang[i]=1;
lie[j]=1;
dfs(j+1); //判断下一列
erwei[i][j]=0;
hang[i]=0;
lie[j]=0;
}
}
}
int main()
{
for(int i=1;i<=10;i++)
{
memset(erwei,0,sizeof(erwei));
memset(hang,0,sizeof(hang));
memset(lie,0,sizeof(lie));
n=i;
sum=0;
dfs(0);
table[i]=sum;
}
while(scanf("%d",&n))
{
if(n==0)
break;
printf("%d\n",table[n]);
}
return 0;
}