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

#define N 9

// printf function
void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

// if placing num at board[row][col] is valid
bool isValid(int board[N][N], int row, int col, int num) {
    // Check row
    for (int x = 0; x < N; x++)
        if (board[row][x] == num)
            return false;

    // Check column
    for (int x = 0; x < N; x++)
        if (board[x][col] == num)
            return false;

    // Check grid
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (board[i + startRow][j + startCol] == num)
                return false;

    return true;
}

// solve Sudoku using backtracking
bool solveSudoku(int board[N][N]) {
    int row, col;
    bool emptyFound = false;

    // Find the next empty cell
    for (row = 0; row < N; row++) {
        for (col = 0; col < N; col++) {
            if (board[row][col] == 0) {
                emptyFound = true;
                break;
            }
        }
        if (emptyFound)
            break;
    }

    // No empty cell left, puzzle solved
    if (!emptyFound)
        return true;

    // Try placing digits 1-9
    for (int num = 1; num <= N; num++) {
        if (isValid(board, row, col, num)) {
            board[row][col] = num;

            if (solveSudoku(board))
                return true;

            // Undo if not valid
            board[row][col] = 0;
        }
    }

    return false; // No sol found
}

int main() {
    int board[N][N];

    // enter the board values
    printf("Enter the Sudoku board values (use 0 for empty cells):\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("Enter value for cell [%d][%d]: ", i + 1, j + 1);
            scanf("%d", &board[i][j]);
            // error handling included
            if (board[i][j] < 0 || board[i][j] > 9) {
                printf("Invalid input. Please enter a number between 0 and 9.\n");
                j--; // Retry current cell
            }
        }
    }

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

    return 0;
}