【Leetcode】【python】Sudoku Solver 解数独

题目大意

计算数独，假设解唯一

解题思路

回溯法，深度优先

代码

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

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)