37 Sudoku Solver

使用回溯法对于问题进行解决。 回溯法的思路就是，选择一个进行处理，处理了之后，抹除处理效果，进行后续操作。类似于深度搜索。

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.solve()
    def findUnassigned(self):
        for row in range(9):
            for col in range(9):
                if self.board[row][col] == '.':
                    return row, col
        return -1,-1

    def isValid(self,val,x,y):
        if self.checkRow(val,x,y) and self.checkCol(val,x,y) and self.checkBox(val,x,y):
            return True
        return False

    def checkCol(self,val,x,y):
        for col in range(9):
            if self.board[x][col] == chr(ord('0')+val):
                return False
        return True

    def checkRow(self,val,x,y):
        for row in range(9):
            if self.board[row][y] == chr(ord('0')+val):
                return False
        return True

    def checkBox(self,val,x,y):
        row_base = x-x%3
        col_base = y-y%3
        for row in range(3):
            for col in range(3):
                if self.board[row_base+row][col_base+col] == chr(ord('0')+val):
                    return False
        return True

    def solve(self):        
        x,y = self.findUnassigned()
        if [x,y] == [-1,-1]:
            return True
        for val in range(1,10):
            if self.isValid(val,x,y):
                self.board[x][y] = chr(ord('0')+val)
                if self.solve():
                    return True
                self.board[x][y] = '.'
        return False