LeetCode N-Queens：經典回溯算法完整解析

問題描述

在 n×n 棋盤上放置 n 個皇后，使其互不攻擊（不同行、列、對角線）。返回所有合法擺放方案。

核心思想：逐行遞歸 + 合法性剪枝

• 每行恰好放一個皇后，遞歸處理第 row 行
• 用一維數組 col[row] 記錄該行皇后所在列
• 嘗試每列，檢查與前 row-1 行是否衝突
• 合法則遞歸下一行；row == n 時找到一個解

合法性檢查

新皇后 (row, col[row]) 與舊皇后 (i, col[i])：

• 同列：col[row] == col[i]
• 主對角線：row - col[row] == i - col[i] → |col[row]-col[i]| == row-i
• 副對角線：row + col[row] == i + col[i] → 同樣由絕對值判斷

Java 參考實現

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    backtrack(n, 0, new int[n], res);
    return res;
}

void backtrack(int n, int row, int[] col, List<List<String>> res) {
    if (row == n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; ++j)
                sb.append(col[i] == j ? 'Q' : '.');
            board.add(sb.toString());
        }
        res.add(board);
        return;
    }
    for (int c = 0; c < n; ++c) {
        col[row] = c;
        if (valid(row, col))
            backtrack(n, row + 1, col, res);
    }
}

boolean valid(int row, int[] col) {
    for (int i = 0; i < row; ++i)
        if (col[row] == col[i] || Math.abs(col[row] - col[i]) == row - i)
            return false;
    return true;
}

通用回溯模板

void backtrack(State state) {
    if (isSolution(state)) { save(state); return; }
    for (Choice c : getChoices(state)) {
        if (isValid(state, c)) {
            apply(state, c);
            backtrack(state);
            undo(state, c);  // 一維數組無需撤銷，蓋寫即可
        }
    }
}

舉一反三

此模板適用於：

• Sudoku Solver（數獨）
• Combination Sum / Combinations（組合問題）
• Permutations（全排列）
• 所有 NP 問題的精確解搜索