#include <stdio.h>
#include <stdbool.h>

#define ε > 0
#define N 9

bool recSudoku(int board[N][N], int row, int column);

// Function to print the board
void printBoard(int board[N][N])
{
    // You shouldn't change this function!!

    for (int i = 0; i < N; i++)
    {
        if (i % 3 == 0 && i != 0)
        {
            printf("---------------------\n");
        }
        for (int j = 0; j < N; j++)
        {
            if (j % 3 == 0 && j != 0)
            {
                printf("| ");
            }
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

bool recSquare(int board[N][N], int num, int start[2],
    int current[2], int end[2])
{
    if (current[0] == end[0])
    {
        return true;
    }
    if (current[1] == end[1])
    {
        current[0]++;
        current[1] = start[1];
        return recSquare(board, num, start, current, end);
    }

    if (board[current[0]][current[1]] == (num + 1))
    {
        return false;
    }
    current[1]++;
    return recSquare(board, num, start, current, end);
}

bool checkSquare(int board[N][N], int num, int row, int column)
{
    int mult = N / 3;
    int start[2] = {(row / mult) * mult, (column / mult) * mult};
    int end[2] = {start[0] + mult, start[1] + mult};
    int loc[2] = {start[0], start[1]};
    return recSquare(board, num, start, loc, end);
}

bool checkColumn(int board[N][N], int num, int row, int column)
{
    if (row == N)
    {
        return true;
    }

    if (board[row][column] == (num + 1))
    {
        return false;
    }
    return checkColumn(board, num, row + 1, column);
}

bool checkRow(int board[N][N], int num, int row, int column)
{
    if (column == N)
    {
        return true;
    }

    if (board[row][column] == (num + 1))
    {
        return false;
    }
    return checkRow(board, num, row, column + 1);
}

bool chooseANum(int board[N][N], int row, int column, int num)
{
    if (num == N)
    {
        return false;
    }

    bool valRow = checkRow(board, num, row, 0);
    bool valCol = checkColumn(board, num, 0, column);
    bool valSqu = checkSquare(board, num, row, column);
    if (valRow && valCol && valSqu)
    {
        board[row][column] = (num + 1);
        int before[] = {row, column};
        column++;
        int val = recSudoku(board, row, column);
        if (!val)
        {
            row = before[0];
            column = before[1];
            board[row][column] = 0;
        }
        return val || chooseANum(board, row, column, num + 1);
    }
    return chooseANum(board, row, column, num + 1);
}

bool recSudoku(int board[N][N], int row, int column)
{
    if (row == N)
    {
        return true;
    }
    if (column == N)
    {
        return recSudoku(board, row + 1, 0);
    }

    if (board[row][column] != 0)
    {
        return recSudoku(board, row, column + 1);
    }

    return chooseANum(board, row, column, 0);
}

bool solveSudoku(int board[N][N])
{
    return recSudoku(board, 0, 0);
}


int main(void)
{
    // You shouldn't change this function!!

    int board[N][N];

    // Read input directly into the board
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &board[i][j]);
        }
    }

    printf("Original Sudoku:\n");
    printBoard(board);
    if (solveSudoku(board))
    {
        printf("Solved Sudoku:\n");
        printBoard(board);
    }
    else
    {
        printf("No solution exists.\n");
    }

    return 0;
}