ZeroJudge 解題筆記：i644. 列舉八皇后問題所有解

作者：王一哲
日期：2025年11月19日


ZeroJudge 題目連結：i644. 列舉八皇后問題所有解

解題想法

經典的題目，用函式遞迴及回溯比較好寫。

Python 程式碼

使用時間約為 9 ms，記憶體約為 3.1 MB，通過測試。

def solve_n_queens(n):  # 自訂函式，解 n 皇后問題
    # 回溯，代入目前的列，已用的欄、左上右下斜線、右上左下斜線
    def backtrack(row, cols, diag1, diag2):
        if row == n:  # 遞迴出口，填入第 n 列，找到一組解
            # 將 borad 儲存的欄與列組成 tuple，依照欄排序，存入 ans
            # 由 ans 取出列的順序，轉成字串，存入 solutions
            ans = sorted([(c, i) for i, c in enumerate(board, start=1)])
            solutions.append("".join([str(i) for _, i in ans]))
        for col in range(n):  # 依序測試第 0 ~ n-1 欄
            d1 = row - col  # 左上右下斜線
            d2 = row + col  # 右上左下斜線
            # 如果 col, d1, d2 不在已用的集合之中，可以用這個位置
            if col not in cols and d1 not in diag1 and d2 not in diag2:
                board[row] = col  # row 列使用的欄為 col
                # 遞迴，找下一列，代入原來的集合分別與 col, d1, d2 的聯集
                backtrack(row+1, cols | {col}, diag1 | {d1}, diag2 | {d2})
    # end of backtrack
    solutions = []  # 所有的解
    board = [-1]*n  # 第 row 列的皇后放在第 col 欄
    backtrack(0, set(), set(), set())  # 呼叫 backtrack 求解
    return solutions  # 回傳所有的解
# end of solve_n_queens
all_solutions = solve_n_queens(8)
all_solutions.sort()  # 依照字典排序
for i, sol in enumerate(all_solutions, start=1):
    print(f"{i:d}: {sol:s}")

C++ 程式碼

使用時間約為 1 ms，記憶體約為 316 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <string>
using namespace std;

vector<string> solutions;  // 所有的解
// 回溯，代入目前的列，已用的欄、左上右下斜線、右上左下斜線
void backtrack(int n, int row, vector<int>& board, unordered_set<int>& cols, unordered_set<int>& diag1, unordered_set<int>& diag2) {
    if (row == n) {  // 遞迴出口，填入第 n 列，找到一組解
        // 將 borad 儲存的欄與列組成 pair，依照欄排序，存入 ans
        // 由 ans 取出列的順序，轉成字串，存入 solutions
        vector<pair<int, int>> ans (n);
        for(int i=0; i<n; i++) ans[i] = make_pair(board[i], i+1);
        sort(ans.begin(), ans.end());
        string solution = "";
        for(auto it : ans) solution += char(it.second + '0');
        solutions.push_back(solution);
    }
    for(int col=0; col<n; col++) {  // 依序測試第 0 ~ n-1 欄
        int d1 = row - col, d2 = row + col;  // 左上右下斜線，右上左下斜線
        // 如果 col, d1, d2 不在已用的集合之中，可以用這個位置
        if (cols.count(col) == 0 && diag1.count(d1) == 0 && diag2.count(d2) == 0) {
            board[row] = col;  // row 列使用的欄為 col
            // 遞迴，找下一列，代入原來的集合分別與 col, d1, d2 的聯集
            cols.insert(col); diag1.insert(d1); diag2.insert(d2);
            backtrack(n, row+1, board, cols, diag1, diag2);
            cols.erase(col); diag1.erase(d1); diag2.erase(d2);  // 要手動移除 col, d1, d2
        }
    }
}

void solve_n_queens(int n) {  // 自訂函式，解 n 皇后問題
    vector<int> board (n, -1);  // 第 row 列的皇后放在第 col 欄
    unordered_set<int> cols, diag1, diag2;
    backtrack(n, 0, board, cols, diag1, diag2);  // 呼叫 backtrack 求解
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve_n_queens(8);
    sort(solutions.begin(), solutions.end());  // 依照字典排序
    int n = (int)solutions.size();
    for(int i=0; i<n; i++) cout << i+1 << ": " << solutions[i] << "\n";
    return 0;
}