Problem statement

https://binarysearch.com/problems/Sudoku-Solver/

Solution

Equal to Leetcode 0037. Sudoku Solver

Complexity

Time complexity of one dfs step is O(1), because we actually need to check row, column and box. However it is difficult to estimate overall complexity of algorithm - I think it is exponential at least. Space complexity is O(1).

Code

class Solution:    
    def solve(self, board):
        def dfs(board, empty, rows, cols, boxes):
            if not empty: return True
            r, c = empty[-1]
            for k in set(range(1,10)) - (rows[r]|cols[c]|boxes[3*(r//3)+c//3]):
                board[r][c] = k
                for dic in [rows[r], cols[c], boxes[3*(r//3)+c//3]]:
                    dic.add(k)
                if dfs(board, empty[:-1], rows, cols, boxes): return True
                board[r][c] = '.'
                for dic in [rows[r], cols[c], boxes[3*(r//3)+c//3]]:
                    dic.remove(k)

            return False
        
        cols, rows, boxes, empty = defaultdict(set), defaultdict(set), defaultdict(set), []
        for r, c in product(range(9), range(9)):
            if board[r][c] == 0:
                empty.append((r,c))
            else:
                for dic in [rows[r], cols[c], boxes[3*(r//3)+c//3]]:
                    dic.add(board[r][c])
               
        dfs(board, empty, rows, cols, boxes)
        return board