N皇后问题

N皇后问题

N皇后问题是指将 N 个皇后放在 N×N 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

十分经典的作业题，高斯在这个问题上也没有得出正确的解（八皇后问题高斯给出的答案是76种，而正确答案是92种）

这个题目可以这么看，每一行只能放一个皇后，同时保证这一个皇后所对应的列，正反对角线都不能再放皇后。所以我们对于皇后的位置就有了判断的标准。

这里穿插一个小技巧：将棋盘看做一个坐标系，那么对角线上的点会满足x+y=b 或 x-y=b,这样一来，就有x-y为负数的情况，而棋盘的坐标系无负数象限，所以在后面加上一个N,即x-y+N=b，这样就可以避免负数情况。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 100;
char board[N][N];
bool col[N], dg[N], udg[N];          //因为每行只放一个皇后，所以要保证其每列，正反对角线上都不能有皇后
int n;
int sum = 0;

void search(int cnt)
{
    if (cnt == n)                  //n个皇后全部排好
    {
        sum++;
        cout << endl;
        for (int i = 0; i < n; i++) puts(board[i]);
        puts("");
        cout << "-------------------------------" << endl;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (!col[i] && !dg[cnt + i] && !udg[n - cnt + i])
        {
            board[cnt][i] = 'Q';          //放置皇后，将其所对应的位置上全部标记，不能再放
            col[i] = dg[cnt + i] = udg[n - cnt + i] = true;
            search(cnt + 1);
            col[i] = dg[cnt + i] = udg[n - cnt + i] = false;     //恢复现场，回溯
            board[cnt][i] = '.';
        }
    }

}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = '.';

    search(0);
    if (sum > 0)
        cout << "一共有" << sum << "种方法" << endl;
    else cout << "无解" << endl;
    return 0;
}