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

#define SIZE 9

void print_sudoku(char matrix[][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%c ", matrix[i][j]);
            if (j == 2 || j == 5) {
                printf("| ");
            }
        }
        printf("\n");
        if (i == 2 || i == 5) {
            printf("- - - + - - - + - - -\n");
        }
    }
}

bool is_valid_sudoku(char matrix[][SIZE]) {
    // 检查每一行是否满足数独定义
    for (int i = 0; i < SIZE; i++) {
        bool used[SIZE] = {false};
        for (int j = 0; j < SIZE; j++) {
            char c = matrix[i][j];
            if (c != '.') {
                int index = c - '1';
                if (used[index]) {
                    return false;
                }
                used[index] = true;
            }
        }
    }

    // 检查每一列是否满足数独定义
    for (int j = 0; j < SIZE; j++) {
        bool used[SIZE] = {false};
        for (int i = 0; i < SIZE; i++) {
            char c = matrix[i][j];
            if (c != '.') {
                int index = c - '1';
                if (used[index]) {
                    return false;
                }
                used[index] = true;
            }
        }
    }

    // 检查每个3x3的小方格是否满足数独定义
    for (int block = 0; block < SIZE; block++) {
        int row_start = (block / 3) * 3;
        int col_start = (block % 3) * 3;
        bool used[SIZE] = {false};
        for (int i = row_start; i < row_start + 3; i++) {
            for (int j = col_start; j < col_start + 3; j++) {
                char c = matrix[i][j];
                if (c != '.') {
                    int index = c - '1';
                    if (used[index]) {
                        return false;
                    }
                    used[index] = true;
                }
            }
        }
    }

    return true;
}

bool is_valid(char num, char matrix[][SIZE], int row, int col) {
    // 检查同一行是否有重复数字
    for (int i = 0; i < SIZE; i++) {
        if (matrix[row][i] == num) {
            return false;
        }
    }

    // 检查同一列是否有重复数字
    for (int i = 0; i < SIZE; i++) {
        if (matrix[i][col] == num) {
            return false;
        }
    }

    // 检查所在的3x3小方格是否有重复数字
    int row_start = (row / 3) * 3;
    int col_start = (col / 3) * 3;
    for (int i = row_start; i < row_start + 3; i++) {
        for (int j = col_start; j < col_start + 3; j++) {
            if (matrix[i][j] == num) {
                return false;
            }
        }
    }

    return true;
}

bool backtrack(char matrix[][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (matrix[i][j] == '.') {
                for (char num = '1'; num <= '9'; num++) {
                    if (is_valid(num, matrix, i, j)) {
                        matrix[i][j] = num;
                        if (backtrack(matrix)) {
                            return true;
                        }
                        matrix[i][j] = '.';  // 回溯
                    }
                }
                return false;
            }
        }
    }
    return true;
}

bool solve_sudoku(char matrix[][SIZE]) {
    if (is_valid_sudoku(matrix)) {
        if (backtrack(matrix)) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}

int main() {
    char board0[SIZE][SIZE] = {
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

    char board1[SIZE][SIZE] = {
        {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

    char board2[SIZE][SIZE] = {
        {'5', '2', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

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

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

    printf("\n");

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

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

    printf("\n");

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

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

    return 0;
}