52. N Queens II

Hard

Description

N 皇后問題：在 n x n 的棋盤上放置 n 個皇后，使得任意兩個皇后不能互相攻擊（不同行、不同列、不同對角線）。回傳解的數量。

Example:

Input: n = 4 Output: 2

Intuition#

核心思路：與 51. N-Queens 相同的回溯，但只計數不需要記錄棋盤。

每行放一個皇后，用回溯嘗試每列
用三個 Set（或 bitmask）追蹤被攻擊的列、主對角線、副對角線
因為只需計數，不需要建構棋盤，程式碼更簡潔

Approaches#

1: 回溯 + HashSet#

概念: 逐行放置皇后，用 HashSet 記錄被佔用的列和對角線
時間複雜度: O(n!) - 每行的可選列逐步減少
空間複雜度: O(n)

class Solution {
    fun totalNQueens(n: Int): Int {
        val cols = mutableSetOf<Int>()
        val diag1 = mutableSetOf<Int>()  // row - col
        val diag2 = mutableSetOf<Int>()  // row + col
        var count = 0

        fun backtrack(row: Int) {
            if (row == n) {
                count++
                return
            }

            for (col in 0 until n) {
                if (col in cols || (row - col) in diag1 || (row + col) in diag2) {
                    continue
                }

                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                backtrack(row + 1)

                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
            }
        }

        backtrack(0)
        return count
    }
}

⭐2: 回溯 + Bitmask#

概念: 用三個整數的位元表示佔用狀態，位元運算比 HashSet 更快
時間複雜度: O(n!)
空間複雜度: O(n) - 遞迴深度

class Solution {
    fun totalNQueens(n: Int): Int {
        var count = 0

        fun backtrack(row: Int, cols: Int, diag1: Int, diag2: Int) {
            if (row == n) {
                count++
                return
            }

            // 可用位置 = 所有位置 - 被攻擊的位置
            var available = ((1 shl n) - 1) and (cols or diag1 or diag2).inv()

            while (available != 0) {
                // 取最低位的 1（lowbit trick）
                val pos = available and (-available)
                available = available xor pos

                backtrack(
                    row + 1,
                    cols or pos,
                    (diag1 or pos) shl 1,
                    (diag2 or pos) shr 1
                )
            }
        }

        backtrack(0, 0, 0, 0)
        return count
    }
}

🔑 Takeaways#

Pattern: N 皇后 → 逐行回溯 + 列 / 對角線衝突檢測
關鍵技巧: Bitmask 方式用 lowbit = x & (-x) 逐一枚舉可用位置；主對角線往左移、副對角線往右移來傳遞攻擊範圍；與 51. N-Queens 的差異僅在於只計數不需記錄解