37. Sudoku Solver - cocoder39/coco39_LC GitHub Wiki

37. Sudoku Solver

T = 9 ^ (m*n)

reverting board[r][c] to '.' is necessary. Otherwise, the wrong decision at deeper level can affect upper level

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        opens = []
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    opens.append((i, j))
        
        self.solver(board, opens, 0)
    
    def solver(self, board, opens, idx):
        if len(opens) == idx:
            return True
        
        digits = set([i for i in range(1, 10)])

        r, c = opens[idx]
        for i in range(9):
            if '1' <= board[i][c] <= '9':
                d = ord(board[i][c]) - ord('0')
                if d in digits:
                    digits.remove(d)
            if '1' <= board[r][i] <= '9':
                d = ord(board[r][i]) - ord('0')
                if d in digits:
                    digits.remove(d)
        
        startR, startC = (r // 3) * 3, (c // 3) * 3
        for p in range(startR, startR+3):
            for q in range(startC, startC+3):
                if '1' <= board[p][q] <= '9':
                    d = ord(board[p][q]) - ord('0')
                    if d in digits:
                        digits.remove(d)
        
        for d in digits:
            board[r][c] = str(d)
            if self.solver(board, opens, idx+1):
                return True
            board[r][c] = '.'
        return False