[leetcode] 36. Valid Sudoku Pyth

很不幸，当时研究生入学考试一模一样的题，这次居然还不会，hash table标签的题练得太少，还得加油刷。

36. Valid Sudoku(Medium)

题目描述：合法的数独

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
简单的说就是一个给定一个9x9的矩阵，判定其是不是合法的数独，
每一行只能包含1-9的数字且不能重复，
每一列只能包含1-9的数字且不能重复，
每个3x3的子矩阵只能包含1-9的数字且不能重复，
数独矩阵可以部分填满，空的部分用'.'来表示

思路：

把每一个单元行，单元列和单位3x3 单独存入一个等长的二位数组之中，三个矩阵分别检查三个规则是否有重复数字，初始值为False，一旦计算过则列为True，再次检测到则函数返回False。关键点在于3x3的矩阵可以用i/3*3 + j/3来表示。

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row    = [[False]*9 for _ in range(9)]
        column = [[False]*9 for _ in range(9)]
        matrix = [[False]*9 for _ in range(9)]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] != '.':
                    k = i/3*3 + j/3
                    num = int(board[i][j]) - 1
                    if row[j][num] or column[i][num] or matrix[k][num]:
                        return False
                    row[j][num] = column[i][num] = matrix[k][num] = True
        return True