37 Sodoku Solver

https://leetcode.com/problems/sudoku-solver/

solution

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.dfs(board)

    def dfs(self, board):
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] != '.':
                    continue
                for k in range(1, 10):
                    if self.is_valid(board, i, j, k):
                        board[i][j] = str(k)
                        if self.dfs(board):
                            return True
                        board[i][j] = '.'
                return False
        return True

    def is_valid(self, board, row, col, val):
        for i in range(9):
            if board[row][i] == str(val):
                return False
        # 判断同一列是否冲突
        for j in range(9):
            if board[j][col] == str(val):
                return False
        # 判断同一九宫格是否有冲突
        start_row = (row // 3) * 3
        start_col = (col // 3) * 3
        for i in range(start_row, start_row + 3):
            for j in range(start_col, start_col + 3):
                if board[i][j] == str(val):
                    return False
        return True

时间复杂度：O(9^m) 空间复杂度：O(m)

follow up

36. Valid Sudoku

• 同一行，同一列，同一小方形不能有重复值

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        res = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == '.':
                    continue

                element = board[i][j]
                res += [(i, element), (element, j), (i//3, j//3, element)]
        return len(res) == len(set(res))

时间复杂度：O(1) 空间复杂度：O(1)