given a partially filled 99 2d array the objective is to fill a 99 square grid with digits numbered 1 to 9 so that every row column and and each of the nine 33 subgrids contains all of the digits this can be solved using backtracking and is similar to nqueens we check to see if a cell is safe or not and recursively call the function on the next column to see if it returns true if yes we have solved the puzzle else we backtrack and place another number in that cell and repeat this process assigning initial values to the grid a grid with no solution this function checks the grid to see if each row column and the 3x3 subgrids contain the digit n it returns false if it is not safe a duplicate digit is found else returns true if it is safe this function finds an empty location so that we can assign a number for that particular row and column takes a partially filledin grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for sudoku solution nonduplication across rows columns and boxes sudokuinitialgrid doctest normalizewhitespace 3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9 sudokunosolution is none true if the location is none then the grid is solved a function to print the solution in the form of a 9x9 grid make a copy of grid so that you can compare with the unmodified grid assigning initial values to the grid a grid with no solution this function checks the grid to see if each row column and the 3x3 subgrids contain the digit n it returns false if it is not safe a duplicate digit is found else returns true if it is safe this function finds an empty location so that we can assign a number for that particular row and column takes a partially filled in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for sudoku solution non duplication across rows columns and boxes sudoku initial_grid doctest normalize_whitespace 3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9 sudoku no_solution is none true if the location is none then the grid is solved a function to print the solution in the form of a 9x9 grid make a copy of grid so that you can compare with the unmodified grid
from __future__ import annotations

Matrix = list[list[int]]


initial_grid: Matrix = [
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]


no_solution: Matrix = [
    [5, 0, 6, 5, 0, 8, 4, 0, 3],
    [5, 2, 0, 0, 0, 0, 0, 0, 2],
    [1, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]


def is_safe(grid: Matrix, row: int, column: int, n: int) -> bool:
    
    for i in range(9):
        if n in {grid[row][i], grid[i][column]}:
            return False

    for i in range(3):
        for j in range(3):
            if grid[(row - row % 3) + i][(column - column % 3) + j] == n:
                return False

    return True


def find_empty_location(grid: Matrix) -> tuple[int, int] | None:
    
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                return i, j
    return None


def sudoku(grid: Matrix) -> Matrix | None:
    
    if location := find_empty_location(grid):
        row, column = location
    else:
        
        return grid

    for digit in range(1, 10):
        if is_safe(grid, row, column, digit):
            grid[row][column] = digit

            if sudoku(grid) is not None:
                return grid

            grid[row][column] = 0

    return None


def print_solution(grid: Matrix) -> None:
    
    for row in grid:
        for cell in row:
            print(cell, end=" ")
        print()


if __name__ == "__main__":
    
    for example_grid in (initial_grid, no_solution):
        print("\nExample grid:\n" + "=" * 20)
        print_solution(example_grid)
        print("\nExample grid solution:")
        solution = sudoku(example_grid)
        if solution is not None:
            print_solution(solution)
        else:
            print("Cannot find a solution.")