from typing import Tuple


def generate_matrixes(start_matrix: list[list[int]], nulls_passed: int = 0) -> list[list[list[int]]]:
    if nulls_passed - 1 == count_nulls_in_matrix(start_matrix):
        return [start_matrix]
    
    coords = count_coords(start_matrix, nulls_passed)
    if coords is None:
        print("\n\n\n\n\n\n\nNI NI NI\n\n\n\n\n\n\n")
    x, y = coords

    numbers_we_can_put = get_possible_numbers(start_matrix, x, y)

    all_new_matrixes: list[list[list[int]]] = []
    for numb in numbers_we_can_put:
        new_matrix = my_deep_copy(start_matrix)
        new_matrix[x][y] = numb
        new_generated_matrixes = generate_matrixes(new_matrix, nulls_passed + 1)
        all_new_matrixes = my_extend(all_new_matrixes, new_generated_matrixes)

    return all_new_matrixes
    

def my_extend(arr1: list[list[list]], arr2: list[list[list]]) -> list[list[list]]:
    for matrix in arr2:
        arr1.append(matrix)
    return arr1


def my_deep_copy(arr: list[list]) -> list[list]:
    new_arr = []
    for i in range(len(arr)):
        new_row = []
        for j in range(len(arr[i])):
            new_row.append(arr[i][j])
        new_arr.append(new_row)
    return new_arr

def count_coords(matrix: list[list[int]], at_null: int) -> Tuple[int, int]:
    numbers_passed = 0

    for ind1 in range(len(matrix)):
        for ind2 in range(len(matrix[ind1])):
            elem = matrix[ind1][ind2]
            if elem == 0 and numbers_passed != at_null:
                numbers_passed += 1
            elif elem == 0 and numbers_passed == at_null:
                return ind1, ind2
            

def get_possible_numbers(matrix: list[int], i: int, j: int) -> list[int]:
    possible_numbers = get_canon_numbers()

    for ind_in_row in range(len(matrix[i])):
        elem_in_row = matrix[i][ind_in_row]
        if ind_in_row != j and elem_in_row != 0:
            try_to_remove(possible_numbers, elem_in_row)

    for ind_in_col in range(len(matrix)):
        elem_in_col = matrix[ind_in_col][j]
        if ind_in_col != i and elem_in_col != 0:
            try_to_remove(possible_numbers, elem_in_col)
    
    square = get_square(matrix, i, j)
    for ind_1 in range(3):
        for ind_2 in range(3):
            elem = square[ind_1][ind_2]
            if not(ind_1 == i and ind_2==j):
                if elem != 0:
                    try_to_remove(possible_numbers, elem)

    return possible_numbers

def try_to_remove(arr: list[int], numb: int) -> list:
    if numb in arr:
        arr.remove(numb)
    
    return arr


def get_square(matrix: list[int], i: int, j: int) -> list[int]:
    square_i = i // 3
    square_j = j // 3

    square = []
    for ind_1 in range(3):
        square_row = []

        for ind_2 in range(3):
            elem = matrix[(square_i * 3) + ind_1][(square_j * 3) + ind_2]
            square_row.append(elem)

        square.append(square_row)

    return square


def count_nulls_in_matrix(matrix: list[list[int]]) -> int:
    summ = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == 0:
                summ += 1
    return summ


def check_if_matrix_right(matrix: list[list[int]]) -> bool:
    canon_numbers = get_canon_numbers()

    for i in range(len(matrix)):
        numbers_arr = []
        for j in range(len(matrix[i])):
            elem = matrix[i][j]
            if elem == 0:
                return False
            numbers_arr.append(elem)

        if not is_arrays_equal(numbers_arr, canon_numbers):
            return False
        
    for col_ind in range(len(matrix)):
        numbers_arr = []
        for row_ind in range(len(matrix[col_ind])):
            elem = matrix[row_ind][col_ind]
            numbers_arr.append(elem)

        if not is_arrays_equal(numbers_arr, canon_numbers):
            return False
        
    for square_i in range(3):
        for square_j in range(3):
            square = get_square(matrix, square_i * 3, square_j * 3)
            numbers_arr = []
            for i in range(3):
                for j in range(3):
                    elem = square[i][j]
                    numbers_arr.append(elem) 
            if not is_arrays_equal(numbers_arr, canon_numbers):
                return False
            
    return True
        
            
def get_canon_numbers() -> list[int]:
    return [i for i in range(1, 9 + 1)]


def is_arrays_equal(arr1: list[int], arr2: list[int]) -> bool:
    if len(arr1) != len(arr2):
        return False
    
    for i in range(len(arr1)):
        if arr1[i] != arr2[i]:
            return False
        
    return True


def sudoku(matrix):
    all_variants = generate_matrixes(matrix, 0)
    for variant in all_variants:
        if check_if_matrix_right(variant):
            return variant
        
    return matrix


if __name__ == '__main__':
    matrix =    [ [0, 0, 0, 8, 0, 0, 0, 0, 0],
                      [4, 0, 0, 0, 1, 5, 0, 3, 0],
                      [0, 2, 9, 0, 4, 0, 5, 1, 8],
                      [0, 4, 0, 0, 0, 0, 1, 2, 0],
                      [0, 0, 0, 6, 0, 2, 0, 0, 0],
                      [0, 3, 2, 0, 0, 0, 0, 9, 0],
                      [6, 9, 3, 0, 5, 0, 8, 7, 0],
                      [0, 5, 0, 4, 8, 0, 0, 0, 1],
                      [0, 0, 0, 0, 0, 3, 0, 0, 0] ]
                      
    matrix_copy =    [ [0, 0, 0, 8, 0, 0, 0, 0, 0],
                      [4, 0, 0, 0, 1, 5, 0, 3, 0],
                      [0, 2, 9, 0, 4, 0, 5, 1, 8],
                      [0, 4, 0, 0, 0, 0, 1, 2, 0],
                      [0, 0, 0, 6, 0, 2, 0, 0, 0],
                      [0, 3, 2, 0, 0, 0, 0, 9, 0],
                      [6, 9, 3, 0, 5, 0, 8, 7, 0],
                      [0, 5, 0, 4, 8, 0, 0, 0, 1],
                      [0, 0, 0, 0, 0, 3, 0, 0, 0] ]
    
    ans = sudoku(matrix)
    is_right = check_if_matrix_right(ans)
    print(is_right)
    print(ans)