LeetCode - Valid Sudoku（判斷有效的數獨）

題目描述

給定一個 9 x 9 的數獨板 board，判斷該數獨是否有效。數獨僅需要滿足以下條件：

1. 每行只能包含數字 1-9，每個數字只能出現一次。
2. 每列只能包含數字 1-9，每個數字只能出現一次。
3. 每個 3 x 3 的小方塊只能包含數字 1-9，每個數字只能出現一次。

注意：

• 數獨板中的空白格用 '.' 表示。

範例：

輸入：
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

解法思路

為了驗證數獨的合法性，可以通過檢查以下三個條件來確認數獨是否有效：

1. 行檢查：確認每一行中數字 1-9 是否有重複。
2. 列檢查：確認每一列中數字 1-9 是否有重複。
3. 小方塊檢查：確認每個 3 x 3 小方塊中數字 1-9 是否有重複。

可以分別使用集合（set）來檢查上述條件，利用集合的唯一性判斷每個數字是否重複出現。

步驟

1. 使用三個集合數組：
   • rows：記錄每一行中已經出現過的數字。
   • cols：記錄每一列中已經出現過的數字。
   • boxes：記錄每個 3 x 3 小方塊中已經出現過的數字。
2. 遍歷整個數獨板 board，針對每個數字執行以下操作：
   • 如果當前位置為 '.'，則跳過。
   • 否則，根據數字 num 的位置 (i, j)：
     • 檢查 num 是否已在該行 i、列 j、或小方塊中出現過。
     • 若出現重複，則返回 False。
     • 若無重複，將 num 加入相應的行、列和小方塊的集合中。
3. 遍歷完所有數字後若無重複，返回 True。

範例代碼

以下是 Python 的實現：

def isValidSudoku(board):
    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
            if num in cols[j]:
                return False
            box_index = (i // 3) * 3 + (j // 3)
            if num in boxes[box_index]:
                return False
            
            # 將數字加入集合中
            rows[i].add(num)
            cols[j].add(num)
            boxes[box_index].add(num)
    
    return True

代碼解析

1. 創建三個大小為 9 的集合數組，分別記錄行、列和小方塊中的數字。
2. 遍歷 board，針對每個數字：
   • 計算該數字所在的 3 x 3 小方塊索引 box_index = (i // 3) * 3 + (j // 3)。
   • 檢查數字 num 是否已在行、列或小方塊集合中出現，若已出現則返回 False。
   • 若未出現，將數字加入相應的集合。
3. 最後，若檢查無誤，則返回 True。

時間和空間複雜度

• 時間複雜度：O(1)，因為數獨板固定為 9 x 9，即最多檢查 81 個元素。
• 空間複雜度：O(1)，使用固定大小的 27 個集合（9 行 + 9 列 + 9 小方塊）。