题目描述

n-皇后问题

样例

4

.Q..
…Q
Q…
..Q.

..Q.
Q…
…Q
.Q..

算法1

（DFS按行枚举） 时间复杂度O(n!)
对角线 dg[u+i]，反对角线udg[n−u+i]中的下标 u+i和 n−u+i 表示的是截下面分析中的(x,y)相当于上面的(u,i)
反对角线 y=x+b, 截距 b=y−x，因为我们要把b当做数组下标来用，显然b不能是负的，所以我们加上+n（实际上+n+4,+2n都行），来保证是结果是正的，即y-x+n而对角线y=−x+b,截距是b=y+x，这里截距一定是正的，所以不需要加偏移量

核心目的：找一些合法的下标来表示dg
或udg是否被标记过，所以如果你愿意，你取 udg[n+n−u+i] 也可以，只要所有(u,i)对可以映射过去就行

// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径


遇到无解的话，if条件没有一个成立，那就正常把这个函数运行完，然后进行回溯。对于void最后加return和不加是一样的!!!

参考文献

原文链接：https://www.acwing.com/solution/content/2820/

C++ 代码

#include<iostream>
using namespace std;



const int N =20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N];

void dfs(int u) {

    if(u==n) {//放满了棋盘，输出棋盘
        for(int i=0; i<n; i++) puts(g[i]);// 等价于cout << g[i] << endl;
        puts("");
        return;
    }

    for(int i=0; i<n; i++)//第 r 行，第 i 列 是否放皇后
    // 剪枝(对于不满足要求的点，不再继续往下搜索)  
        // udg[n - u + i]，+n是为了保证下标非负
        if(!col[i]&&!dg[u+i]&&!udg[n-u+i]) {//不冲突，放皇后
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[n-u+i]=true;//对应的 列， 斜线 状态改变

            dfs(u+1);//处理下一行

            col[i]=dg[u+i]=udg[n-u+i]=false;//恢复现场
            g[u][i]='.';
        }

}

int main() {

    cin >> n;

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            g[i][j]='.';

    dfs(0);

    return 0;

}