'''
Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.
generate working python code that implements the Storyboard class and Scene class
'''

# Define the Sudoku grid as a 9x9 list of lists, where 0 represents an empty cell
grid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

def solve_sudoku(grid):
    """
    Solves a Sudoku puzzle using a recursive backtracking algorithm.
    """
    # Find the next empty cell in the grid
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                # Try each digit from 1 to 9 in the empty cell
                for digit in range(1, 10):
                    if is_valid(grid, row, col, digit):
                        # If the digit is valid, place it in the cell and recurse
                        grid[row][col] = digit
                        if solve_sudoku(grid):
                            return True
                        # If the recursion doesn't lead to a solution, backtrack
                        grid[row][col] = 0
                # If none of the digits work, the puzzle is unsolvable
                return False
    # If there are no empty cells, the puzzle is solved
    return True

def is_valid(grid, row, col, digit):
    """
    Checks if a given digit is valid in a given cell of the Sudoku grid.
    """
    # Check if the digit is already in the same row or column
    for i in range(9):
        if grid[row][i] == digit or grid[i][col] == digit:
            return False
    # Check if the digit is already in the same 3x3 subgrid
    subgrid_row = (row // 3) * 3
    subgrid_col = (col // 3) * 3
    for i in range(subgrid_row, subgrid_row + 3):
        for j in range(subgrid_col, subgrid_col + 3):
            if grid[i][j] == digit:
                return False
    # If the digit passes all tests, it is valid
    return True

# Solve the Sudoku puzzle
solve_sudoku(grid)

# Print the solved grid
for row in grid:
    print(row)