判斷一個(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

<small style="box-sizing: border-box; font-size: 12px;">上圖是一個(gè)部分填充的有效的數(shù)獨(dú)。</small>

數(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
</pre>

示例 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ú)效的。</pre>

說(shuō)明:

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

• 執(zhí)行用時(shí)為 44 ms 的范例

class Solution:
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        row = [set([]) for i in range(9)]
        col = [set([]) for i in range(9)]
        grid = [set([]) for i in range(9)]

        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    continue
                if board[r][c] in row[r]:
                    return False
                if board[r][c] in col[c]:
                    return False

                g = r / 3 * 3 + c / 3
                if board[r][c] in grid[g]:
                    return False
                grid[g].add(board[r][c])
                row[r].add(board[r][c])
                col[c].add(board[r][c])

        return True

• 執(zhí)行用時(shí)為 52 ms 的范例

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        s_row = [set() for i in range(9)]
        s_col = [set() for i in range(9)]
        s_box = [[set() for i in range(3)] for j in range(3)]
        
        for i in range(9):
            for j in range(9):
                item = board[i][j]
                if item != '.':
                    if item in s_row[i]:
                        return False
                    s_row[i].add(item)
                    if item in s_col[j]:
                        return False
                    s_col[j].add(item)
                    bi, bj = i/3, j/3
                    if item in s_box[bi][bj]:
                        return False
                    s_box[bi][bj].add(item)
        return True

• 執(zhí)行用時(shí)為 60 ms 的范例

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        for row in board:
            if not self.checkNums(row):
                return False
        
        for i in range(9):
            col = [board[j][i] for j in range(9)]
            if not self.checkNums(col):
                return False
        
        for i in range(0,9,3):
            for j in range(0,9,3):
                if not self.checkNode(row=i,col=j, board=board):
                    return False
        return True
        
    
    def checkNode(self, row=0, col=0, board=None):
        lyst = []
        for i in range(3):
            for j in range(3):
                lyst.append(board[row+i][col+j])
        return self.checkNums(lyst)
    
    
    def checkNums(self, lyst):
        null_cnt = lyst.count('.')
        m_set = set(lyst)
        if '.' in lyst:
            return len(m_set) - 1 + null_cnt == len(lyst)
        else:
            return len(m_set) == len(lyst)