首页 > itarticle > 036 valid sukodu

036 valid sukodu

admin 1月 11, 2021 0

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

思路

需要熟悉数独的规则，利用哈希表来进行判断。

数独的棋盘大小是一定的，不需要考虑时间的耗费，直接利用穷举法把所有情况列举出来，判断数独是否有效。

判断条件是：每一行、每一列、每一个3×3子块，不能有重复的数字。

class (object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        collen = len(board)
        rowlen = len(board[0])
        
        squarelen = 3
        for line in board:
            linedict = {}
            for i in line:
                if (i != '.'):
                    if (linedict.has_key(i)):
                        return False
                    else:
                        linedict[i] = 1
        for i in range(rowlen):
            rowdict = {}
            for j in range(collen):
                if (board[j][i] != '.'):
                    if (rowdict.has_key(board[j][i])):
                        return False
                    else:
                        rowdict[board[j][i]] = 1
                        
        for m in [0,3,6]:
            for n in [0,3,6]:
                squaredict = {}
                for i in range(squarelen):
                    for j in range(squarelen):
                        cur = board[i+m][j+n]
                        if (cur != '.'):
                            if (squaredict.has_key(cur)):
                                return False
                            else:
                                squaredict[cur] = 1
        
        return True