判斷一個 9x9 的數(shù)獨是否有效。只需要根據(jù)以下規(guī)則，驗證已經(jīng)填入的數(shù)字是否有效即可。

1. 數(shù)字 1-9 在每一行只能出現(xiàn)一次。
2. 數(shù)字 1-9 在每一列只能出現(xiàn)一次。
3. 數(shù)字 1-9 在每一個以粗實線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

image

上圖是一個部分填充的有效的數(shù)獨。

數(shù)獨部分空格內(nèi)已填入了數(shù)字，空白格用 '.' 表示。

示例 1:

輸入:
[
["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:

輸入:
[
["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
解釋: 除了第一行的第一個數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與 示例1 相同。
但由于位于左上角的 3x3 宮內(nèi)有兩個 8 存在, 因此這個數(shù)獨是無效的。

說明:

• 一個有效的數(shù)獨（部分已被填充）不一定是可解的。
• 只需要根據(jù)以上規(guī)則，驗證已經(jīng)填入的數(shù)字是否有效即可。
• 給定數(shù)獨序列只包含數(shù)字 1-9 和字符 '.' 。
• 給定數(shù)獨永遠是 9x9 形式的。

思路:

1. 判斷行和列是否有重復(fù)值，按一行和一列同時循環(huán)，分別判斷2個值當(dāng)前值是否在行字典內(nèi)，或者是否在列字典內(nèi)，如圖，逐行掃描完整個表。

2. 把表劃成9個宮，每個宮內(nèi)掃描是否有重復(fù)值。

   
   
   Image.png

class Solution:
    def isValidSudoku(self, board):
        # 先判斷行和列是否有重復(fù)數(shù)字，向后進行判斷，判斷過的不再判斷
        for x in range(9):
            row_dic = {}
            col_dic = {}
            for y in range(9):
                if board[x][y] != '.':
                    if board[x][y] in row_dic or board[x][y] < '1' or board[x][y] > '9':
                        return False
                    row_dic[board[x][y]] = 1
                if board[y][x] != '.':
                    if board[y][x] in col_dic or board[y][x] < '1' or board[y][x] > '9':
                        return False
                    col_dic[board[y][x]] = 1
        # 分成9個區(qū)域進行處理，每個區(qū)域單獨判斷
        coordinate = [(i, j) for i in range(0, 9, 3) for j in range(0, 9, 3)]
        for i, j in coordinate:
            cell_dic = {}
            for x in range(3):
                for y in range(3):
                    x_move = i + x
                    y_move = j + y
                    if board[x_move][y_move] != '.':
                        if board[x_move][y_move] in cell_dic or board[x_move][y_move] < '1' or board[x_move][y_move] > '9':
                            return False
                        cell_dic[board[x_move][y_move]] = 1

        return True


su = Solution()
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"]
]
res = su.isValidSudoku(board)
print(res)