shudujuzhen/4

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

#define SIZE 9

bool isValidSudoku(int ma[SIZE][SIZE]);
bool isSafe(int ma[SIZE][SIZE], int row, int col, int num);
bool solveSudoku(int ma[SIZE][SIZE]);
void printMatrix(int ma[SIZE][SIZE]);

void printMatrix(int ma[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%c ", ma[i][j] != 0 ? '1' + ma[i][j] - 1 : '.');
            if (j < SIZE - 1) {
                if (j % 3 == 2) {
                    printf("| ");
                } else {
                    printf(" ");
                }
            }
        }
        if (i < SIZE - 1) {
            if (i % 3 == 2) {
                printf("\n---------------------\n");
            } else {
                printf("\n");
            }
        } else {
            printf("\n");
        }
    }
}

bool isValidSudoku(int ma[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (ma[i][j] != 0) {
                for (int k = 0; k < SIZE; k++) {
                    if (ma[i][k] == ma[i][j] && k != j) return false;
                    if (ma[k][j] == ma[i][j] && k != i) return false;
                }
                int startRow = i - i % 3;
                int startCol = j - j % 3;
                for (int p = 0; p < 3; p++) {
                    for (int q = 0; q < 3; q++) {
                        if (ma[p + startRow][q + startCol] == ma[i][j] &&
                            (p + startRow != i || q + startCol != j)) {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return true;
}

bool isSafe(int ma[SIZE][SIZE], int row, int col, int num) {
    for (int k = 0; k < SIZE; k++) {
        if (ma[row][k] == num) return false;
        if (ma[k][col] == num) return false;
    }
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int p = 0; p < 3; p++) {
        for (int q = 0; q < 3; q++) {
            if (ma[p + startRow][q + startCol] == num) return false;
        }
    }
    return true;
}

bool solveSudoku(int ma[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (ma[i][j] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (isSafe(ma, i, j, num)) {
                        ma[i][j] = num;
                        if (solveSudoku(ma)) {
                            return true;
                        } else {
                            ma[i][j] = 0;
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main() {
    int ma[SIZE][SIZE] = {
        {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 ");
    printMatrix(ma);

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

    return 0;
}