[LeetCode解題攻略] 37. Sudoku Solver

問題描述

編寫一個程式，求解數獨（Sudoku）問題。

數獨需要根據以下規則完成：

1. 每一行只能包含數字 1-9，且不能重複。
2. 每一列只能包含數字 1-9，且不能重複。
3. 每一個 3x3 的子方格只能包含數字 1-9，且不能重複。

注意：

• 數獨棋盤中的空格由 '.' 表示。
• 必須就地修改數獨棋盤。

範例 1

輸入：
board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

輸出：
[["5","3","4","6","7","8","9","1","2"]
,["6","7","2","1","9","5","3","4","8"]
,["1","9","8","3","4","2","5","6","7"]
,["8","5","9","7","6","1","4","2","3"]
,["4","2","6","8","5","3","7","9","1"]
,["7","1","3","9","2","4","8","5","6"]
,["9","6","1","5","3","7","2","8","4"]
,["2","8","7","4","1","9","6","3","5"]
,["3","4","5","2","8","6","1","7","9"]]

解法一：回溯法

思路

回溯法（Backtracking），這是一種暴力解法。具體步驟如下：

1. 從棋盤的左上角開始，找到第一個空格（.）。
2. 嘗試將數字 1-9 填入這個位置，並檢查是否符合數獨規則。
3. 如果符合，繼續檢查下一個空格；如果不符合，回退並嘗試下一個數字。
4. 如果所有空格都被成功填充，則找到解。
5. 如果嘗試所有數字後都無法填充當前空格，則回溯到上一個空格，並嘗試不同的數字。

程式碼

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        def is_valid(board, row, col, num):
            num = str(num)
            # 檢查行
            for i in range(9):
                if board[row][i] == num:
                    return False
            # 檢查列
            for i in range(9):
                if board[i][col] == num:
                    return False
            # 檢查子方格
            box_row_start = (row // 3) * 3
            box_col_start = (col // 3) * 3
            for i in range(box_row_start, box_row_start + 3):
                for j in range(box_col_start, box_col_start + 3):
                    if board[i][j] == num:
                        return False
            return True

        def backtrack(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for num in range(1, 10):
                            if is_valid(board, i, j, num):
                                board[i][j] = str(num)
                                if backtrack(board):
                                    return True
                                # 回溯
                                board[i][j] = '.'
                        return False
            return True

        backtrack(board)

解釋

1. is_valid 函數：
2. • 驗證某個數字是否可以填入指定位置。
   • 檢查行、列、以及子方格。
2. backtrack 函數：
3. • 遍歷整個棋盤，找到第一個空格。
   • 嘗試填入 1-9，並遞歸解決。
   • 如果無法填入任何數字，回退到上一個空格並嘗試其他數字。
3. 回溯步驟：
4. • 填入數字 → 檢查是否有效 → 遞歸到下一步。
   • 如果當前步驟無法進一步完成，將數字清除並嘗試下一個數字。

時間與空間複雜度

• 時間複雜度：O(9^(n))，其中 n 是空格數量。
• • 每個空格最多嘗試 9 種數字，遞歸深度為空格數。
• 空間複雜度：O(n)，遞歸深度等於空格數。

解法二：優化回溯法

思路

我們可以通過額外的資料結構來加速檢查行、列和子方格是否有重複數字：

1. 使用 3 個集合列表分別存儲每一行、每一列、以及每個子方格的數字。
2. 當我們嘗試填入某個數字時，快速檢查集合是否包含該數字。

程式碼

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        # 初始化集合
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = board[i][j]
                    rows[i].add(num)
                    cols[j].add(num)
                    boxes[(i // 3) * 3 + j // 3].add(num)

        def backtrack(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for num in map(str, range(1, 10)):
                            box_index = (i // 3) * 3 + j // 3
                            if num not in rows[i] and num not in cols[j] and num not in boxes[box_index]:
                                # 填入數字
                                board[i][j] = num
                                rows[i].add(num)
                                cols[j].add(num)
                                boxes[box_index].add(num)

                                if backtrack(board):
                                    return True

                                # 回溯
                                board[i][j] = '.'
                                rows[i].remove(num)
                                cols[j].remove(num)
                                boxes[box_index].remove(num)
                        return False
            return True

        backtrack(board)

解釋

1. 優化檢查：
2. • 將每行、每列、每個子方格的數字存入集合。
   • 插入和檢查操作的時間複雜度為 O(1)。
2. 回溯過程：
3. • 與解法一相同，但加入集合操作進行檢查，提升效率。

時間與空間複雜度

• 時間複雜度：O(9^(n))，其中 n 是空格數量。
• • 優化的檢查操作不改變回溯的總體複雜度。
• 空間複雜度：O(1)。
• • 集合大小固定為棋盤大小。

結論

• 解法二通過使用集合加速檢查操作，使程式更高效且易於維護。
• 整體回溯法對於數獨問題表現優秀，適用於求解這類組合問題。