n皇后（dfs）

Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

1
8
5
0

Sample Output

1
92
10

对于某些题目需要打表，否则超时。

解一：

a[i]表示第i行皇后所在列数。保证了不同行、不同列。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,ans,a[10];
bool check()
{
    for(int i=1; i<=n; ++i)
    {
        for(int j=i+1; j<=n; ++j)
        {
            if(j-i==abs(a[j]-a[i]))
                return 0;
        }
    }
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int ans=0;
        if(n==0)
            break;
        for(int i=1; i<=n; ++i)
            a[i]=i;
        do
        {
            if(check())
                ans++;
        }
        while(next_permutation(a+1,a+1+n));
        cout << ans << '\n';
    }

    return 0;
}

解二：（打了个表）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=5e6+30;
bool vis[50][50];
int n,ans[20];

bool check(int x,int y)
{
    for(int i=1;i<x;i++)
        if(vis[i][y])
            return 0;
    for(int i=1;i<y;i++)
        if(vis[x][i])
            return 0;
    int xx=x-1;
    int yy=y-1;
    while(xx&&yy)
    {
        if(vis[xx][yy])
            return 0;
        xx--;
        yy--;
    }
    xx=x-1;
    yy=y+1;
    while(xx&&yy<=n)
    {
        if(vis[xx][yy])
            return 0;
        xx--;
        yy++;
    }
    return 1;
}
void dfs(int tmp)
{
    if(tmp==n+1)
    {
        ans[n]++;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(check(tmp,i))
        {
            vis[tmp][i]=1;
            dfs(tmp+1);
            vis[tmp][i]=0;
        }
    }
}
int main()
{
    for(n=1;n<=10;n++)
    {
        memset(vis,0,sizeof(vis));
        ans[n]=0;
        dfs(1);
    }
    while(scanf("%d",&n)!=EOF&&n)
        cout<<ans[n]<<'\n';
    return 0;
}