/*-------------------*/
/*实验：数独矩阵------*/
/*4. 对一个不完整的“数独矩阵”进行判断，如果满足“数独矩阵”则补充完整，*/
/*使之成为一个完整的“数独矩阵”：*/
/*-------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void randseedInit(){
    srand(time(NULL));
}
void printBoad(int _board[9][9]){
	int i,j; 
    for ( i = 0; i < 9;i++){
        if(!(i%3))printf("|-----------------------|\n");
        for ( j = 0; j < 9;j++){
            if(!(j%3))
                printf("| ");
            if(_board[i][j]==0)
                printf(". ");
            else 
                printf("%d ", _board[i][j]);
        }
        printf("|\n");
    }
    printf("|-----------------------|\n");
}
void makeNSeq(int _seq[],int n){//产生1-n的不重复序列（传入一个数组名指针）
    int ct[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
    int i;
    for (i = 0; i < n; i++) {
        int t = rand() % n;
        while(ct[t=rand() % n]);
        ct[t]++;
        _seq[i] = t+1;
    }
}
void initBoard(int _board[9][9]){
	int i,j;
    for ( i = 0; i < 9;i++)
        for ( j = 0; j < 9;j++)
            _board[i][j] = 0;
}
void makeRandomBoard(int _board[9][9]){
    initBoard(_board);
    int i_1,i,idx;
    for ( i_1 = 0; i_1 < 3;i_1++){
        int seq[9];
        makeNSeq(seq, 9);
        for ( i = 0; i < 3;i++){
            int where[9];
            makeNSeq(where, 9);
            for ( idx = 0; idx < 3;idx++){
                _board[i_1 * 3 + i][where[idx+i*3]-1] = seq[idx+i*3];
            }
        }
    }
}
void printWhyInvalid(int num,int is_col,int index,int *valid,int ndpt){
    if(*valid){
        if(ndpt)printf("False:Invalid initial Sudoku matrix!\n      The number %d in the %s %d has been used!\n", num, (is_col ? "col" : "block"), index);
        *valid = 0;
    };
}
int whoBeUsedInSeq(int seq[9]){
    int ct[10]={0,0,0,0,0,0,0,0,0,0};
    int i;
    for ( i = 0; i < 9;i++){
        ct[seq[i]]++;
    }
    for (i = 1; i < 10;i++){
        if(ct[i]>1)
            return i;
    }
    return 0;
}
void matrixT(int _board[9][9],int _output[9][9]){
	int i,j;
    for (i = 0; i < 9;i++)
        for ( j = 0; j < 9;j++)
            _output[j][i] = _board[i][j];
}
void resortByBlock(int _board[9][9], int _output[9][9]) {
	int i,j;
    for ( i = 0; i < 9;i++){
        int p1x = i / 3;
        int p1y = i % 3;
        for (j = 0; j < 9; j++){
            int p2x = j / 3;
            int p2y = j % 3;
            _output[i][j] = _board[p1x * 3 + p2x][p1y * 3 + p2y];
        }
    }
}
int judgeValid(int _board[9][9],int ndpt){
    int valid = 1;
    int boardT[9][9];
    int boardB[9][9];
    matrixT(_board, boardT);
    resortByBlock(_board, boardB);
    int i;
    for ( i = 0; i < 9;i++){
        int who = whoBeUsedInSeq(boardT[i]);
        if(who)
            printWhyInvalid(who, 1, i+1, &valid,ndpt);
        who = whoBeUsedInSeq(boardB[i]);
        if(who)
            printWhyInvalid(who, 0, i+1, &valid,ndpt);
        who = whoBeUsedInSeq(_board[i]);
        if(who)
            valid = 0;
    }
    return valid;
}
int try(int _b[9][9],int where[]){
    int w = where[0];
    if(!judgeValid(_b,0))
        return 0;
    if(w==-1){
        printf("The Solution of Sudoku Matrix:\n");
        printBoad(_b);
        return 1;
    }
    int n,i,j;
    for ( n = 1; n <= 9;n++){
        int _bt[9][9];
        for ( i = 0; i < 9;i++)
            for ( j = 0; j < 9;j++)
                _bt[i][j] = _b[i][j];
        _bt[w / 9][w % 9] = n;
        if(try(_bt, &where[1])){
            return 1;
        }
    }
    return 0;
}
int solve(int _board[9][9]){
    int idx = 0;
    int where[81];
    int _b[9][9];
    int i,j;
    for ( i = 0; i < 9;i++)
        for ( j = 0; j < 9;j++)
            _b[i][j] = _board[i][j];
    for ( i = 0; i < 81;i++)
        where[i] = -3;
    int pos = 0;
    while (pos < 81) {
        if (!_b[pos / 9][pos % 9]){
            where[idx]=pos;
            idx++;
        }
        pos++;
    }
    where[idx] = -1;
    if(try(_b, where)){
        
        return 1;
    }
    else{
        printf("No Solution!\n");
         return 0;
    };
}
int main(){
    randseedInit();
    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}};
    printBoad(board);
    solve(board);
}