#include <stdio.h>
#include <stdbool.h>
void print_sudoku(int matrix[9][9]) {
    int i,j;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if (matrix[i][j] == 0) {
                printf(". ");
            } else {
                printf("%d ", matrix[i][j]);
            }
        }
        printf("\n");
    }
}
bool is_safe(int matrix[9][9], int row, int col, int num) {
    int i,j;
    for (i = 0; i < 9; i++) {
        if (matrix[row][i] == num) {
            return false;
        }
    }
    for (i = 0; i < 9; i++) {
        if (matrix[i][col] == num) {
            return false;
        }
    }
    int start_row = row - row % 3;
    int start_col = col - col % 3;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            if (matrix[i + start_row][j + start_col] == num) {
                return false;
            }
        }
    }

    return true;
}
bool solve_sudoku(int matrix[9][9]) {
    int i,j,num;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if (matrix[i][j] == 0) {
                for (num = 1; num <= 9; num++) {
                    if (is_safe(matrix, i, j, num)) {
                        matrix[i][j] = num;
                        if (solve_sudoku(matrix)) {
                            return true;
                        }
                        matrix[i][j] = 0;
                    }
                }
                return false; 
            }
        }
    }
    return true;
}
bool is_valid_sudoku(int matrix[9][9], char* error_message) {
    int i,j;
    for (i = 0; i < 9; i++) {
        bool row_set[10] = {0}; 
        bool col_set[10] = {0}; 
        bool block_set[10] = {0}; 

        for (j = 0; j < 9; j++) {
            if (matrix[i][j] != 0 && row_set[matrix[i][j]]) {
                sprintf(error_message, "Row %d has duplicates.", i + 1);
                return false;
            }
            if (matrix[i][j] != 0) row_set[matrix[i][j]] = true;
            if (matrix[j][i] != 0 && col_set[matrix[j][i]]) {
                sprintf(error_message, "Column %d has duplicates.", i + 1);
                return false;
            }
            if (matrix[j][i] != 0) col_set[matrix[j][i]] = true;
            int block_row = (i / 3) * 3;
            int block_col = (i % 3) * 3;
            int num = matrix[block_row + j / 3][block_col + j % 3];
            if (num != 0 && block_set[num]) {
                sprintf(error_message, "Block starting at (%d,%d) has duplicates.", block_row + 1, block_col + 1);
                return false;
            }
            if (num != 0) block_set[num] = true;
        }
    }
    return true;
}

int main() {
    int sudoku[9][9] = {
        {5, 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");
    print_sudoku(sudoku);

    char error_message[100];
    bool valid = is_valid_sudoku(sudoku, error_message);

    if (valid) {
        printf("True: Valid initial Sudoku matrix!\n");
        if (solve_sudoku(sudoku)) {
            printf("The solution of Sudoku matrix:\n");
            print_sudoku(sudoku);
        } else {
            printf("No solution!\n");
        }
    } else {
        printf("False: Invalid initial Sudoku matrix!\n");
        printf("%s\n", error_message);
        printf("No solution!\n");
    }

    return 0;
}