leetcode-backtracking

37. Sudoku Solver.py

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        
        Brute Force
        1. Generate all possible boards
        2. To check if it's a valid sudoku board. 
        So, the operation is exponential amount.
        T(9**81), where 9 is # choices we can make to fill empty cell and 81 is number of cells we need to fill in the grid.
       
        Backtracking
        
        T( (9!) ** 9) because
        1. not more than 9! possibilities in a just one row.
        2. It mean, not more than (9!) ** 9 operations in total.
        Note:
        We use array+dictionary to represent 9 rows, 9 columns and 9 sub-grids to have constant accessing time, O(1).
        """
        
        def _box_index(row, col):
            # function to compute box index
            return (row // n ) * n + col // n
        
        def _could_not_place(d, row, col):
            """
            Check if one could place a number d in (row, col) cell
            """
            return (d in rows[row] or d in columns[col] or \
                    d in boxes[_box_index(row, col)])
         
        def backtrack(row = 0, col = 0): 
            # base case
            if row == N:
                # the flag is set to tell us we find optimal solution(it's a unique solution), no need to backtrack to previous state
                self.sudoku_solved = True 
                return 
            
            if col == N:
                # if we're in the end of the row, go to the next row(start from col = 0)
                return backtrack(row+1, 0)
            
            if board[row][col] != '.':
                # only empty cell, we try to fill the cell
                return backtrack(row, col+1)
            
            for d in range(1, 10):
                if _could_not_place(d, row, col):
                    continue
                # mark a certain row, columns, and subgrid has a certain digit
                rows[row][d] += 1
                columns[col][d] += 1
                boxes[_box_index(row, col)][d] += 1
                board[row][col] = str(d)
                backtrack(row, col+1)
                if not self.sudoku_solved:
                    # backtrack to previous state if needed(node in the recursion tree)
                    del rows[row][d]
                    del columns[col][d]
                    del boxes[_box_index(row, col)][d]
                    # undo what we did previously by making the cell empty again
                    board[row][col] = '.' 
        # box size
        n = 3
        # row size
        N = n * n
        # init rows, columns and boxes that contains digits originally
        rows = [defaultdict(int) for _ in range(N)]
        columns = [defaultdict(int) for _ in range(N)]
        boxes = [defaultdict(int) for _ in range(N)]
        for row in range(N):
            for col in range(N):
                if board[row][col] != '.': 
                    d = int(board[row][col])
                    # mark a certain row, columns, and subgrid has a certain digit
                    rows[row][d] += 1
                    columns[col][d] += 1
                    boxes[_box_index(row, col)][d] += 1
            
        self.sudoku_solved = False
        backtrack()