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

題目描述

在 N-Queens 問題的基礎上，只需返回不同解法的總數，而不需要具體的棋盤佈局。

範例：

輸入: n = 8
輸出: 92

解題思路

核心邏輯與 N-Queens 完全相同，使用回溯 + 位掩碼（或布林陣列）記錄列、主對角線、副對角線是否被佔用。不同之處在於不需要構建字符串棋盤，只需一個計數器 count，每當成功放置第 n 個皇后（即 row == n）時，計數器加一。

1. 維護三個布林陣列：col、diag、anti_diag，大小分別為 n、2n、2n。
2. 遞歸函數 backtrack(row)：若 row == n，count++ 並返回。
3. 對當前行的每一列 col，檢查是否可放置；若可，標記三個陣列，遞歸下一行，回溯時取消標記。

參考代碼 (Python)

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.col = [False] * n
        self.diag = [False] * (2 * n)
        self.anti_diag = [False] * (2 * n)
        self.count = 0
        self.backtrack(0, n)
        return self.count

    def backtrack(self, row: int, n: int):
        if row == n:
            self.count += 1
            return
        for c in range(n):
            d = row + c
            ad = n - 1 + row - c  # 或 row - c + n - 1
            if not self.col[c] and not self.diag[d] and not self.anti_diag[ad]:
                self.col[c] = self.diag[d] = self.anti_diag[ad] = True
                self.backtrack(row + 1, n)
                self.col[c] = self.diag[d] = self.anti_diag[ad] = False

複雜度分析

• 時間複雜度：O(N!) —— 經典回溯上界。
• 空間複雜度：O(N) —— 遞歸棧深度 + 三個輔助陣列。