[Leetcode][python]Sudoku Solver/解数独

淡淡的烟草味﹌ 2022-06-08 04:48 227阅读 0赞

## 题目大意 ##

计算数独，假设解唯一

## 解题思路 ##

回溯法，深度优先

## 代码 ##

这一题注释写的很多，因为比较复杂头疼中

class Solution(object):
    
        seen = set()
    
        def isValue(self,board,x,y):
            # 判断符合，就是上一题
            c = board[x][y]
            if (x, c) in self.seen or (c, y) in self.seen or (x/3, y/3, c) in self.seen:
                return False
            self.seen.add((x, c))
            self.seen.add((c, y))
            self.seen.add((x/3, y/3, c))
            return True
    
        def dfs(self,board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for k in '123456789':
                            # 向第一个找到的空格填写了数字
                            board[i][j] = k  
                            # 左边验证该数字是符合标准的，右边验证之后一个数字是否正确（回溯法）
                            if self.isValue(board,i,j) and self.dfs(board):  #如果这两个and前后交换顺序就TLE
                                return True
                            board[i][j] = '.'
                        # 该False表示如果都不正确，之前一直没返回True 
                        return False
            # 这个True是每一行的最后如果没有数了，说明该行都填写上了，所以返回True这样self.dfs(board) = True，该行结束
            return True
    
        def solveSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            for i in range(9):
                for j in range(9):
                    c = board[i][j]
                    if c == '.':
                        continue
                    self.seen.add((i, int(c)))
                    self.seen.add((int(c), j))
                    self.seen.add((i/3, j/3, int(c)))
            print self.seen
            self.dfs(board)

## 总结 ##

上一题hashtable的解法效率很高，想挪过来判断，但始终没修改成功，以后有空改好它，在这里做备份。

class Solution(object):
    
        seen = set()
    
        def isValue(self,board,x,y):
            # 判断符合，就是上一题
            c = int(board[x][y])
            if (x, c) in self.seen or (c, y) in self.seen or (x/3, y/3, c) in self.seen:
                print 'buxing'
                return False
            self.seen.add((x, c))
            self.seen.add((c, y))
            self.seen.add((x/3, y/3, c))
            return True
    
        def dfs(self,board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for k in '123456789':
                            board[i][j] = k  # 向第一个找到的空格填写了数字
                            # 左边验证该数字是符合标准的，右边验证之后一个数字是否正确（回溯法）
                            if self.isValue(board,i,j) and self.dfs(board):  #如果这两个and前后交换顺序就TLE,说明and确实只判断前面的False就会停止
                                return True
                            # 问题在何时删除这个key，应该是删除上一位已经正确的key
                            # else: 
                            #     self.seen.remove((i, int(k)))
                            #     self.seen.remove((int(k), j))
                            #     self.seen.remove((i/3, j/3, c))
                            board[i][j] = '.'
    
                        # 该False表示如果都不正确，之前一直没返回True 
                        return False
            # 这个True是每一行的最后如果没有数了，说明该行都填写上了，所以返回True这样self.dfs(board) = True，该行结束
            return True
    
        def solveSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            for i in range(9):
                for j in range(9):
                    c = board[i][j]
                    if c == '.':
                        continue
                    self.seen.add((i, int(c)))
                    self.seen.add((int(c), j))
                    self.seen.add((i/3, j/3, int(c)))
            print self.seen
            self.dfs(board)