mirror of https://github.com/dnomd343/Sudoku
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
235 lines
8.2 KiB
235 lines
8.2 KiB
#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; //空的假设节点
|
|
|
|
void Init();
|
|
void Analyse();
|
|
void Engine();
|
|
bool Check_Compete();
|
|
bool Check_Error();
|
|
void Create_New_Point();
|
|
void Solve_Output();
|
|
bool Try_Next();
|
|
bool 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(){
|
|
cout<<"Welcome to Sudoku-Calculator by Dnomd343"<<endl;
|
|
cout<<"Please wait..."<<endl;
|
|
Init();
|
|
if(Data_Input()==false){cout<<"Something Wrong!"<<endl;return 0;}
|
|
unsigned int i;
|
|
i=Calculate();
|
|
cout<<"Calculate Compete"<<endl;
|
|
File_Output.open("Compete");
|
|
if(i==0){File_Output<<"Error!!!"<<endl;}
|
|
File_Output.close();
|
|
return 0;
|
|
}
|
|
bool Data_Input(){
|
|
unsigned char i;
|
|
char dat[81];
|
|
File_Input.open("Data_Input.txt");
|
|
File_Input>>dat;
|
|
File_Input.close();
|
|
for(i=0;i<=80;i++){
|
|
Base[i].Data=dat[i]-48;
|
|
if(Base[i].Data>9){return false;}
|
|
}
|
|
return true;
|
|
}
|
|
void Solve_Output(){
|
|
unsigned char i;
|
|
char Data[82];
|
|
for(i=0;i<=80;i++){
|
|
Data[i]=Base[i].Data+48;
|
|
}
|
|
Data[81]=0;
|
|
File_Output<<Data<<endl;
|
|
}
|
|
unsigned int Calculate(){ //主计算函数
|
|
unsigned char i;
|
|
int Solve_Num=0;
|
|
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;
|
|
}
|
|
}
|
|
|