37. Sudoku Solver

Description

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
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.

Solutions

1. Backtracking

　　注意剪枝！

# Time: O()
# Space: O()
class Solution:
    def dfs_Sudoku(self, row_map, col_map, sec_map, unfilled, board):
        
        if len(unfilled)==0: return True
        
        row, col = unfilled.pop()
        for num in range(9):
            sec_index = 3 * (row // 3) + col // 3
            if row_map[row][num] == False and \
               col_map[col][num] == False and \
               sec_map[sec_index][num] == False:
                row_map[row][num] = True
                col_map[col][num] = True
                sec_map[sec_index][num] = True
                board[row][col] = str(num+1)
                
                completed = self.dfs_Sudoku(row_map, col_map, sec_map, unfilled, board)
                
                if completed: return True
                
                row_map[row][num] = False
                col_map[col][num] = False
                sec_map[sec_index][num] = False
                board[row][col] = '.'
        unfilled.append((row, col))
        return False
    
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        unfilled = []
        row_map = [[False]*9 for _ in range(9)]
        col_map = [[False]*9 for _ in range(9)]
        sec_map = [[False]*9 for _ in range(9)]
        
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.': 
                    unfilled.append((i,j))
                    continue
                index = int(board[i][j]) - 1
                row_map[i][index] = True
                col_map[j][index] = True
                sec_index = 3 * (i // 3) + j // 3
                sec_map[sec_index][index] = True
        
        self.dfs_Sudoku(row_map, col_map, sec_map, unfilled, board)
# 6/6 cases passed (148 ms)
# Your runtime beats 73.69 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)

　　采用迭代形式：

# Time: O()
# Space: O()
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def isValid(x,y):
            tmp=board[x][y]
            board[x][y]='D'
            for i in range(9):
                if board[i][y]==tmp: 
                    return False
            for i in range(9):
                if board[x][i]==tmp: 
                    return False
            for i in range(3):
                for j in range(3):
                    if board[(x//3)*3+i][(y//3)*3+j]==tmp: 
                        return False
            board[x][y]=tmp
            return True
        
        def dfs(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j]=='.':
                        for k in '123456789':
                            board[i][j]=k
                            if isValid(i,j) and dfs(board):
                                return True
                            board[i][j]='.'
                        return False
            return True
        dfs(board)
# 6/6 cases passed (752 ms)
# Your runtime beats 19.48 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)

References

37. Sudoku Solver