843.n-皇后问题

详情见AcWing.843.n-皇后问题

DFS按行遍历

时间复杂度为 $O(n!)$

思路

n-皇后问题中要求每个皇后在棋盘中放置之后，该皇后所在的行列正，负，两条对角线，上都没有皇后。
经过推理可以知道，每行必定有一个皇后。也就是说我们遍历行的时候只需要判断列，正负对角线符合条件就可以了
为什么这个题可以使用DFS？
n皇后问题得出结果的步骤与求全排列基本一致，也是可以生成搜索树，利用DFS的深入来确定一个答案，利用回溯来获得多个答案

下面对代码进行注释

C++ 代码

//第一种方法DFS按行遍历
#include <iostream>
using namespace std;

const int N = 20;

int n;
char g[N][N];       //g数组用于存储整个棋盘，之后的放置皇后的棋盘改动也是在g数组上操作的
bool col[N],dg[N],udg[N];   
//col列数组，用于判断列上有没有皇后
//dg数组，用于判断正对角线上有没有皇后
//udg数组，用于判断负对角线上有没有皇后

void dfs(int u)             //u代表，当前遍历到了哪一行了
{
    if(u == n)              //u == n了说明已经遍历完所有的行了
    {
        for(int i = 0 ; i < n ; i++)    puts(g[i]);     //输出棋盘每行的结果
        puts("");
        return ;
    }


    for(int i = 0 ; i < n ; i++)            //对每列进行遍历
    {
        if(!col[i] && !dg[u + i] && !udg[n - u + i])        //列与正负对角线上都没有皇后
        {
            g[u][i] = 'Q';
            col[i] = true;
            dg[u + i] = true;               //dg里参数是u + i，dg代表着正对角线
            udg[n - u + i] = true;

            dfs(u + 1);                 //这里调用dfs(u + 1)才是更换行的操作


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

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;
}

DFS逐个枚举每个元素

时间复杂度为 $O(2的n平方次方)$

思路

第一个方法使用的是DFS按行搜索，之所以按行搜索是因为已经推理出来每行必定有皇后了，我们可以无视行的判定，只比较剩余的条件
而DFS逐个枚举每个元素，就是我们也不知道每行是否必须有一个皇后，就是每个格子进行枚举获得答案

C++ 代码

#include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; 
//判断数组之中多了一个数组row，用于判断这一行是否出现过皇后


// s表示已经放上去的皇后个数
void dfs(int x, int y, int s)               //dfs的参数换了，x，y就是棋盘坐标，从左上角(0,0)开始枚举，s是已经放置的皇后数量
{
    // 处理超出边界的情况
    if (y == n) y = 0, x ++ ;       //到达了列的边界，将列下标y重置，行下标x移动到下一行


    if (x == n) {                       //如果行走完的基础之上，皇后也放满到了n个
        if (s == n) { 
            for (int i = 0; i < n; i ++ ) puts(g[i]);   //输出
            puts("");
        }
        return;
    }

    //对每一个格子的处理总体有两种情况
    //1.不放皇后，直接进行下一个格子的枚举就可以了
    //2.放皇后，就需要进行放置的条件判断了


    //放置皇后情况
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;

        dfs(x, y + 1, s + 1);       //下一个格子递归遍历的时候别忘了s + 1

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

    //不放置皇后情况
    dfs(x, y + 1, s);
}


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

    dfs(0, 0, 0);

    return 0;
}