[LeetCode解題攻略] 51. N-Queens

題目描述

51. N-Queens 是一個經典的演算法題目，要求在 n x n 的棋盤上放置 n 個皇后，並且保證它們之間不會互相攻擊。皇后可以攻擊任意與它處於同一行、同一列或同一對角線的其他棋子，因此我們需要找到所有合法的放置方式，並返回所有解。

題目要求

• 輸入：一個整數 n，表示棋盤的大小（即 n x n 的棋盤）。
• 輸出：所有可能的放置方式，每種方式應以 n 個字符串的列表表示，每個字符串的長度為 n，並且字符 Q 表示皇后，字符 . 表示空格。

範例

範例 1

輸入：n = 4
輸出：
[
  [".Q..",  // 解 1
   "...Q",
   "Q...",
   "..Q."],
   
  ["..Q.",  // 解 2
   "Q...",
   "...Q",
   ".Q.."]
]

範例 2

輸入：n = 1
輸出：
[
  ["Q"]
]

解題思路

關鍵觀念：

1. 行與列：每一行只能放置一個皇后，這樣可以保證不會有皇后處於同一行。
2. 對角線：每個皇后有兩條對角線，這些對角線必須避免與其他皇后重疊。
3. 回溯法：我們使用回溯法來不斷嘗試放置每一行的皇后，並且在每一次嘗試後進行合法性檢查。如果不合法，就回到上一步重新嘗試。

解法一：回溯法

思路：

1. 我們使用一個長度為 n 的數組 board，其中 board[i] 表示第 i 行放置的皇后所處的列數。
2. 每次嘗試放置一個皇后時，我們檢查是否會與前面的皇后攻擊，這就是回溯的核心。
3. 一旦我們成功放置了 n 個皇后，就找到了一个解。

程式碼實作：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def is_valid(board, row, col):
            for i in range(row):
                # 檢查是否在同一列或者對角線上
                if board[i] == col or abs(board[i] - col) == abs(i - row):
                    return False
            return True

        def backtrack(board, row):
            if row == n:
                result.append(["." * i + "Q" + "." * (n - i - 1) for i in board])
                return
            for col in range(n):
                if is_valid(board, row, col):
                    board[row] = col
                    backtrack(board, row + 1)
                    board[row] = -1  # Backtrack

        result = []
        board = [-1] * n  # 初始化棋盤
        backtrack(board, 0)
        return result

程式碼說明：

• is_valid(board, row, col)：這個函數用來檢查在第 row 行第 col 列放置皇后是否合法。它會檢查該列是否已經有皇后，還會檢查對角線的衝突。
• backtrack(board, row)：回溯的核心函數。它逐行放置皇后，每放置一個皇后就檢查是否合法。如果成功放置 n 個皇后，將當前棋盤的解加入 result。如果放置過程中發現衝突，則進行回溯。
• result：存儲所有合法的棋盤配置，並以字符串的形式輸出。

時間與空間複雜度：

• 時間複雜度：最壞情況下，對於每一行，我們都有 n 個可能的位置來嘗試放置皇后，且每次檢查是否合法是 O(n)。因此時間複雜度是 O(n!)。
• 空間複雜度：由於我們使用回溯法，空間複雜度是 O(n)，主要來自於遞歸的調用堆疊。

解法二：剪枝優化

在解法一中，我們檢查每一列和對角線是否有衝突。這個檢查是逐一進行的，效率並不高。我們可以進一步優化，通過三個集合來追蹤列和兩條對角線的佔用情況。

程式碼實作：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(row):
            if row == n:
                result.append(["." * col + "Q" + "." * (n - col - 1) for col in board])
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row] = col
                backtrack(row + 1)
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        result = []
        board = [-1] * n
        cols = set()
        diag1 = set()
        diag2 = set()
        backtrack(0)
        return result

程式碼說明：

• cols, diag1, diag2：這些集合用來記錄被佔用的列和對角線，從而避免重複檢查每個位置。
• 這種方法減少了每次放置皇后時的檢查時間，使得算法更高效。

時間與空間複雜度：

• 時間複雜度：與回溯法相同，最壞情況下是 O(n!)，但由於優化了衝突檢查，實際情況會比解法一更好一點。
• 空間複雜度：空間複雜度是 O(n)，來自於遞歸調用堆疊及存儲已經佔用的列和對角線集合。

結論

這道 N-Queens 題目是一個典型的回溯法問題，通過遞歸和回溯來嘗試不同的解，並檢查合法性。這題可以幫助大家更好地理解回溯法的使用，並且能夠進一步掌握如何進行優化。回溯法的解法雖然直觀，但是在大規模數據上依然有效，對於許多組合問題有廣泛應用。