class Solution:
    def __init__(self):
        self.rows = {i: set() for i in range(9)}
        self.cols = {i: set() for i in range(9)}
        self.boxes = {i: set() for i in range(9)}

    def get_box_number(self, row, col):
        return (row // 3) * 3 + (col // 3)

    def init_used_numbers(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j])
                    self.rows[i].add(num)
                    self.cols[j].add(num)
                    self.boxes[self.get_box_number(i, j)].add(num)

    def is_valid(self, row, col, num):
        box_num = self.get_box_number(row, col)
        return num not in self.rows[row] and num not in self.cols[col] and num not in self.boxes[box_num]

    def solveSudoku(self, board):
        self.init_used_numbers(board)
        self.backtrack(board)
        return board
        
    def backtrack(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in range(1, 10):
                        if self.is_valid(i, j, num):
                            board[i][j] = str(num)
                            self.rows[i].add(num)
                            self.cols[j].add(num)
                            self.boxes[self.get_box_number(i, j)].add(num)
                            if self.backtrack(board):
                                return True
                            board[i][j] = '.'
                            self.rows[i].remove(num)
                            self.cols[j].remove(num)
                            self.boxes[self.get_box_number(i, j)].remove(num)
                    return False
        return True