#include <stdio.h>
#include <stdbool.h>
#define N 9
void printSudoku(int sudoku[9][9]) {
    printf("+-------+-------+-------+\n");
    for (int i = 0; i < 9; i++) {
        if (i > 0 && i % 3 == 0) {
            printf("+-------+-------+-------+\n");
        }
        for (int j = 0; j < 9; j++) {
            if (j % 3 == 0) {
                printf("| ");
            }
            printf("%d ", sudoku[i][j]); // 输出数组中的元素
        }
        printf("|\n");
    }
    printf("+-------+-------+-------+\n");
}
// Function to check if a number is already present in the row
bool isSafeRow(int board[N][N], int row, int num) {
    for (int col = 0; col < N; col++) {
        if (board[row][col] == num) {
            return false;
        }
    }
    return true;
}
// Function to check if a number is already present in the column
bool isSafeCol(int board[N][N], int col, int num) {
    for (int row = 0; row < N; row++) {
        if (board[row][col] == num) {
            return false;
        }
    }
    return true;
}
// Function to check if a number is already present in the 3x3 grid
bool isSafeGrid(int board[N][N], int row, int col, int num) {
    int startRow = row - (row % 3);
    int startCol = col - (col % 3);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i + startRow][j + startCol] == num) {
                return false;
            }
        }
    }
    return true;
}
bool isSafe(int board[N][N], int row, int col, int num) {
    return isSafeRow(board, row, num) && isSafeCol(board, col, num) && isSafeGrid(board, row, col, num);
}
bool solveSudoku(int board[N][N]) {
    int row = -1;
    int col = -1;
    bool isEmpty = true;
    // Find an empty cell
    for (int i = 0; i < N && isEmpty; i++) {
        for (int j = 0; j < N && isEmpty; j++) {
            if (board[i][j] == 0) {
                row = i;
                col = j;
                isEmpty = false;
            }
        }
    }
    if (isEmpty) {
        return true;
    }
    for (int num = 1; num <= N; num++) {
        if (isSafe(board, row, col, num)) {
            board[row][col] = num;

            if (solveSudoku(board)) {
                return true;
            }

            board[row][col] = 0;
        }
    }   return false;
}
int main() {
    int sudoku[N][N] = {{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");
    printSudoku(sudoku);
    bool valid = solveSudoku(sudoku);
    if (valid) {
        printf("True: Valid initial Sudoku matrix!\n");

        if (solveSudoku(sudoku)) {
            printf("The solution of Sudoku matrix:\n");
            printSudoku(sudoku);
        } else {
            printf("No solution!\n");
        }
    } else {
        printf("False: Invalid initial Sudoku matrix!\n");
        printf("No solution!\n");
    }
    return 0;
}