n-皇后问题 第一种搜索顺序，按单元搜索

第一种是有两种分支：在当前格子放皇后，还是不放皇后。判断前面的dfs对应不放皇后，判断里面的dfs对应放皇后，都不可以去掉。第二种是枚举在当前行的哪一列上放皇后。
两种方法综合来看：每次在放皇后时，都需要先判断；不放时不用判断。

递归可以看作二叉搜索树
把当前节点不放皇后的看作0， 放皇后看作1
先序遍历：
讨论当前格子是放皇后还是不放皇后
先遍历0，到头之后，再遍历1（放皇后）
从根节点到叶节点代表着一种排列情况
当1个个数满足n的时候，代表每行都放了皇后，直接输出

样例

4

按单元搜，搜索树前序遍历

(暴力枚举) $O(2^n^2)$

时间复杂度

参考文献

y总代码

C++ 代码

#include<iostream>
using namespace std;
const int N = 20;
bool dg[N], udg[N], col[N], row[N];
char chess[N][N];
int n;

/*s表示放了皇后的行数，当s == n 时候表示，一种排列已经结束。可以输出。*/
void dfs(int x, int y, int s)
{
    if(s > n) return ;
    if(y == n) x++,y = 0;
    if(x == n)
    {
        /*当s == n 时候表示，一种排列已经结束。可以输出*/
        if(s == n)
        {
            for(int i = 0; i < n; ++i)
                cout << chess[i] << endl;
            puts("");
        }
        return;
    }
    /*讨论当前格子是放皇后还是不放皇后*/
    dfs(x, y + 1, s);
    /*满足条件可以放皇后，放一个皇后s + 1*/
    if(!dg[x + y] && !udg[n - x + y] && !col[y] && !row[x]) 
    {
        chess[x][y] = 'Q';
        dg[x + y] = udg[n - x + y] = col[y] = row[x] = true; 
        /*只有放了皇后，s 才能 + 1*/
        dfs(x, y + 1, s + 1);
        dg[x + y] = udg[n - x + y] = col[y] = row[x] = false;
        chess[x][y] = '.';
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            chess[i][j] = '.';
    dfs(0,0, 0);
    return 0;
}