問題描述
編寫一個程式，求解數獨（Sudoku）問題。
數獨需要根據以下規則完成：
- 每一行只能包含數字
1-9，且不能重複。 - 每一列只能包含數字
1-9，且不能重複。 - 每一個 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-9填入這個位置，並檢查是否符合數獨規則。 - 如果符合，繼續檢查下一個空格；如果不符合，回退並嘗試下一個數字。
- 如果所有空格都被成功填充，則找到解。
- 如果嘗試所有數字後都無法填充當前空格，則回溯到上一個空格，並嘗試不同的數字。
程式碼
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)
解釋
is_valid函數：- 驗證某個數字是否可以填入指定位置。
- 檢查行、列、以及子方格。
backtrack函數：- 遍歷整個棋盤，找到第一個空格。
- 嘗試填入
1-9，並遞歸解決。 - 如果無法填入任何數字，回退到上一個空格並嘗試其他數字。
- 回溯步驟：
- 填入數字 → 檢查是否有效 → 遞歸到下一步。
- 如果當前步驟無法進一步完成，將數字清除並嘗試下一個數字。
時間與空間複雜度
- 時間複雜度：O(9^(n))，其中
n是空格數量。 - 每個空格最多嘗試 9 種數字，遞歸深度為空格數。
- 空間複雜度：O(n)，遞歸深度等於空格數。
解法二：優化回溯法
思路
我們可以通過額外的資料結構來加速檢查行、列和子方格是否有重複數字：
- 使用 3 個集合列表分別存儲每一行、每一列、以及每個子方格的數字。
- 當我們嘗試填入某個數字時，快速檢查集合是否包含該數字。
程式碼
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)
解釋
- 優化檢查：
- 將每行、每列、每個子方格的數字存入集合。
- 插入和檢查操作的時間複雜度為 O(1)。
- 回溯過程：
- 與解法一相同，但加入集合操作進行檢查，提升效率。
時間與空間複雜度
- 時間複雜度：O(9^(n))，其中
n是空格數量。 - 優化的檢查操作不改變回溯的總體複雜度。
- 空間複雜度：O(1)。
- 集合大小固定為棋盤大小。
結論
- 解法二通過使用集合加速檢查操作，使程式更高效且易於維護。
- 整體回溯法對於數獨問題表現優秀，適用於求解這類組合問題。
