37. Sudoku Solver(递归和回溯)

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

Solution1:(TLE)

class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.solve(board,0,0)


    def solve(self,board,i,j):
        if i==8 and j==8:
            return True
        if board[i][j]=='.':
            for t in range(1,10):
                board[i][j] = str(t)
                if self.isValidSudoku(board=board):
                    if j==8:
                        if self.solve(board,i+1,0):
                            return True
                    else:
                        if self.solve(board,i,j+1):
                            return True
                board[i][j] = '.'
        else:
            if j == 8:
                if self.solve(board, i + 1, 0):
                    return True
            else:
                if self.solve(board, i, j + 1):
                    return True
        return False


    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        def line():
            for i in range(9):
                ans = [0 for _ in range(10)]
                for j in range(9):
                    if board[i][j]=='.':
                        continue
                    ans[int(board[i][j])] += 1
                for t in ans:
                    if t>1:
                        return False
            return True
        def coloum():
            for j in range(9):
                ans = [0 for _ in range(10)]
                for i in range(9):
                    if board[i][j]=='.':
                        continue
                    ans[int(board[i][j])] += 1
                # print(j,'
',ans)
                for t in ans:
                    if t>1:
                        return False
            return True
        def boxes(a,b,c,d):
            ans = [0 for _ in range(10)]
            for i in range(a,b):
                for j in range(c,d):
                    if board[i][j]=='.':
                        continue
                    ans[int(board[i][j])] += 1
            for t in ans:
                if t>1:
                    return False
            return True
        if line() and coloum() and boxes(0,3,0,3) and boxes(3,6,0,3) and boxes(6,9,0,3) and boxes(0,3,3,6) and boxes(3,6,3,6) and boxes(6,9,3,6) and boxes(0,3,6,9) and boxes(3,6,6,9) and boxes(6,9,6,9):
            return True
        return False

Solution2:

class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.solve(board)

    def solve(self,board): #每次都是重新解决这个板子
        for i in range(9):
            for j in range(9):
                if board[i][j]=='.':
                    for c in range(1,10):
                        if self.isvalid(board,i,j,str(c)):
                            board[i][j] = str(c)
                            if self.solve(board):   #递归
                                return True
                            else:
                                board[i][j] = '.'  #回溯
                    return False
        return True

    def isvalid(self,board,row,col,c):
        for i in range(9):
            if board[row][i]==c or board[i][col]==c:
                return False
            if board[row//3*3+i//3][col//3*3+i%3]==c:
                return False
        return True

判断已经不需要那么麻烦，只需要判断新加的这个数字是否是valid就可以了。