数独计算器
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.

313 lines
10 KiB

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream File_Input;
ofstream File_Output;
struct Sudoku_Data { //一个宫格的内容
unsigned char Data; //数字1~9 0表示未完成
bool May[9]; //假设数
};
struct Try_Point { //假设链上的节点
unsigned char Block_num; //被假设的宫格编号
unsigned char Point_num; //当前正在被假设的item编号
vector <unsigned char> item; //节点中的所有假设数
};
struct Sudoku_Data Base[81]; //全部81个宫格
struct Sudoku_Data Backup[81]; //进行假设的时候暂存使用
unsigned char Addr_Kind[3][9][9]; //行列宫对应的位置表
unsigned char Addr_Block[81][3]; //宫格所在行列宫的编号
vector <struct Try_Point> Try; //假设链
struct Try_Point Empty_Point; //空的假设节点
bool display; //决定Solve_Output时是否输出
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 by Dnomd343"<<endl<<endl;
Reinput:;
Data_Input();
cout<<"The Input Data:"<<endl<<endl;
for (int i = 0; i < 81; i++) {
if (Base[i].Data == 0) {
cout<<"- ";
} else {
cout<<int(Base[i].Data)<<" ";
}
if (i % 3 == 2) {cout<<" ";}
if (i % 9 == 8) {cout<<endl;}
if (i % 27 == 26) {cout<<endl;}
}
cout<<endl;
cout<<"0. Go Back and Edit the Data"<<endl;
cout<<"1. Just Search all the Cases"<<endl;
cout<<"2. Show all Solutions One by One"<<endl;
cout<<endl<<"Select a mode and then Continue : ";
cin>>dat;
cin.get();
if (dat == 1) {
display=false;
} else if (dat == 2) {
display=true;
} else {
goto Reinput;
}
cout<<"Please Wait..."<<endl<<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 = 0;
char dat;
Next:;
cout<<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 (int i = 0; i < 81; i++) {
if (i == num) {
cout<<"_"<<" ";
} else {
if (Base[i].Data == 48) {
cout<<"?"<<" ";
} else {
cout<<int(Base[i].Data)<<" ";
}
}
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)) { // 0~9
Base[num].Data = int(dat - 48);
if (num <= 79) {num++;}
goto Next;
} else { //其他
goto Next;
}
}
void Solve_Output() { //命令行模式下显示数独答案
if (display == true) { //确认是否处于输出模式
cout<<endl;
for (int i = 0; i < 81; i++) {
cout<<int(Base[i].Data)<<" ";
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;
}
char dat[82];
for (int i = 0; i < 81; i++) {dat[i] = Base[i].Data + 48;}
File_Output<<dat<<endl; //将结果保存到文件中
}
unsigned int Calculate() { //主计算函数
unsigned char i;
int Solve_num = 0;
File_Output.open("Sudoku_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 < 81; i++) {Backup[i] = Base[i];} //备份数据 假设时暂存
Create_New_Point(); //创建假设链根节点
while (1 == 1) {
for (i = 0; i < Try.size(); i++) { //装载假设链
Base[Try[i].Block_num].Data = Try[i].item[Try[i].Point_num];
}
Engine(); //进行排除运算
if (Check_Error() == 1) { //当前假设错误
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 < 81; 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 < 9; 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 < 81; i++) {
if (Base[i].Data == 0) {return i;}
}
return 0; //没有未确定宫格
}
bool Check_Error() { //检查数独是否存在错误
unsigned char kind, num, add, item;
for (kind = 0; kind < 3; kind++) { //分别扫描行列宫
for (num = 0; num < 9; num++) {
for (item = 1; item <= 9; item++) {
add = 0;
for (unsigned char k = 0; k < 9; k++) {
if (Base[Addr_Kind[kind][num][k]].Data == item) {add++;}
}
if (add >= 2) {return true;} //若一组行列宫中存在两个相同的数 -> 错误退出
}
}
}
for (num = 0; num < 81; num++) { //扫描全部宫格
if (Base[num].Data == 0) { //若未完成
add = 0;
for (unsigned char k = 0; k < 9; 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 < 81; 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 < 3; kind++) { //分别扫描行列宫
for (num = 0; num < 9; num++) {
for (item = 0; item < 9; item++) {
add = 0;
for(unsigned char k = 0; k < 9; 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 < 81; num++) { //遍历所有宫格
if (Base[num].Data != 0) { //若该宫格已完成
for (kind = 0; kind < 3; kind++) { //分别扫描行列宫
for (item = 0; item < 9; 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 < 9; i++) { //初始化行与列的位置表
for (j = 0; j < 9; j++) {
Addr_Kind[0][i][j] = i * 9 + j;
Addr_Kind[1][i][j] = j * 9 + i;
}
}
for (x = 0; x < 3; x++) { //初始化九宫格的位置表
for (y = 0; y < 3; y++) {
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
Addr_Kind[2][y*3 + x][j*3 + i] = (y*3 + j) * 9 + (x*3 + i);
}
}
}
}
for (i = 0; i < 3; i++) { //初始化宫格所在行列宫的编号
for (x = 0; x < 9; x++) {
for (y = 0; y < 9; y++) {
Addr_Block[Addr_Kind[i][x][y]][i] = x;
}
}
}
for (i = 0; i < 81; i++) { //清空所有假设数
for (j = 0; j < 9; j++) {
Base[i].May[j] = true;
}
}
for (i = 0; i < 81; i++) {Base[i].Data = 0;} //清空所有数字
}