題目網址：https://leetcode.cn/problems/n-queens/

題意：按照國際象棋的規則, 皇后可以攻擊處於同一行 or 同一列 or 同一斜線上的棋子。

n-queens 問題是研究如何將 n 個皇后放在 n x n 的棋盤上, 並使皇后們之間不能互相攻擊。

給一整數 n, 返回所有不同的 n-queens 問題的解法, 可以任意順序返回。

每一種解法包含一種放置棋子的方式, 其中 'Q' 和 '.' 分別代表皇后跟空格。

Solution：

想法：利用 DFS + Backtracking, 單一格之兩條對角線可用公式表示

  • 對角線1：f(x) = x + y, 範圍：[0, 2n - 2] ➔ 總共 2n - 1 條

  • 對角線2：f(x) = x - y, 範圍：[-(n - 1), (n - 1)] ➔ 因為 vector 的 idx 從 0 開始, 所以要將範圍由 [-(n - 1), (n - 1)] 轉為 [0, 2n - 2] ➔ 得新公式：f(x) = x - y + (n - 1)

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        board.resize(n, string(n, '.'));
        col.resize(n, 0); // col 是否被占用
        diag1.resize(2 * n - 1, 0); // 正對角線是否被占用
        diag2.resize(2 * n - 1, 0); // 負對角線是否被占用
        dfs(0, n);
        return res;
    }

private:
    vector<vector<string>> res;
    vector<bool> col, diag1, diag2;
    vector<string> board;

    // 判斷 col 和兩條對角線上是否有衝突
    bool isValid(const int x, const int& y, const int n){
        // 只有在同 col 和兩條對角線都不衝突的情況下才能放
        return !col[x] && !diag1[x + y] && !diag2[x - y + n - 1];
    }

    void updateBoard(const int x, const int y, const int n, const bool status){
        col[x] = status;
        diag1[x + y] = status;
        diag2[x - y + n - 1] = status;
        board[y][x] = status ? 'Q' : '.';
    }

    // y 為 row
    void dfs(const int y, const int n){
        if (y == n) {
            res.emplace_back(board);
            return;
        }

        // 在同一 row 中嘗試各個 col
        for (int x = 0; x < n; ++x) {
            if (!isValid(x, y, n)) {
                continue;
            }

            updateBoard(x, y, n, true);
            dfs(y + 1, n);
            updateBoard(x, y, n, false);
        }
    }
};
  • time：$O(n!)$ ➔ 第一列最多有 n 種選擇, 而第二列最多有 n - 1 種選擇, 依此類推…
  • space：$O(n)$ ➔ 若不考慮 board 和要返回的 res, 則取決於遞迴深度, 遞迴深度不超過 n