N-皇后问题

30 Aug 2024 in Algorithm Pageviews

dfs algorithm

一道经典DFS算法，从8皇后到n皇后问题

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

输入格式：共一行，包含整数 n, 数据范围 1 <= n <= 9

输出格式：

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空，用 Q 表示某一个位置上的方格上摆放皇后，每个方案输出完成后，输出一个空行。

注意：行末不能有多余的空格。输出方案的顺序是任意的，没有遗漏即可。

输入样例:

4

输出样例：

---

. Q . . . . Q .

. . . Q Q . . .

Q . . . . . . Q

. . Q . . Q . .

---

代码实现如下:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    void BackTrack(vector<string> &board, int x)
    {
        int n = board.size();
        if (x == n) {
            res.emplace_back(board);
            return;
        }
        
        for (int y = 0; y < n; y++) {
            if (st[y] || dg[y + x] || ug[y - x + n]) {
                continue;
            }
            
            st[y] = dg[y + x] = ug[y - x + n] = true;
            board[x][y] = 'Q';
            BackTrack(board, x + 1);
            board[x][y] = '.';
            st[y] = dg[y + x] = ug[y - x + n] = false;
        }
    }
    
    vector<vector<string>> SolveNQueens(int n)
    {
        vector<string> board(n, string(n, '.'));
        st.resize(20);
        dg.resize(20);
        ug.resize(20);
        BackTrack(board, 0);
        return res;
    }
    
private:
    vector<bool> st; // 是否已经访问过
    vector<bool> dg; // 正向不能同行
    vector<bool> ug; // 反向不能同行
    vector<vector<string>> res;
};