LeetCode 筆記：N-Queens II - 計算 N 皇后問題的不同解總數

一、題目描述

這是 N-Queens 問題的進階版。原題要求輸出所有合法的棋盤配置，而本題僅需返回 不同解的總數。給定一個 N×N 的棋盤，請計算有多少種方式可以放置 N 個皇后，使它們互不攻擊（即不在同一行、同一列、同一對角線上）。

二、題目分析

解法與經典 N-Queens 幾乎相同，但因為不需要記錄具體的棋盤佈局，程式碼大幅簡化。核心思路仍是 深度優先搜尋（DFS）配合回溯：逐行嘗試放置皇后，利用陣列標記已被佔用的列與對角線，當成功走到第 N 行（即所有皇后皆已放置）時，將全域計數器加一。由於不需輸出路徑，省去了字串操作與記憶體開銷，執行效率更高。

三、示例代碼 (C++)

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int totalNQueens(int n) {
        row.assign(n, 0);      // 記錄每行皇后所在的列索引
        col.assign(n, 0);      // 標記各列是否已有皇后
        result = 0;
        dfs(0, n);
        return result;
    }

private:
    int result;
    vector<int> row;
    vector<int> col;

    void dfs(int r, int n) {
        if (r == n) {          // 成功放置 N 個皇后
            ++result;
            return;
        }
        for (int c = 0; c < n; ++c) {
            if (col[c]) continue;               // 該列已被佔用
            bool conflict = false;
            for (int prev = 0; prev < r; ++prev) {
                if (abs(r - prev) == abs(c - row[prev])) { // 對角線衝突
                    conflict = true;
                    break;
                }
            }
            if (!conflict) {
                col[c] = 1;
                row[r] = c;
                dfs(r + 1, n);
                col[c] = 0;    // 回溯：撤銷標記
            }
        }
    }
};

四、小結

N-Queens II 將輸出需求從「所有解」降級為「解的個數」，使得程式碼更精簡、執行更快。這也是典型的「以空間換時間」或「裁剪輸出以提升效能」的實例。掌握此題有助於理解如何在回溯算法中只保留必要的狀態資訊。