C++N皇后問題

2023-09-20 09:23 更新

Question

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

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

4 皇后問題的解

圖 13-15   4 皇后問題的解

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

n 皇后問題的約束條件

圖 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è)格子滿足 row1?col1=row2?col2 ,則它們一定處在同一條主對角線上。利用該規(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ù)組 diag1diag2 的長度都為 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 次,考慮列約束,則從第一行到最后一行分別有 nn?1、、21 個(gè)選擇,因此時(shí)間復(fù)雜度為 O(n!) 。實(shí)際上,根據(jù)對角線約束的剪枝也能夠大幅地縮小搜索空間,因而搜索效率往往優(yōu)于以上時(shí)間復(fù)雜度。

數(shù)組 state 使用 O(n2) 空間,數(shù)組 colsdiags1diags2 皆使用 O(n) 空間。最大遞歸深度為 n ,使用 O(n) 棧幀空間。因此,空間復(fù)雜度為 O(n2) 。


以上內(nèi)容是否對您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號