#J30902. n-皇后问题

题目描述

𝑛−n−皇后问题是指将 𝑛n 个皇后放在 𝑛×𝑛n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 𝑛n，请你输出所有满足条件的棋子摆法。

输入格式

共一行，包含一个整数 𝑛n。

输出格式

每个方案应该是一个 𝑛n 行 𝑛n 列的二维字符数组，其中 . 表示这个方格为空，Q 表示这个方格上摆着皇后。每输出完一个方案后，应该输出一个空行后再输出下一个方案。输出方案的顺序任意，只要不重复且没有遗漏即可。

思路

采用深度优先搜索（DFS）结合回溯的方法，从棋盘的第一行开始，逐行尝试在每一列放置皇后。在放置过程中，检查当前位置是否与之前已经放置的皇后冲突，如果不冲突则继续放置下一行的皇后；如果冲突则尝试当前行的下一列。当成功放置完 个皇后（即遍历完所有行），记录并输出当前的棋盘布局，然后回溯到上一行，继续尝试其他可能的放置位置，直到找出所有可行的方案。

完整代码

#include<bits/stdc++.h>
using namespace std;
int n, a[10];
// mp数组表示是否有皇后 
bool mp[10][10];
// 深度优先搜索，y 表示行号
void dfs(int y) {
    // 如果当前行号 y 大于 n，说明已经成功在 n 行都放置了皇后
    if (y > n) {
        // 遍历棋盘的每一行
        for (int i = 1; i <= n; i++) {
            // 遍历棋盘的每一列
            for (int j = 1; j <= n; j++) {
                // 如果该位置放置了皇后
                if (mp[i][j]) {
                    // 输出 'Q' 表示皇后
                    cout << 'Q';
                } else {
                    // 否则输出 '.' 表示空位
                    cout << '.';
                }
            }
            // 每行输出完后换行
            cout << endl;
        }
        // 每一种可行解输出完后，再换一行，以便区分不同的解
        cout << endl;
        return;
    }
    // 尝试在当前行的每一列放置皇后
    for (int i = 1; i <= n; i++) {
        // f用于标记当前列是否可以放置皇后，初始设为 true
        bool f = true;
        // 检查当前列是否与之前行的皇后冲突
        for (int j = 1; j <= y; j++) {
            // 如果在同一列，或者在同一斜线上，则冲突
            if (i == a[j] || i - y == a[j] - j || i + y == a[j] + j) {
                // 标记
                f = false;
                // 一旦发现冲突，就不需要再继续了
                break;
            }
        }
        // 如果可以放置
        if (f) {
            // 记录当前行的皇后所在的列号
            a[y] = i;
            // 标记该位置放置了皇后
            mp[a[y]][y] = true;
            // 递归调用dfs函数，继续放置下一行的皇后
            dfs(y + 1);
            // 回溯操作，将该位置的皇后移除
            mp[a[y]][y] = false;
            // 清除当前行皇后所在的列号记录
            a[y] = 0;
        }
    }
    return;
}
int main() {
    cin >> n;
    // 从第一行开始
    dfs(1);
    return 0;
}