python实现 LeetCode37——Sudoku Solver

数独游戏，用了dfs的深度优先树。

25行和26行的else将该位置改为点，是在一次dfs中的，相当于在for循环中不断尝试c值中的赋值。

如果所有的c值都不对的时候会进入27行的return false，然后再进入23行的赋值。

class Solution(object):
    def solveSudoku(self, board):
        def isvaild(i,j):
            for m in range(9):
                if m!=i and board[m][j]==board[i][j]:
                    return False
            for n in range(9):
                if n!=j and board[i][n]==board[i][j]:
                    return False
            for m in range(i/3*3,i/3*3+3):
                for n in range(j/3*3,j/3*3+3):
                    if m!=i and n!=j and board[m][n]==board[i][j]:
                        return False
            return True
        for i in range(9):
            for j in range(9):
                if board[i][j]=='.':
                    for c in '123456789':
                        board[i][j]=c
                        if isvaild(i,j):
                            if self.solveSudoku(board):
                                return True
                            else:
                                board[i][j] = '.'
                        else:
                            board[i][j] = '.'
                    return False
        return True