# N is the size of the 2D matrix N*N
N = 9

# Помощна функция за отпечатване на мрежа в посочения формат
def printing(arr):
    print("+-----+-------+-------+")
    for i in range(N):
        if i > 0 and i % 3 == 0:
            print("+-----+-------+-------+")
        for j in range(N):
            if j > 0 and j % 3 == 0:
                print("|", end=" ")
            print(arr[i][j], end=" ")
        print("|")
    print("+-----+-------+-------+")

# Проверява дали ще бъде правилно да присвоите num на дадения ред, кол
def isSafe(grid, row, col, num):
    # Проверете за дублиращи числа в подобен ред, връщаме false
    for x in range(N):
        if grid[row][x] == num:
            return False

    # Проверете за дублиращи колона в подобен ред, връщаме false
    for x in range(N):
        if grid[x][col] == num:
            return False

    # Проверете дали намерим същото число в конкретната матрица 3*3, връщаме false
    startRow = row - row % 3
    startCol = col - col % 3
    for i in range(3):
        for j in range(3):
            if grid[i + startRow][j + startCol] == num:
                return False
    return True

# Взема частично попълнена решетка и се опитва да присвои стойности на всички неприсвоени местоположения по такъв начин,
# че да отговаря на изискванията за решение за судоку (без дублиране в редове, колони и кутии) */
def solveSudoku(grid, row, col):
    # Проверете дали сме достигнали последния ред и колона, връщаме true, за да избегнем по-нататъшно връщане назад
    if row == N - 1 and col == N:
        return True

    # Проверете дали стойността на колоната става N, преминете към следващия ред и започнете колоната от 0
    if col == N:
        row += 1
        col = 0
    # Проверете дали текущата позиция на мрежата вече съдържа стойност > 0, итерирайте до следващата колона
    if grid[row][col] > 0:
        return solveSudoku(grid, row, col + 1)
    for num in range(1, N + 1, 1):
        # Проверете дали е безопасно да се постави числото (1-9) в дадения ред, колона, преминава към следващата колона
        if isSafe(grid, row, col, num):
            # Priema числото в текущата (ред, колона) позиция на мрежата и приемете,
            # че зададеното ни число в позицията е правилно
            grid[row][col] = num

            # Проверка за следващата възможност със следващата колона
            if solveSudoku(grid, row, col + 1):
                return True

        grid[row][col] = 0
    return False

# Инициализация на матрицата
matrix = [[0 for _ in range(N)] for _ in range(N)]

# Въвеждане на стойности от конзолата
for i in range(N):
    for j in range(N):
        # Въвеждане на стойност от конзолата и преобразуване към int
        element = int(input(f"Въведете стойност за ред {i + 1}, колона {j + 1}: "))
        matrix[i][j] = element

# Извеждане на матрицата
for row in matrix:
    print(row)

# Driver Code
solveSudoku(matrix, 0, 0)
printing(matrix)