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

void format(int board[9][9]) { 
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d ", board[i][j]);
            if ((j + 1) % 3 == 0 && j != 8) {
                printf("| ");
            }
        }
        if ((i + 1) % 3 == 0 && i != 8) {
            printf("\n---------------------\n");
        }
        else { printf("\n"); }
    }
}

bool panduan(int board[9][9]) {
    
    for (int i = 0; i < 9; i++) {
        bool row[10] = { 0 }, col[10] = { 0 }, block[10] = { 0 }; 
        for (int j = 0; j < 9; j++) {
           
            if (board[i][j] != 0) {
                if (row[board[i][j]]) {
                    printf("The number %d in row %d has been used!\n", board[i][j], i);
                    return false;
                }
                row[board[i][j]] = true;
            }
            
            if (board[j][i] != 0) {
                if (col[board[j][i]]) {
                    printf("The number %d in column %d has been used!\n", board[j][i], i);
                    return false;
                }
                col[board[j][i]] = true;
            }
           
            int blockRow = 3 * (i / 3), blockCol = 3 * (i % 3);
            if (board[blockRow + j / 3][blockCol + j % 3] != 0) {
                if (block[board[blockRow + j / 3][blockCol + j % 3]]) {
                    printf("The number %d in block %d has been used!\n",
                        board[blockRow + j / 3][blockCol + j % 3], (i / 3) * 3 + (i % 3));
                    return false;
                }
                block[board[blockRow + j / 3][blockCol + j % 3]] = true;
            }
        }
    }
    return true;
}


bool jie(int board[9][9]) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == 0) { 
                for (int num = 1; num <= 9; num++) {
                    board[row][col] = num; 
                    if (panduan(board)) { 
                        if (panduan(board)) {
                            return true;
                        }
                    }
                    board[row][col] = 0; 
                }
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int board[9][9] = { {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}};
    void format(int board[9][9]);

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

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

    return 0;



}