八皇后问题

是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
考虑到每行只能放置一个皇后，每列也只能放置一个皇后，那么如果把n列皇后所在的行号一次写出，那么就会是1~n的一个排列。
于是只需要枚举1~n的所有排列，查看每个排列是否合法即可。八皇后总共有n！个排列即40320此枚举。
又，一般来说，如果能在到达递归边界前的某层，由于一些事实导致已经不需要往任何一个子问题递归，就可以直接返回上一层。一般把此称为回溯法。

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

const int maxn = 20;
int n, P[maxn], hashTable[maxn] = {false};
int coun = 0;
void generateP(int index)
{
    if (index == n+1)
    {
        coun++;
        printf("%d", coun);
        return;
    }
    for (int x = 1; x <= n; x++)
    {
        if(hashTable[x] == false)
        {
            bool flag = true;
            for(int pre  = 1; pre < index; pre++)
            {
                if(abs(index - pre) == abs(x - P[pre]))
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                P[index] = x;
                hashTable[x] = true;
                generateP(index + 1);
                hashTable[x] = false;
            }
        }
    }
}
int main()
{
    scanf("%d", &n);
    generateP(1);
    return 0;
}