def read_sudoku(file_name):
    digits = [c for c in open(file_name).read() if c in '1234567890']
    matrix = []
    for i in range(9):
        line = []
        for j in range(9):
            line.append(int(digits[j + 9 * i]))
        matrix.append(line)
    return matrix


def get_row(matrix, row_number):
    return matrix[row_number]


def get_col(matrix, col_number):
    col = []
    for i in range(9):
        col.append(matrix[i][col_number])
    return col


def get_block(matrix, position):
    col = int(position[1] / 3) * 3
    row = int(position[0] / 3) * 3
    block = []
    for i in range(3):
        for j in range(3):
            block.append(matrix[row + i][col + j])
    return block


def find_empty_position(matrix):
    for i in range(9):
        for j in range(9):
            if matrix[i][j] == 0:
                return i, j
    return -1, -1


def find_possible_values(matrix, position):
    row = get_row(matrix, position[0])
    col = get_col(matrix, position[1])
    block = get_block(matrix, position)
    is_exist = []
    for i in range(10):
        is_exist.append(True)
    for i in range(9):
        if row[i] != 0:
            is_exist[row[i]] = False
        if col[i] != 0:
            is_exist[col[i]] = False
        if block[i] != 0:
            is_exist[block[i]] = False
    possible_values = []
    for i in range(1, 10):
        if is_exist[i]:
            possible_values.append(i)
    return possible_values


def is_end(matrix):
    position = find_empty_position(matrix)
    if position[0] == -1:
        return True
    return False


def solve_sudoku(matrix):
    position = find_empty_position(matrix)
    row = position[0]
    col = position[1]
    values = find_possible_values(matrix, position)
    if len(values) == 0:
        return matrix
    for i in values:
        matrix[row][col] = i
        if is_end(matrix):
            return matrix
        matrix = solve_sudoku(matrix)
        if is_end(matrix):
            return matrix
    matrix[row][col] = 0
    return matrix


def print_sudoku(matrix):
    for i in range(9):
        if i % 3 == 0 and i != 0:
            print('\n')
        for j in range(9):
            if j % 3 == 0 and j != 0:
                print("    ", end="")
            print(matrix[i][j], end=" ")
        print()


def check_solution(matrix):
    return check_blocks(matrix) and check_cols(matrix) and check_rows(matrix)


def check_blocks(matrix):
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            block = get_block(matrix, (i, j))
            if not common_check(block):
                return False
    return True


def check_rows(matrix):
    for i in range(9):
        row = get_row(matrix, i)
        if not common_check(row):
            return False
    return True


def check_cols(matrix):
    for i in range(9):
        col = get_col(matrix, i)
        if not common_check(col):
            return False
    return True


def common_check(values):
    result = []
    for k in range(10):
        result.append(0)
    for k in values:
        result[k] += 1
    for k in range(1, 10):
        if result[k] != 1:
            return False
    return True


print("Enter the name of the file with sudoku: ", end="")
fileName = input()
sudoku = read_sudoku(fileName)
sudoku = solve_sudoku(sudoku)
print_sudoku(sudoku)
print("Do you want check solution? Y/N")
answer = input().lower()
if answer == "yes" or answer == 'y':
    print(check_solution(sudoku))