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

// 判断数字在行是否重复
bool isRowValid(int matrix[9][9], int row, int num) {
    for (int col = 0; col < 9; col++) {
        if (matrix[row][col] == num) {
            return false;
        }
    }
    return true;
}

// 判断数字在列是否重复
bool isColValid(int matrix[9][9], int col, int num) {
    for (int row = 0; row < 9; row++) {
        if (matrix[row][col] == num) {
            return false;
        }
    }
    return true;
}

// 判断数字在3x3的子矩阵是否重复
bool isBlockValid(int matrix[9][9], int startRow, int startCol, int num) {
    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {
            if (matrix[startRow + row][startCol + col] == num) {
                return false;
            }
        }
    }
    return true;
}

// 判断是否满足数独矩阵的定义
bool isValidSudoku(int matrix[9][9]) {
    int sum = 0;

    // 检查每行是否出现重复
    for (int row = 0; row < 9; row++) {
        sum = 0;
        for (int col = 0; col < 9; col++) {
            sum += matrix[row][col];
            if (!isRowValid(matrix, row, matrix[row][col]) || !isColValid(matrix, col, matrix[row][col]) || !isBlockValid(matrix, row - row % 3, col - col % 3, matrix[row][col])) {
                return false;
            }
        }
        if (sum != 45) {
            return false;
        }
    }

    // 检查每列是否出现重复
    for (int col = 0; col < 9; col++) {
        sum = 0;
        for (int row = 0; row < 9; row++) {
            sum += matrix[row][col];
            if (!isRowValid(matrix, row, matrix[row][col]) || !isColValid(matrix, col, matrix[row][col]) || !isBlockValid(matrix, row - row % 3, col - col % 3, matrix[row][col])) {
                return false;
            }
        }
        if (sum != 45) {
            return false;
        }
    }

    // 检查每个3x3子矩阵是否出现重复
    for (int startRow = 0; startRow < 9; startRow += 3) {
        for (int startCol = 0; startCol < 9; startCol += 3) {
            sum = 0;
            for (int row = 0; row < 3; row++) {
                for (int col = 0; col < 3; col++) {
                    sum += matrix[startRow + row][startCol + col];
                    if (!isRowValid(matrix, startRow + row, matrix[startRow + row][startCol + col]) || !isColValid(matrix, startCol + col, matrix[startRow + row][startCol + col]) || !isBlockValid(matrix, startRow, startCol, matrix[startRow + row][startCol + col])) {
                        return false;
                    }
                }
            }
            if (sum != 45) {
                return false;
            }
        }
    }

    return true;
}

// 解数独
bool solveSudoku(int matrix[9][9]) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (matrix[row][col] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (isRowValid(matrix, row, num) && isColValid(matrix, col, num) && isBlockValid(matrix, row - row % 3, col - col % 3, num)) {
                        matrix[row][col] = num;
                        if (solveSudoku(matrix)) {
                            return true;
                        }
                        matrix[row][col] = 0; // 回溯
                    }
                }
                return false;
            }
        }
    }
    return true;
}

// 打印数独矩阵
void printMatrix(int matrix[9][9]) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            printf("%d ", matrix[row][col]);
        }
        printf("\n");
    }
}

int main() {
    int matrix[9][9] = {
        {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, 0},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

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

    bool isSudokuValid = solveSudoku(matrix);

    if (isSudokuValid) {
        printf("True:Valid initial Sudoku matrix!\n");
        printf("The solution of Sudoku matrix:\n");
        printMatrix(matrix);
    }
    else {
        printf("False:Invalid initial Sudoku matrix!\n");
        printf("No solution!\n");
    }

    return 0;
}