遊戲模擬題: Valid Sudoku 驗證是否為合法Sudoku輸入_Leetcode #36

Bozhin Karaivanov on Unsplash

題目敘述 Valid Sudoku

給定一個9x9的輸入陣列代表數獨題目已經 部分作答 的狀態，

請驗證已經作答的部分是否為合法的Sudoku的輸入。

註:

合法的Sudoku輸入必須滿足這些規則

1~9每一直排恰好出現一次。

1~9每一橫排恰好出現一次。

1~9在3x3的小方陣裏面也恰好出現一次。

只要其中一個規則被打破，則是非法的Sudoku輸入，返回False

否則，返回True

測試範例

Example 1:

Input: 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"]]
Output: true

已作答的部分都滿足Sudoku的規則。​

Example 2:

Input: 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"]]
Output: false
Explanation:

左上角那個3x3的方陣裡
8重複出現兩次，違反Sudoku的規定​

約束條件

Constraints:

• board.length == 9

輸入陣列的高一定是9

• board[i].length == 9

輸入陣列的寬一定是9

• board[i][j] is a digit 1-9 or '.'.

輸入陣列裡面只會有1~9或者 . (代表尚未作答的格子點)

演算法 檢查已作答部分是否符合Sudoku規則

針對整個9x9的輸入陣列進行檢查

已作答的部分必須滿足下列Sudoku規則:

1~9每一直排恰好出現一次。

1~9每一橫排恰好出現一次。

1~9在3x3的小方陣裏面也恰好出現一次。

只要其中一個規則被打破，則是非法的Sudoku輸入，返回False

否則，返回True

程式碼 檢查已作答部分是否符合Sudoku規則

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # Row flag for 1~9
        row_flag = [[False for i in range(9)] for j in range(9)]
        
        # Column flag for 1~9
        col_flag = [[False for i in range(9)] for j in range(9)]
        
        # 3x3 sub-block flag for 1~9
        block_flag = [[False for i in range(9)] for j in range(9)]
        
        for i in range(9):
            for j in range(9):
                
                if board[i][j] != '.':
                    
                    # get current number
                    num = int(board[i][j]) - 1

                    # compute index of 3x3 sub-block
                    k = (i//3)*3 + j//3
                    
                    # Reject if there is number repeated in row, column or 3x3 sub-block
                    if row_flag[i][num] or col_flag[j][num] or block_flag[k][num]:
                        return False
                    
                    # update row flag, column flag, 3x3 sub-block flag for current number
                    row_flag[i][num] = col_flag[j][num] = block_flag[k][num] = True
                    
        return True

複雜度分析

時間複雜度: O(9 * 9) = O(1)

針對整個9x9輸入矩陣做檢查，耗時O(81) = O(1)

空間複雜度: O(9 * 9) = O(1)

針對每一個橫排、直排、3x3小方陣 檢查1~9是否恰好存在一次的布林陣列，所需空間為O(81) = O(1)

Reference:

[1] Valid Sudoku - LeetCode