n皇后问题：n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。在文件5.in中给定棋盘的大小n，在文件5.out中输出放置方法的个数。

输入示例:
4
输出示例:
2

输入示例:
8
输出示例:
92

#include <iostream>

using namespace std;

const int N = 1010;

bool g[N][N];
bool col[N];
int res = 0;
int n;

bool panduan(int x, int y)
{
    if (g[x][y]) return false;

    int i = x - 1, j = y - 1;
    while (i > 0 && j > 0)
    {
        if (g[i][j]) return false;
        i --, j --;
    }

    i = x + 1, j = y + 1;
    while (i <= n && j <= n)
    {
        if (g[i][j]) return false;
        i ++, j ++;
    }
    i = x - 1, j = y + 1;
    while (i > 0 && j <= n)
    {
        if (g[i][j]) return false;
        i --, j ++;
    }

    i = x + 1, j = y - 1;
    while (i <= n && j > 0)
    {
        if (g[i][j]) return false;
        i ++, j --;
    }
    return true;
}

void dfs(int r)
{
    if (r > n) return;
    for (int i = 1; i <= n; i ++)
    {
        if (!col[i] && panduan(r, i))
        {
            g[r][i] = true;
            col[i] = true;
            if (r == n) 
            {
                res ++;
                g[r][i] = false;
                col[i] = false;
                return;
            }
            dfs(r + 1);
            g[r][i] = false;
            col[i] = false;
        }
    }

}



int main()
{
    cin >> n;
    int t = 0;

    dfs(1);
    cout << res;
    return 0;
}