有效的數(shù)獨(dú)

題目描述：

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

1. 數(shù)字 1-9 在每一行只能出現(xiàn)一次。

2. 數(shù)字 1-9 在每一列只能出現(xiàn)一次。

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

image

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

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

說(shuō)明:

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

解題思路：

主要是利用多層循環(huán)判斷，判斷矩陣是否一一滿足題目條件

• 首先先將9x9矩陣中的.轉(zhuǎn)換為數(shù)字0,然后利用多層循環(huán)來(lái)判斷是否滿足條件

• 第一層是判斷每一行和每一列是否滿足條件，判斷在同一行是否出現(xiàn)兩個(gè)相同的值，（if column != j and board[i][j] == board[i][column]）；同理，判斷在同一列是否出現(xiàn)兩個(gè)相同的值，（if row != i and board[i][j] == board[row][j]）

• 第二層是判斷在每一個(gè)3x3小格內(nèi)是否能滿足要求，首先，每3x3小格的范圍可以通過(guò)range((i // 3) * 3, (i // 3) * 3 + 3)來(lái)獲得，然后判斷在3x3小格內(nèi)是否出現(xiàn)在不同位置卻相同的值（if row != i and col != j and board[i][j] == board[row][col]）

• 如果上述條件都滿足，返回True，只要有一個(gè)不滿足，就返回False

Python源碼：

class Solution:
    def isValidSudoku(self, board: 'List[List[str]]') -> 'bool':
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    board[i][j] = 0

        for i in range(9):
            for j in range(9):
                if board[i][j] != 0:
                    for column in range(9):
                        if column != j and board[i][j] == board[i][column]:
                            return False
                    for row in range(9):
                        if row != i and board[i][j] == board[row][j]:
                            return False
                    for row in range((i // 3) * 3, (i // 3) * 3 + 3):
                        for col in range((j // 3) * 3, (j // 3) * 3 + 3):
                            if row != i and col != j and board[i][j] == board[row][col]:
                                return False
        return True
        

歡迎關(guān)注我的github：https://github.com/UESTCYangHR