void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%2d", board[i][j]);
            if (j < N - 1) {
                printf(" ");
            }
        }
        printf("\n");
    }
}
// 检查数独矩阵的有效性
int isValid(int board[N][N], int row, int col, int num) {
    // 检查行
    for (int i = 0; i < N; i++) {
        if (board[row][i] == num) {
            return 0;
        }
    }
    // 检查列
    for (int j = 0; j < N; j++) {
        if (board[j][col] == num) {
            return 0;
        }
    }
    // 检查3x3子矩阵
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int m = 0; m < 3; m++) {
        for (int n = 0; n < 3; n++) {
            if (board[m + startRow][n + startCol] == num) {
                return 0;
            }
        }
    }
    return 1;
}
// 检查数独矩阵的定义是否满足
int checkBoardDefinition(int board[N][N]) {
    int rowUsed[N][N] = { 0 };
    int colUsed[N][N] = { 0 };
    int blockUsed[N][N] = { 0 };

    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            int num = board[row][col];
            if (num != 0) {
                if (rowUsed[row][num - 1]) {
                    printf("False: Invalid initial Sudoku matrix!\n");
                    printf("The number %d in the row %d has been used!\n", num, row + 1);
                    printf("No solution!\n");
                    return 0;
                }
                if (colUsed[col][num - 1]) {
                    printf("False: Invalid initial Sudoku matrix!\n");
                    printf("The number %d in the col %d has been used!\n", num, col + 1);
                    printf("No solution!\n");
                    return 0;
                }
                int blockIndex = (row / 3) * 3 + (col / 3);
                if (blockUsed[blockIndex][num - 1]) {
                    printf("False: Invalid initial Sudoku matrix!\n");
                    printf("The number %d in the block %d has been used!\n", num, blockIndex + 1);
                    printf("No solution!\n");
                    return 0;
                }
                rowUsed[row][num - 1] = 1;
                colUsed[col][num - 1] = 1;
                blockUsed[blockIndex][num - 1] = 1;
            }
        }
    }
    return 1;
}
// 解数独
int solveBoard(int board[N][N]) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if (board[row][col] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (isValid(board, row, col, num)) {
                        board[row][col] = num;
                        if (solveBoard(board)) {
                            return 1;
                        }
                        board[row][col] = 0;
                    }
                }
                return 0;
            }
        }
    }
    return 1;
}
int main() {
    int board[N][N] = { {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");
    printBoard(board);
    int initialIsValid = checkBoardDefinition(board); // 检查数独矩阵的定义
    if (!initialIsValid) {
    }
    else {
        if (solveBoard(board)) {
            printf("True: Valid initial Sudoku matrix!\n");
            printf("The solution of Sudoku matrix:\n");
            printBoard(board);
        }
        else {
            printf("True: Valid initial Sudoku matrix, but no solution!\n");
        }
    }
    return 0;
}