class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        # 1. State Management (The "Sets")
        # Use simple arrays/sets to track what numbers are currently in use
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        # 2. Pre-process the board
        # Fill our sets with the initial numbers given in the puzzle
        for r in range(9):
            for c in range(9):
                if board[r][c] != ".":
                    val = board[r][c]
                    rows[r].add(val)
                    cols[c].add(val)
                    boxes[(r // 3) * 3 + (c // 3)].add(val)

        # 3. The Backtracking Function
        def backtrack(r, c):
            # If we went past the last column, move to next row
            if c == 9:
                return backtrack(r + 1, 0)
            
            # If we went past the last row, we are done! Solution found.
            if r == 9:
                return True
            
            # If cell is already filled, skip it
            if board[r][c] != ".":
                return backtrack(r, c + 1)
            
            # Identify the 3x3 box index
            box_idx = (r // 3) * 3 + (c // 3)

            # Try numbers 1-9
            for k in range(1, 10):
                val = str(k)
                # CHECK CONSTRAINTS (O(1) lookup)
                if val not in rows[r] and val not in cols[c] and val not in boxes[box_idx]:
                    
                    # PLACE
                    board[r][c] = val
                    rows[r].add(val)
                    cols[c].add(val)
                    boxes[box_idx].add(val)

                    # RECURSE
                    if backtrack(r, c + 1):
                        return True
                    
                    # BACKTRACK (Remove)
                    board[r][c] = "."
                    rows[r].remove(val)
                    cols[c].remove(val)
                    boxes[box_idx].remove(val)
            
            return False

        backtrack(0, 0)