C++N皇后問題

Question

根據(jù)國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。給定 $n$ 個(gè)皇后和一個(gè) $n\times n$ 大小的棋盤，尋找使得所有皇后之間無法相互攻擊的擺放方案。

如圖 13-15 所示，當(dāng) $n=4$ 時(shí)，共可以找到兩個(gè)解。從回溯算法的角度看，$n\times n$ 大小的棋盤共有 $n^2$ 個(gè)格子，給出了所有的選擇 choices 。在逐個(gè)放置皇后的過程中，棋盤狀態(tài)在不斷地變化，每個(gè)時(shí)刻的棋盤就是狀態(tài) state 。

圖 13-15   4 皇后問題的解

圖 13-16 展示了本題的三個(gè)約束條件：多個(gè)皇后不能在同一行、同一列、同一對角線。值得注意的是，對角線分為主對角線 \ 和次對角線 / 兩種。

圖 13-16   n 皇后問題的約束條件

1.   逐行放置策略

皇后的數(shù)量和棋盤的行數(shù)都為 $n$ ，因此我們?nèi)菀椎玫揭粋€(gè)推論：棋盤每行都允許且只允許放置一個(gè)皇后。

也就是說，我們可以采取逐行放置策略：從第一行開始，在每行放置一個(gè)皇后，直至最后一行結(jié)束。

如圖 13-17 所示，為 $4$ 皇后問題的逐行放置過程。受畫幅限制，圖 13-17 僅展開了第一行的其中一個(gè)搜索分支，并且將不滿足列約束和對角線約束的方案都進(jìn)行了剪枝。

圖 13-17   逐行放置策略

本質(zhì)上看，逐行放置策略起到了剪枝的作用，它避免了同一行出現(xiàn)多個(gè)皇后的所有搜索分支。

2.   列與對角線剪枝

為了滿足列約束，我們可以利用一個(gè)長度為 $n$ 的布爾型數(shù)組 cols 記錄每一列是否有皇后。在每次決定放置前，我們通過 cols 將已有皇后的列進(jìn)行剪枝，并在回溯中動(dòng)態(tài)更新 cols 的狀態(tài)。

那么，如何處理對角線約束呢？設(shè)棋盤中某個(gè)格子的行列索引為 $(row,col)$ ，選定矩陣中的某條主對角線，我們發(fā)現(xiàn)該對角線上所有格子的行索引減列索引都相等，即對角線上所有格子的 $row?col$ 為恒定值。

也就是說，如果兩個(gè)格子滿足 $ro{w}_1?co{l}_1=ro{w}_2?co{l}_2$ ，則它們一定處在同一條主對角線上。利用該規(guī)律，我們可以借助圖 13-18 所示的數(shù)組 diag1 ，記錄每條主對角線上是否有皇后。

同理，次對角線上的所有格子的 $row+col$ 是恒定值。我們同樣也可以借助數(shù)組 diag2 來處理次對角線約束。

圖 13-18   處理列約束和對角線約束

3.   代碼實(shí)現(xiàn)?

請注意，$n$ 維方陣中 $row?col$ 的范圍是 $[?n+1,n?1]$ ，$row+col$ 的范圍是 $[0,2n?2]$ ，所以主對角線和次對角線的數(shù)量都為 $2n?1$ ，即數(shù)組 diag1 和 diag2 的長度都為 $2n?1$ 。

n_queens.cpp

/* 回溯算法：N 皇后 */
void backtrack(int row, int n, vector<vector<string>> &state, vector<vector<vector<string>>> &res, vector<bool> &cols,
               vector<bool> &diags1, vector<bool> &diags2) {
    // 當(dāng)放置完所有行時(shí)，記錄解
    if (row == n) {
        res.push_back(state);
        return;
    }
    // 遍歷所有列
    for (int col = 0; col < n; col++) {
        // 計(jì)算該格子對應(yīng)的主對角線和副對角線
        int diag1 = row - col + n - 1;
        int diag2 = row + col;
        // 剪枝：不允許該格子所在列、主對角線、副對角線存在皇后
        if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
            // 嘗試：將皇后放置在該格子
            state[row][col] = "Q";
            cols[col] = diags1[diag1] = diags2[diag2] = true;
            // 放置下一行
            backtrack(row + 1, n, state, res, cols, diags1, diags2);
            // 回退：將該格子恢復(fù)為空位
            state[row][col] = "#";
            cols[col] = diags1[diag1] = diags2[diag2] = false;
        }
    }
}

/* 求解 N 皇后 */
vector<vector<vector<string>>> nQueens(int n) {
    // 初始化 n*n 大小的棋盤，其中 'Q' 代表皇后，'#' 代表空位
    vector<vector<string>> state(n, vector<string>(n, "#"));
    vector<bool> cols(n, false);           // 記錄列是否有皇后
    vector<bool> diags1(2 * n - 1, false); // 記錄主對角線是否有皇后
    vector<bool> diags2(2 * n - 1, false); // 記錄副對角線是否有皇后
    vector<vector<vector<string>>> res;

    backtrack(0, n, state, res, cols, diags1, diags2);

    return res;
}

逐行放置 $n$ 次，考慮列約束，則從第一行到最后一行分別有 $n$、$n?1$、$\dots$、$2$、$1$ 個(gè)選擇，因此時(shí)間復(fù)雜度為 $O(n!)$ 。實(shí)際上，根據(jù)對角線約束的剪枝也能夠大幅地縮小搜索空間，因而搜索效率往往優(yōu)于以上時(shí)間復(fù)雜度。

數(shù)組 state 使用 $O(n^2)$ 空間，數(shù)組 cols、diags1 和 diags2 皆使用 $O(n)$ 空間。最大遞歸深度為 $n$ ，使用 $O(n)$ 棧幀空間。因此，空間復(fù)雜度為 $O(n^2)$ 。