#include <stdio.h>


int board0[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}};

int board1[9][9] = {{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}};

int board2[9][9] = {{5, 2, 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}};
int err_group=0,err_num=0;

int check_submatrix(int * ptr){
    int bottle[10]={0};
    int * cur_ptr=ptr;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            bottle[*(cur_ptr+j)]++;
            //printf("%d ",*(cur_ptr+j));
        }
        //printf("\n");
        cur_ptr+=9;
    }
    for(int i=1;i<=9;i++){
        //printf("%d",bottle[i]);
        if(bottle[i]>1){
            err_num = i;
            return 0;
        }
    }
    return 1;
}

int check_col(int * ptr){
    int bottle[10]={0};
    int * cur_ptr=ptr;
    for(int i=0;i<9;i++){
        bottle[* cur_ptr]++;
        //printf("%d \n",* cur_ptr);
        cur_ptr+=9;
    }
    for(int i=1;i<=9;i++){
        //printf("%d",bottle[i]);
        if(bottle[i]>1){
            err_num = i;
            return 0;
        }
    }
    return 1;
}

int check_row(int * ptr){
    int bottle[10]={0};
    int * cur_ptr=ptr;
    for(int i=0;i<9;i++){
        bottle[* cur_ptr]++;
        //printf("%d ",* cur_ptr);
        cur_ptr++;
    }
    for(int i=1;i<=9;i++){
        //printf("%d",bottle[i]);
        if(bottle[i]>1){
            err_num = i;
            return 0;
        }
    }
    return 1;
}

int check_whole(int * ptr,int output_on){
    for(int i=0;i<9;i+=3){
        for(int j=0;j<9;j+=3){
            if(!check_submatrix(&ptr[i*9+j])){
                if(output_on){
                    printf("False:Invalid initial Sudoku matrix!\n");
                    printf("The number %d in the block %d has been used!",err_num,i+j/3+1);
                }
                return 0;
            }
        }
    }

    for(int i=0;i<9;i++){
        if(!check_row(&ptr[i*9+0])){
            if(output_on) {
                printf("False:Invalid initial Sudoku matrix!\n");
                printf("The number %d in the col %d has been used!", err_num, i);
            }
            return 0;
        }
    }

    for(int i=0;i<9;i++){
        if(!check_col(&ptr[i])){
            if(output_on){
                printf("False:Invalid initial Sudoku matrix!\n");
                printf("The number %d in the row %d has been used!",err_num,i);
            }
            return 0;
        }
    }
    if(output_on){
        printf("True:Valid initial Sudoku matrix!\n");
    }
    return 1;
}

int dfs(int * ptr,int * start_pos){

    for(int * i=ptr;i<start_pos+81;i++){
        if((* i)==0){
            for(int j=1;j<=9;j++){
                * i = j;
                if(check_whole(start_pos,0) && dfs(i+1,start_pos))return 1;
            }
            * i =0;
            return 0;
        }
    }
    return 1;
}

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

int Sudoku_validator(int grid[9][9]){
    printf("The original Sudoku matrix:\n");
    printGrid(grid);

    check_whole(&grid[0][0],1);

    if(dfs(&grid[0][0],&grid[0][0])) {

        printf("The solution of Sudoku matrix:\n");
        printGrid(grid);
    }
    else printf("No solution");
    return 0;
}
int main(void) {
    Sudoku_validator(board2);

}