Valid Sudoku

偏执的太偏执、 2021-12-17 10:29 203阅读 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 `'.'`.

![250px-Sudoku-by-L2G-20050714.svg.png][]

A partially filled sudoku which is valid.

简单题，思路也非常直接，brute-force,按行扫，按列扫，按小方块扫，值得注意的是判断是否有重复元素，一个非常好的做法是使用set，一个是可以把所有不为'.'的元素加入set，判断最后set的大小是否等于不为0的元素数目。另外一个是把set当普通集合使用。但是因为python的set使用dictionary实现，判断元素在不在set中的平均时间复杂度为O(1).下面给出一个统一接口的实现，即将9个3\*3的扫描做了转化，不需要3\*3的循环。代码如下：

class Solution(object):
        def isValidSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: bool
            """
            for i in xrange(9):
                if not self.is_partially_valid(board,i,i+1,0,9): return False
                if not self.is_partially_valid(board,0,9,i,i+1): return False
                x = i/3*3
                y = i%3*3
                if not self.is_partially_valid(board,x,x+3,y,y+3): return False
                
            return True
    
        
        def is_partially_valid(self,board,x1,x2,y1,y2):
            a = set()
            for i in xrange(x1,x2):
                for j in xrange(y1,y2):
                  val = board[i][j]
                  if val != '.':
                      if val not in a:
                          a.add(val)
                      else:
                          return False
            return True

另外一个使用bool数字记录元素是否出现的解法也很巧妙,但是中间涉及到str到int的类型转换，代码如下：

class Solution(object):
        def isValidSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: bool
            """
            
            for i in xrange(9):
               res = [False]*9
               for j in xrange(9):
                   if board[i][j]!='.':
                      if res[int(board[i][j])-1]:
                         return False
                      else:
                         res[int(board[i][j])-1] = True
    
            for j in xrange(9):
                res = [False]*9
                for i in xrange(9):
                   if board[i][j]!='.':
                       if res[int(board[i][j])-1]:
                          return False
                       else:
                          res[int(board[i][j])-1] = True
            for i in xrange(9):
              res = [False]*9
              for j in range(i/3*3,i/3*3+3):
                  for k in range(i%3*3,i%3*3+3):
                      
                      if board[j][k] !='.':
                          if res[int(board[j][k])-1]:
                            return False
                          else:
                            res[int(board[j][k])-1] = True
            return True

转载于:https://www.cnblogs.com/sherylwang/p/5461858.html

[Sudoku Puzzles - The Rules]: http://sudoku.com.au/TheRules.aspx
[250px-Sudoku-by-L2G-20050714.svg.png]: /images/20211217/42956d842ae74680a5318bad1ad8adec.png