• 分类：BackTracking

• 考察知识点：BackTracking 数组遍历

• 最优解时间复杂度：**O(???) ** BackTracking不好求

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.

代码：

解法:

class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.solved(board)
        
    #判断问题是否解决    
    def solved(self,board):
        for i in range(9):
            for j in range(9):
                # 当board[i][j]为空值的时候开始填数
                if board[i][j]=='.':
                    for k in range(1,10):
                        if self.isValid(board,i,j,str(k)):
                            board[i][j]=str(k)
                            if self.solved(board):
                                return True
                            else:
                                board[i][j]='.'
                    # 当填不了的时候返回False
                    return False
        return True
    
    #判断是否符合逻辑
    def isValid(self,board,row,col,num):
        for i in range(9):
            #row
            if board[row][i]!='.' and board[row][i]==num:
                return False     
            #col
            if board[i][col]!='.' and board[i][col]==num:
                return False
            
        for i in range(3):
            for j in range(3):
                if board[3*(row//3)+i][3*(col//3)+j]!='.' and board[3*(row//3)+i][3*(col//3)+j]==num:
                    return False
                
        return True

讨论：

1.这道题目是道Hard题，我就不深究它了，Beats的人少就少吧
2.这道题的思路完全和HashTable没有半毛钱的关系啊，不知道为什么它的tag还是HashTable- -真的是逗。。。
3.这道题和之前的Valid Soduku的第二种解法是类似的解，先是进行for循环，当遇到空值的时候填空值，如果这个空值填进去，先判断填进去后是否符合逻辑，然后再继续填（递归的开始），之后如果不合适的话就换一个填。逻辑还是有些复杂的，怪不得是Hard题

毕竟Hard