51. N-Queens

Hard

Description

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

Example:

Input: n = 4 Output: [[".Q..","…Q",“Q…”,"..Q."],["..Q.",“Q…”,"…Q",".Q.."]]

Intuition#

核心思路：逐行放置皇后，用集合記錄已佔用的列和對角線，回溯搜尋所有合法配置。

每一行恰好放一個皇后（保證不同行）
需要檢查：不同列、不同主對角線（row - col 相同）、不同副對角線（row + col 相同）
用三個 Set 分別追蹤已佔用的列、主對角線、副對角線

Approaches#

1: Backtracking + 逐格檢查#

概念: 逐行放皇后，每次放置後檢查是否與之前所有皇后衝突
時間複雜度: O(n!) - 第一行 n 種、第二行最多 n-1 種 …
空間複雜度: O(n^2) - 棋盤

class Solution {
    fun solveNQueens(n: Int): List<List<String>> {
        val result = mutableListOf<List<String>>()
        val board = Array(n) { CharArray(n) { '.' } }

        fun isValid(row: Int, col: Int): Boolean {
            for (r in 0 until row) {
                if (board[r][col] == 'Q') return false
                if (col - (row - r) >= 0 && board[r][col - (row - r)] == 'Q') return false
                if (col + (row - r) < n && board[r][col + (row - r)] == 'Q') return false
            }
            return true
        }

        fun backtrack(row: Int) {
            if (row == n) {
                result.add(board.map { String(it) })
                return
            }
            for (col in 0 until n) {
                if (isValid(row, col)) {
                    board[row][col] = 'Q'
                    backtrack(row + 1)
                    board[row][col] = '.'
                }
            }
        }

        backtrack(0)
        return result
    }
}

⭐2: Backtracking + Set 追蹤（O(1) 衝突判斷）#

概念: 用三個 HashSet 分別追蹤已佔用的列（col）、主對角線（row - col）、副對角線（row + col），O(1) 判斷衝突
時間複雜度: O(n!)
空間複雜度: O(n) - 三個 Set 各最多 n 個元素

class Solution {
    fun solveNQueens(n: Int): List<List<String>> {
        val result = mutableListOf<List<String>>()
        val board = Array(n) { CharArray(n) { '.' } }
        val cols = HashSet<Int>()
        val diag1 = HashSet<Int>()  // row - col (主對角線)
        val diag2 = HashSet<Int>()  // row + col (副對角線)

        fun backtrack(row: Int) {
            if (row == n) {
                result.add(board.map { String(it) })
                return
            }

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

                board[row][col] = 'Q'
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                backtrack(row + 1)

                board[row][col] = '.'
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
            }
        }

        backtrack(0)
        return result
    }
}

補充：對角線判斷的數學原理

在 n x n 棋盤上：

同一列: col 值相同
主對角線（左上到右下）: row - col 值相同，因為沿對角線走一步 row+1, col+1，差值不變
副對角線（右上到左下）: row + col 值相同，因為沿對角線走一步 row+1, col-1，和值不變

所以只需要三個 Set 就能 O(1) 判斷任意位置是否安全。

🔑 Takeaways#

Pattern: 約束滿足問題（CSP）用回溯法搜尋，配合高效的衝突檢查來剪枝
關鍵技巧: 用 row - col 和 row + col 表示兩條對角線，是棋盤問題中的經典技巧；Set 追蹤將衝突判斷從 O(n) 降到 O(1)