#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
ifstream File_Input;
ofstream File_Output;

struct Sudoku_Class{  //一个宫格的内容
    unsigned char Data;  //数字1~9，0表示未完成
    bool May[9];  //假设数
};
struct Try_Point_Class{  //假设链上的节点
    unsigned char Block_Num;  //被假设的宫格编号
    unsigned char Point_Num;  //当前正在被假设的Item编号
    vector <unsigned char> Item;  //节点中的所有假设数
};

struct Sudoku_Class Base[81];  //全部81个宫格
struct Sudoku_Class Backup[81];  //进行假设的时候暂存使用
unsigned char Addr_Kind[3][9][9];  //行列宫对应的位置表
unsigned char Addr_Block[81][3];  //宫格所在行列宫的编号
vector <struct Try_Point_Class> Try;  //假设链
struct Try_Point_Class Empty_Point;  //空的假设节点
unsigned char Mode;

void Init();
void Analyse();
void Engine();
bool Check_Compete();
bool Check_Error();
void Create_New_Point();
void Solve_Output();
bool Try_Next();
void Data_Input();
unsigned int Calculate();
unsigned char Next_Empty_Block(unsigned char Start);
void Init_Point(unsigned char Block_Num,unsigned char Point_Num);

int main(){
    unsigned int Solve_Num,Dat;
    Init();
    cout<<"Welcome to Sudoku-Calculator!"<<endl;
    Restart:;
    Data_Input();
    cout<<endl<<"The Input Data:"<<endl;
    Solve_Output();
    cout<<"0.Go back and edit the data"<<endl;
    cout<<"1.Show all solutions one by one"<<endl;
    cout<<"2.Find the number of solutions in all cases"<<endl;
    cout<<"3.Find all solutions and output them to file"<<endl;
    cout<<endl<<"Select a mode and continue : ";
    cin>>Dat;
    if((Dat>=1)&&(Dat<=3)){Mode=Dat;}else{goto Restart;}
    cout<<"The mode is "<<int(Mode)<<" ,Press ENTER to Start Calculate...";
    cin.get();cin.get();
    cout<<"Please Wait..."<<endl;
    Solve_Num=Calculate();
    if(Solve_Num==0){
        cout<<"Error or No solve!!!"<<endl;
    }
    else{
        cout<<"Found "<<Solve_Num<<" Solution"<<endl;
    }
    cout<<"Press ENTER to Exit...";
    cin.get();
    return 0;
}
void Data_Input(){  //接受命令行下输入数独内容
    unsigned int Num,i;
    char Dat;
    char Data[82];
    cout<<"Please Input the Data:"<<endl;
    Num=0;
    Next:;
    cout<<endl<<endl<<endl<<endl<<endl<<endl;
    cout<<"You can Input the Command and then Press the ENTER"<<endl;
    cout<<"'+' : Next Block    '-' : Last Block"<<endl;
    cout<<"'*' : Next Line     '/' : Last Line"<<endl;
    cout<<"'=' : Compete       '0' : Empty Block"<<endl;
    cout<<"'1' to '9' : The Number"<<endl<<endl;
    for(i=0;i<=80;i++){
        Data[i]=Base[i].Data+48;
    }
    Data[81]=0;
    for(i=0;i<=80;i++){
        if(i==Num){
            cout<<"_"<<" ";
        }
        else{
            if(Data[i]=='0'){cout<<"?"<<" ";}else{cout<<Data[i]<<" ";}
        }
        if(i%3==2){cout<<" ";}
        if(i%9==8){cout<<endl;}
        if(i%27==26){cout<<endl;}
    }
    cin>>Dat;
    if(Dat==43){  // ‘+’
        if(Num<=79){Num++;}
    	goto Next;
    }
    else if(Dat==45){  // '-'
        if(Num>=1){Num--;}
        goto Next;
    }
    else if(Dat==42){  // '*'
        if(Num<=71){Num=Num+9;}
        goto Next;
    }
    else if(Dat==47){  // '/'
        if(Num>=9){Num=Num-9;}
        goto Next;
    }
    else if(Dat==61){}  // '='
    else if((Dat>=48)&&(Dat<=57)){
        Base[Num].Data=int(Dat-48);
        if(Num<=79){Num++;}
        goto Next;
    }
    else{goto Next;}
}
void Solve_Output(){
    unsigned char i;
    char Data[82];
    if(Mode==2){return;}
    for(i=0;i<=80;i++){Data[i]=Base[i].Data+48;}
    Data[81]=0;
    if(Mode==0){
        cout<<endl;
        for(i=0;i<=80;i++){
            if(Data[i]==48){cout<<"-"<<" ";}else{cout<<Data[i]<<" ";}
            if(i%3==2){cout<<" ";}
            if(i%9==8){cout<<endl;}
            if(i%27==26){cout<<endl;}
        }
    }
    else if(Mode==1){
        cout<<endl;
        for(i=0;i<=80;i++){
            cout<<Data[i]<<" ";
            if(i%3==2){cout<<" ";}
            if(i%9==8){cout<<endl;}
            if(i%27==26){cout<<endl;}
        }
        cout<<"Press ENTER to Show Next Solution...";
        cin.get();
        cout<<endl;
    }
    else if(Mode==3){
        File_Output<<Data<<endl;
    }
}
unsigned int Calculate(){  //主计算函数
    unsigned char i;
    int Solve_Num=0;
    if(Mode==3){File_Output.open("Data_Output.txt");}
    Engine();  //初步排除运算
    if(Check_Error()==true){File_Output.close();return 0;}  //输入的数独有误
    if(Check_Compete()==true){Solve_Output();File_Output.close();return 1;}  //输入的数独已完成
    for(i=0;i<=80;i++){Backup[i]=Base[i];}  //备份数据 假设时暂存
    Create_New_Point();  //创建假设链根节点
    while(1){
        for(i=0;i<=(Try.size()-1);i++){  //装载假设链
            Base[Try[i].Block_Num].Data=Try[i].Item[Try[i].Point_Num];
        }
        Engine();  //进行排除运算
        if(Check_Error()==true){  //当前假设错误
            if(Try_Next()==false){break;}  //没有下一个假设，则该数独无解，退出
        }
        else{  //当前假设可能正确
            if(Check_Compete()==false){  //若仍未完成，则创建新的假设节点
                Create_New_Point();
            }
            else{  //已完成
                Solve_Output();
                Solve_Num++;  //答案数目+1
                if(Try_Next()==false){break;}  //没有下一个假设，求解完成，退出
            }
        }
    }
    File_Output.close();
    return Solve_Num;
}
bool Try_Next(){  //当前假设错误，装载下一个假设
    unsigned char i;
    while((Try[Try.size()-1].Point_Num>=(Try[Try.size()-1].Item.size()-1))){
        if(Try.size()==1){return false;}
        Try.resize(Try.size()-1);
    }
    Try[Try.size()-1].Point_Num++;  //假设链末节点指向下一个Item
    for(i=0;i<=80;i++){  //将备份数据重新装载
        Base[i]=Backup[i];
    }
    return true;  //成功
}
void Create_New_Point(){  //创建新的假设链节点
    Try.push_back(Empty_Point);
    if(Try.size()==1){  //若为根节点
        Init_Point(Next_Empty_Block(0),0);  //从第一格开始搜索未完成宫格
    }
    else{  //若不是根节点
        Init_Point(Next_Empty_Block(Try[Try.size()-2].Block_Num+1),Try.size()-1);  //从上一节点指向的宫格开始搜索未完成宫格
    }
}
void Init_Point(unsigned char Block_Num,unsigned char Point_Num){  //初始化假设链节点  Block_Num->被假设宫格的编号  Point_Num->节点的编号
    unsigned char i;
    Try[Point_Num].Block_Num=Block_Num;
    for(i=0;i<=8;i++){
        if(Base[Try[Point_Num].Block_Num].May[i]==true){  //遍历目标宫格的所有假设数并加入到该节点的Item中
            Try[Point_Num].Item.push_back(i+1);
        }
    }
    Try[Point_Num].Point_Num=0;  //指向Item中的第一个假设数
}
unsigned char Next_Empty_Block(unsigned char Start){  //找到下一个未确定答案的宫格并返回其编号
    unsigned char i;
    for(i=Start;i<=80;i++){
        if(Base[i].Data==0){return i;}
    }
    return 0;  //没有未确定宫格
}
bool Check_Error(){  //检查数独是否存在错误
    unsigned char kind,num,add,item;
    for(kind=0;kind<=2;kind++){  //分别扫描行列宫
        for(num=0;num<=8;num++){
            for(item=1;item<=9;item++){
                add=0;
                for(unsigned char k=0;k<=8;k++){
                    if(Base[Addr_Kind[kind][num][k]].Data==item){add++;}
                }
                if(add>=2){return true;}  //若一组行列宫中存在两个相同的数 -> 错误退出
            }
        }
    }
    for(num=0;num<=80;num++){  //扫描全部宫格
        if(Base[num].Data==0){  //若未完成
            add=0;
            for(unsigned char k=0;k<=8;k++){  //遍历其所有假设数
                if(Base[num].May[k]==true){add++;}
            }
            if(add==0){return true;}  //没有可能的数 -> 错误退出
        }
    }
    return false;  //暂时未发现错误
}
bool Check_Compete(){  //判断数独是否完成
    unsigned char i;
    for(i=0;i<=80;i++){
        if(Base[i].Data==0){return false;}
    }
    return true;
}
void Engine(){  //使用排除法
    unsigned char kind,num,item,add,dat;
    bool Could_Solve;
    Again:;
    Analyse();  //每次排除前应先消去假设数
    Could_Solve=false;
    for(kind=0;kind<=2;kind++){  //分别扫描行列宫
        for(num=0;num<=8;num++){
            for(item=0;item<=8;item++){
                add=0;
                for(unsigned char k=0;k<=8;k++){
                    if((Base[Addr_Kind[kind][num][k]].Data==0)&&(Base[Addr_Kind[kind][num][k]].May[item]==true)){add++;dat=k;}  //记录一组行列宫中的可能数
                }
                if(add==1){Base[Addr_Kind[kind][num][dat]].Data=item+1;Could_Solve=true;}  //若仅有唯一可能数，则该宫格答案确定
            }
        }
        if(Could_Solve==true){goto Again;}  //一直循环直到没有排除对象
    }
}
void Analyse(){  //消去假设数
    unsigned char num,kind,item;
    for(num=0;num<=80;num++){  //遍历所有宫格
        if(Base[num].Data!=0){  //若该宫格已完成
            for(kind=0;kind<=2;kind++){  //分别对行列宫操作
                for(item=0;item<=8;item++){
                    Base[Addr_Kind[kind][Addr_Block[num][kind]][item]].May[Base[num].Data-1]=false;  //消去同行同列同宫的假设数
                }
            }
        }
    }
}
void Init(){  //初始化容器
    unsigned char i,j,x,y;
    for(i=0;i<=8;i++){  //初始化行与列的位置表
        for(j=0;j<=8;j++){
            Addr_Kind[0][i][j]=i*9+j;
            Addr_Kind[1][i][j]=j*9+i;
        }
    }
    for(x=0;x<=2;x++){  //初始化九宫格的位置表
        for(y=0;y<=2;y++){
            for(i=0;i<=2;i++){
                for(j=0;j<=2;j++){
                    Addr_Kind[2][y*3+x][j*3+i]=(y*3+j)*9+(x*3+i);
                }
            }
        }
    }
    for(i=0;i<=2;i++){  //初始化宫格所在行列宫的编号
        for(x=0;x<=8;x++){
            for(y=0;y<=8;y++){
                Addr_Block[Addr_Kind[i][x][y]][i]=x;
            }
        }
    }
    for(i=0;i<=80;i++){  //清空所有假设数
        for(j=0;j<=8;j++){
            Base[i].May[j]=true;
        }
    }
    for(i=0;i<=80;i++){  //清空所有数字
        Base[i].Data=0;
    }
}