問題描述
給定一個 9x9 的數獨棋盤，請驗證這個棋盤是否有效。
數獨棋盤需滿足以下條件：- 每一行只能包含數字
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"]]
輸出：true
範例 2
輸入：
board =
[["8","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"]]
輸出：false
解釋：第一列有兩個 8，因此這個棋盤是無效的。
解法一：使用集合檢查每一行、每一列和每個子方格
思路
我們可以將數獨棋盤視為三部分來驗證：
- 每一行是否有重複數字。
- 每一列是否有重複數字。
- 每一個 3x3 子方格是否有重複數字。
對於每部分，我們可以使用 集合 來檢查是否有重複數字：
- 如果某數字已經存在於集合中，則表示有重複，棋盤無效。
- 如果某位置是
'.'，則忽略。
程式碼
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
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):
num = board[i][j]
if num == '.':
continue
# 檢查行
if num in rows[i]:
return False
rows[i].add(num)
# 檢查列
if num in cols[j]:
return False
cols[j].add(num)
# 檢查子方格
box_index = (i // 3) * 3 + (j // 3)
if num in boxes[box_index]:
return False
boxes[box_index].add(num)
return True
時間與空間複雜度
- 時間複雜度：O(1)
數獨棋盤大小固定為 9x9，因此無論如何最多遍歷 81 個格子，時間複雜度為常數。 - 空間複雜度：O(1)
使用了三個長度為 9 的集合來存儲行、列和子方格的數字，總空間需求固定。
解法二：壓縮空間版本
思路
我們可以用 唯一標識符 來壓縮存儲需求，僅用一個集合來記錄每個數字是否出現過。
- 將每個數字出現的條件轉化為字串標識，例如：
- 數字
5出現在第 0 行，標識為"5 in row 0"。 - 數字
5出現在第 1 列，標識為"5 in col 1"。 - 數字
5出現在子方格 (0,0)，標識為"5 in box 0-0"。
- 數字
- 將這些標識存入集合，如果發現重複標識則返回
False。
程式碼
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
seen = set()
for i in range(9):
for j in range(9):
num = board[i][j]
if num == '.':
continue
row_key = f"{num} in row {i}"
col_key = f"{num} in col {j}"
box_key = f"{num} in box {i//3}-{j//3}"
if row_key in seen or col_key in seen or box_key in seen:
return False
seen.add(row_key)
seen.add(col_key)
seen.add(box_key)
return True
時間與空間複雜度
- 時間複雜度：O(1)
同樣固定遍歷 81 個格子。 - 空間複雜度：O(1)
由於最多存儲 81 條標識（每個數字最多三條標識），空間需求仍然是固定的。
解法三：逐步檢查行、列、子方格
思路
- 檢查每一行：將每一行的數字存入集合，檢查是否有重複。
- 檢查每一列：同樣將每一列的數字存入集合，檢查是否有重複。
- 檢查每個子方格：對每個子方格中的數字進行檢查。
這種方法較為直觀，分開處理每部分。
程式碼
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
def isValidSet(values):
nums = [v for v in values if v != '.']
return len(nums) == len(set(nums))
# 檢查行
for row in board:
if not isValidSet(row):
return False
# 檢查列
for col in zip(*board):
if not isValidSet(col):
return False
# 檢查子方格
for i in range(0, 9, 3):
for j in range(0, 9, 3):
box = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
if not isValidSet(box):
return False
return True
時間與空間複雜度
- 時間複雜度：O(1)
固定遍歷 81 個格子，且每次檢查集合操作為常數時間。 - 空間複雜度：O(1)
每次檢查時僅臨時存儲數字，無額外存儲需求。
結論
- 最佳解法：解法二（壓縮空間版本），僅用一個集合，實現簡潔且高效。
- 其他解法：對於初學者，解法一 和 解法三 更容易理解。
- 此題重點在於如何高效檢查每一行、每一列與每個子方格是否符合規範，並通過集合實現唯一性檢查。
