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

#define SIZE 9

void printMatrix(int matrix[SIZE][SIZE]);
bool isValidSudoku(int matrix[SIZE][SIZE]);
bool solveSudoku(int matrix[SIZE][SIZE]);
bool isSafe(int matrix[SIZE][SIZE], int row, int col, int num);
bool findUnassignedLocation(int matrix[SIZE][SIZE], int *row, int *col);

int main() {
    int board1[SIZE][SIZE] = {
        {8, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    printf("The original Sudoku matrix:\n");
    printMatrix(board1);

    if (!isValidSudoku(board1)) {
        printf("False: Invalid initial Sudoku matrix!\nNo solution!\n");
    } else {
        printf("True: Valid initial Sudoku matrix!\n");

        if (solveSudoku(board1)) {
            printf("The solution of Sudoku matrix:\n");
            printMatrix(board1);
        } else {
            printf("No solution!\n");
        }
    }

    return 0;
}

void printMatrix(int matrix[SIZE][SIZE]) {
    printf("|-------|-------|-------|\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (j % 3 == 0) printf("| ");
            if (matrix[i][j] == 0) {
                printf(". ");
            } else {
                printf("%d ", matrix[i][j]);
            }
        }
        printf("|\n");
        if (i % 3 == 2) printf("|-------|-------|-------|\n");
    }
}

bool isValidSudoku(int matrix[SIZE][SIZE]) {
    bool rowUsed[SIZE][SIZE + 1] = {false};  
    bool colUsed[SIZE][SIZE + 1] = {false};  
    bool blockUsed[SIZE][SIZE + 1] = {false};  

    for (int row = 0; row < SIZE; row++) {
        for (int col = 0; col < SIZE; col++) {
            int num = matrix[row][col];
            if (num != 0) {
                int blockIndex = (row / 3) * 3 + (col / 3);
                if (rowUsed[row][num] || colUsed[col][num] || blockUsed[blockIndex][num]) {
                    printf("False: Invalid initial Sudoku matrix!\n");
                    if (rowUsed[row][num]) {
                        printf("The number %d in the row %d has been used!\n", num, row + 1);
                    } else if (colUsed[col][num]) {
                        printf("The number %d in the col %d has been used!\n", num, col + 1);
                    } else if (blockUsed[blockIndex][num]) {
                        printf("The number %d in the block %d has been used!\n", num, blockIndex + 1);
                    }
                    return false;
                }
                rowUsed[row][num] = colUsed[col][num] = blockUsed[blockIndex][num] = true;
            }
        }
    }
    return true;
}


bool solveSudoku(int matrix[SIZE][SIZE]) {
    int row, col;

    if (!findUnassignedLocation(matrix, &row, &col)) {
        return true; 
    }

    for (int num = 1; num <= SIZE; num++) {
        if (isSafe(matrix, row, col, num)) {
            matrix[row][col] = num;
            if (solveSudoku(matrix)) {
                return true;
            }
            matrix[row][col] = 0; 
        }
    }
    return false;  
}

bool findUnassignedLocation(int matrix[SIZE][SIZE], int *row, int *col) {
    for (*row = 0; *row < SIZE; (*row)++) {
        for (*col = 0; *col < SIZE; (*col)++) {
            if (matrix[*row][*col] == 0) {
                return true;
            }
        }
    }
    return false;
}

bool isSafe(int matrix[SIZE][SIZE], int row, int col, int num) {
    for (int x = 0; x < SIZE; x++) {
        if (matrix[row][x] == num || matrix[x][col] == num) {
            return false;
        }
    }
    int startRow = row - row % 3, startCol = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (matrix[i + startRow][j + startCol] == num) {
                return false;
            }
        }
    }
    return true;
}