n-皇后问题

思路分析

一、按格子枚举

枚举格子时候，我们可以从第一行第一个格子开始，每一个每一个的枚举

换行小技巧

if (y == n) y = 0, x ++ ;

当然，我们也可以用一个数表示坐标，x和y分别用除法和取模来表示
这里我们用x, y两个数字来表示

2. 合法

如果一个格子可以放，那么它当前行、列、对角线、反对角线都不会有别的皇后

每一个格子有两种状态，放或者不放

3. 结束条件

枚举到最后一个格子的下一个格子时，如果皇后有八个，那么就是正确答案，输出即可

二、按行枚举

我们可以发现上面枚举是过于暴力了，如果当前行放了皇后，那么这一行后面的所有都是不用考虑的

所以我们可以按行（列）进行枚举

1. 结束条件

枚举到最后一行的下一行即可输出答案

三、判断是否合法(两种方法通用)

我们采用bool 数组来表示当前行列对角线是否使用，1表示用过了，0表示还没有用

行列的写法是易懂的，直接用$y = x$的映射函数就可以了。这里分析下对角线（主对角线）与反对角线（副对角线）
我们需要将每一根对角线与反对角线唯一的表示，对角线和反对角线有$2 * n - 1$条，我们考虑用截距来表示它

对角线（左上到右下），由初中数学得$y = - x + b$，截距$b = x + y$

反对角线，$y = x + b$， $b = y - x$，但是这样$b$会出现负数，这在数组里是不允许的，我们给它加上一个偏移量$n$就可以将它们一一映射到$0$ ~ $(2 * n - 1)$的范围了

这里我们只需要将每一个条件与判重数组一一映射即可，并没有其他的特殊要求

这里放置皇后到下一次新的状态时，我们需要恢复现场，因为8 * 8 的图放到参数保存是不太现实的，比较大，浪费时间与空间

代码

按格子枚举

#include <iostream>

using namespace std;

const int N = 10;

int n;
bool row[N], col[N], dg[N * 2], udg[N * 2]; // 判重数组
char g[N][N];

void dfs(int x, int y, int s)
{
    if (s > n) return; // 如果当前放置皇后大于n则返回，其实这个条件很明显是错的，删除也可以ac
    if (y == n) y = 0, x ++ ; // 换行小技巧

    if (x == n) // 当枚举到最后一行的下一行的第一个格子时，就是枚举完了
    {
        if (s == n) // 皇后数量够了就输出答案
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    g[x][y] = '.'; // 该点不放皇后
    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) // 合法性判断
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q'; // 放皇后
        dfs(x, y + 1, s + 1);
        g[x][y] = '.'; // 回溯，恢复现场
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    cin >> n;

    dfs(0, 0, 0); // 初始状态是(0, 0)点，0个黄喉 

    return 0;
}

按行枚举

#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]);
        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] = 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); // 从第0行开始枚举

    return 0;
}