#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define range9(x) for(int x = 0; x < 9; x ++)
#define range81() for(int i = 0; i < 9; i ++) for(int j = 0; j < 9; j ++)
struct Sudoku{
    int inc[9][9];
};

#define MAXSIZE 1000
struct Sudoku M_Sudoku[MAXSIZE];
int tp=0;

void sudokuClear(struct Sudoku *a){range81()a->inc[i][j] = 0;}
void sudokuCopy(struct Sudoku src, struct Sudoku *dst){range81()dst->inc[i][j] = src.inc[i][j];}
void sudokufromArray(int src[9][9], struct Sudoku *dst){range81()dst->inc[i][j] = src[i][j];}
void sudokuPrint(struct Sudoku a){
    range9(i){
        if(!(i % 3)) putchar('\n');
        range9(j){
            if(!(j % 3)) putchar(' ');
            if(!a.inc[i][j])
                putchar('.');
            else 
                putchar(a.inc[i][j] + 48);
            putchar(' ');
        }
        putchar('\n');
    }
}
void initRandomSeed(){srand(time(NULL));}
struct Sudoku sudokuRandomGenerate(unsigned int fill){// %
    fill %= 101;
    struct Sudoku *res = M_Sudoku + tp++;
    range81()
        if(rand()%100 <= fill)
            res->inc[i][j] = rand() % 9 + 1;
        else 
            res->inc[i][j] = 0;
    return *res;
}
struct Sudoku tags;
int tag(struct Sudoku *a, int i, int j, int x, int y, struct Sudoku *tags){
    if(i == x && j == y) return 0;
    if(a->inc[i][j] && a->inc[i][j] == a->inc[x][y]){
        printf("False:repetition found in (%d,%d) and (%d,%d) with the number {%d}\n", i+1, j+1, x+1, y+1, a->inc[x][y]);
        return 1;
    }
    tags->inc[x][y] |= (1 << a->inc[i][j]);
    return 0;
}
int tagPoint(struct Sudoku *a, int i, int j, struct Sudoku *tags){
    range9(k)
        if(tag(a, i, j, i, k, tags)||tag(a, i, j, k, j, tags)||tag(a, i, j, i/3*3+k/3, j/3*3+k%3, tags))
        return 1;
    return 0;
}
int tagsInit(struct Sudoku *a, struct Sudoku *tags){
    range81()
        tags->inc[i][j] |= (1 << a->inc[i][j]);
    range81()
        if(a->inc[i][j] && tagPoint(a, i, j, tags))
            return 1;
}
int sudokuJudge(struct Sudoku a){
    struct Sudoku tags;
    sudokuClear(&tags);
    if(tagsInit(&a, &tags)) return 1;
    printf("True:Valid initial Sudoku matrix!\n");
    return 0;
}
void tagFindLeast(struct Sudoku *a, int *x, int *y, struct Sudoku *tags){
    int minv = 10;
    *x = *y = 0;
    range81()
        if(!(a->inc[i][j])){
            int cnt = 0;
            range9(k)
                cnt += !((tags->inc[i][j] >> (k+1)) & 1);
            if(cnt < minv && cnt != 0)
                minv = cnt,
                *x = i,
                *y = j;
        }

}
struct Sudoku *sudokuFill__(struct Sudoku *a, int unfillednum, struct Sudoku *tags){
    struct Sudoku *pres, *t_tags;
    if(!unfillednum){
        pres = M_Sudoku + tp ++;
        sudokuCopy(*a, pres);
        return pres;
    }
    int m=0, n=0;
    tagFindLeast(a, &m, &n, tags);
    range9(i)
        if(!((tags->inc[m][n] >> (i+1)) & 1)){
            t_tags = M_Sudoku + tp ++;
            sudokuCopy(*tags, t_tags);
            a->inc[m][n] = i+1;
            tagPoint(a, m, n, t_tags);
            // printf("step:%d:[%d %d]:%d\n", unfillednum, m+1, n+1, i+1);
            // sudokuPrint(*a);
            // getchar();
            pres = sudokuFill__(a, unfillednum - 1, t_tags);
            if(pres)
                return pres;
            a->inc[m][n] = 0;
            tp --;
        }
    return NULL;
}
struct Sudoku *sudokuFill(struct Sudoku *a){
    struct Sudoku tags, res, *pres;
    sudokuClear(&tags);
    if(tagsInit(a, &tags)) return NULL;
    int unfillednum = 0;
    range81()
        if(!a->inc[i][j])
            unfillednum ++;
    return sudokuFill__(a, unfillednum, &tags);
}
int main(){
    clock_t st, end;
    st=clock();
    initRandomSeed();
    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}};
    struct Sudoku a;
    sudokufromArray(board, &a);
    printf("The original Sudoku matrix: \n");
    sudokuPrint(a);
    if(sudokuJudge(a)){
        printf("No solution!\n");
        return 0;
    }
    struct Sudoku *pres = sudokuFill(&a);
    if(!pres){
        printf("No solution!\n");
        return 0;
    }
    printf("The solution of Sudoku matrix:\n");
    sudokuPrint(*pres);
    end=clock();
    printf("dur:%.1lfms\n", ((double)end-st)/CLOCKS_PER_SEC*1000);
}