c++实现的简单数独策画器
添加时间:2013-5-30 点击量:
日常平凡挺喜好写小法度的，然则不知道写啥，无意看到关于数独的消息，感觉用小法度实现再合适不过了，网上一搜，有道理，有法度，然则没有找到优良的代码，干脆本身写了一个，固然也不优良，起码本身看得懂。
道理：
1、每个格子可所以1-9的数，n行m列的数断定后，则第n行，第m列，nm地点的”宫“里其他的格子就不克不及是这个数了。
2、刚开端每个格子都有9个”候选数“，慢慢把初始数据添加到终极的格子中，并把响应的格子中的候选数更新，如1所说。
3、开端策画，选出候选数起码的格子，对这些数迭代测试，如把候选数中的第1个添加到终极的格子中。和2一样更新其他格子的候选数列表。
4、3之后天然还是3，所以把3实现为递归要简单一些。并且推敲到本题实际景象最多递归81层，不会栈溢出。并且递归本身还保存了后续所需数据，简化了操纵。
代码注释：
g_currentIndex：格子中已经断定成果的个数（添加到格子中的数的个数，递归的深度），索引默示的，所以0代表已添加1个。
g_affectedFlags：位标记，某次添加数据是否对格子产生影响，回退操纵要应用。
g_candidate：每个格子的候选列表，用bitset的索引默示。第n位为1，代表n是候选数。
g_candidateNum：每个格子的候选个数，为什么不消bitset的count呢？因为速度太慢。
成果截图：
源码：
＃include<iostream>
＃include<set>
＃include<bitset>
＃include<cstring>
＃include<time.h>
using namespace std;
int g_currentIndex=-1;
bitset<81> g_affectedFlags[9][9];
bitset<10> g_candidate[9][9];
int g_candidateNum[9][9];
int resultNum;
const int maxNum=5;
int g_map[9][9]={
{8，0，0，0，0，0，0，0，0}，
{0，0，3，6，0，0，0，0，0}，
{0，7，0，0，9，0，2，0，0}，
{0，5，0，0，0，7，0，0，0}，
{0，0，0，0，4，5，7，0，0}，
{0，0，0，1，0，0，0，3，0}，
{0，0，1，0，0，0，0，6，8}，
{0，0，8，5，0，0，0，1，0}，
{0，9，0，0，0，0，4，0，0}，
};
void AddElement（int row，int column，int num）
{
++g_currentIndex;
g_map[row][column]=num;
int old;
for（int i=0;i<9;++i）
{
if（g_map[row][i]==0 && g_candidate[row][i].test（num））
{
g_candidate[row][i].reset（num）;
--g_candidateNum[row][i];
g_affectedFlags[row][i].set（g_currentIndex）;
}
if（g_map[i][column]==0 && g_candidate[i][column].test（num））
{
g_candidate[i][column].reset（num）;
--g_candidateNum[i][column];
g_affectedFlags[i][column].set（g_currentIndex）;
}
}
int palaceRow=row>2？（row>5？6:3）:0;
int palaceColumn=column>2？（column>5？6:3）:0;
for（int i=0;i<3;++i）
{
for（int j=0;j<3;++j）
{
row=palaceRow+i;
column=palaceColumn+j;
if（g_map[row][column]==0 && g_candidate[row][column].test（num））
{
g_candidate[row][column].reset（num）;
--g_candidateNum[row][column];
g_affectedFlags[row][column].set（g_currentIndex）;
}
}
}
}
void RecoverElement（int row，int column，int num）
{
g_map[row][column]=0;
for（int i=0;i<9;++i）
{
if（g_map[row][i]==0 && g_affectedFlags[row][i].test（g_currentIndex））
{
g_candidate[row][i].set（num）;
++g_candidateNum[row][i];
g_affectedFlags[row][i].reset（g_currentIndex）;
}
if（g_map[i][column]==0 && g_affectedFlags[i][column].test（g_currentIndex））
{
g_candidate[i][column].set（num）;
++g_candidateNum[i][column];
g_affectedFlags[i][column].reset（g_currentIndex）;
}
}
int palaceRow=row>2？（row>5？6:3）:0;
int palaceColumn=column>2？（column>5？6:3）:0;
for（int i=0;i<3;++i）
{
for（int j=0;j<3;++j）
{
row=palaceRow+i;
column=palaceColumn+j;
if（g_map[row][column]==0 && g_affectedFlags[row][column].test（g_currentIndex））
{
g_candidate[row][column].set（num）;
++g_candidateNum[row][column];
g_affectedFlags[row][column].reset（g_currentIndex）;
}
}
}
--g_currentIndex;
}
void Init（）
{
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
g_candidate[i][j].set（）;
g_candidateNum[i][j]=10;
}
}
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
if（g_map[i][j]!=0）
AddElement（i，j，g_map[i][j]）;
}
}
}
bool FindBest（int &row，int &column）
{
int min=999;
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
if（g_map[i][j]==0 && g_candidateNum[i][j]>1 && g_candidateNum[i][j]<min）
{
row=i;
column=j;
min=g_candidateNum[i][j];
}
}
}
if（min==999）
return false;
return true;
}
bool CheckResult（）
{
set<int> elements;
set<int> elements2;
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
elements.（g_map[i][j]）;
elements2.（g_map[j][i]）;
}
if（elements.size（）!=9）
return false;
if（elements2.size（）!=9）
return false;
elements.clear（）;
elements2.clear（）;
}
elements.clear（）;
int row，column;
for（int i=0;i<3;++i）
{
for（int j=0;j<3;++j）
{
row=i3;
column=j3;
for（int k=0;k<9;++k）
{
elements.（g_map[row+k/3][column+k％3]）;
}
if（elements.size（）!=9）
return false;
elements.clear（）;
}
}
return true;
}
void OutputResult（）
{
cout<<endl;
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
cout<<g_map[i][j]<< ;
}
cout<<endl;
}
}
bool Try（）
{
int row，column;
if（!FindBest（row，column））
return true;
for（int i=1;i<10;++i）
{
if（!g_candidate[row][column].test（i））
continue;
AddElement（row，column，i）;
if（Try（））
{
if（g_currentIndex==80 && CheckResult（））
{
cout<<endl<<Result:<<++resultNum<<endl;
OutputResult（）;
if（resultNum>=maxNum）
return false;
}
}
else
return false;
RecoverElement（row，column，i）;
}
return true;
}
int main（）
{
double start，end，cost;
start=clock（）;
Init（）;
Try（）;
if（resultNum）
cout<<endl<<OK!<<endl;
else
cout<<endl<<Wrong Input!<<endl;
end=clock（）;
cost=end-start;
cout<<Costed time:<<cost<<ms<<endl;
char c;
cin>>c;
return 0;
}
其他：
小我感觉这种办法已经到了速度的极限，高手的代码竟然可以或许达到几十毫秒，默示自叹不如!
我用的例子是”史上最难数独“，确切只有一个解，代码中maxNum可以限制显示成果数量。
附其他高手的截图一张：
我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》
日常平凡挺喜好写小法度的，然则不知道写啥，无意看到关于数独的消息，感觉用小法度实现再合适不过了，网上一搜，有道理，有法度，然则没有找到优良的代码，干脆本身写了一个，固然也不优良，起码本身看得懂。
道理：
1、每个格子可所以1-9的数，n行m列的数断定后，则第n行，第m列，nm地点的”宫“里其他的格子就不克不及是这个数了。
2、刚开端每个格子都有9个”候选数“，慢慢把初始数据添加到终极的格子中，并把响应的格子中的候选数更新，如1所说。
3、开端策画，选出候选数起码的格子，对这些数迭代测试，如把候选数中的第1个添加到终极的格子中。和2一样更新其他格子的候选数列表。
4、3之后天然还是3，所以把3实现为递归要简单一些。并且推敲到本题实际景象最多递归81层，不会栈溢出。并且递归本身还保存了后续所需数据，简化了操纵。
代码注释：
g_currentIndex：格子中已经断定成果的个数（添加到格子中的数的个数，递归的深度），索引默示的，所以0代表已添加1个。
g_affectedFlags：位标记，某次添加数据是否对格子产生影响，回退操纵要应用。
g_candidate：每个格子的候选列表，用bitset的索引默示。第n位为1，代表n是候选数。
g_candidateNum：每个格子的候选个数，为什么不消bitset的count呢？因为速度太慢。
成果截图：
源码：
＃include<iostream>
＃include<set>
＃include<bitset>
＃include<cstring>
＃include<time.h>
using namespace std;
int g_currentIndex=-1;
bitset<81> g_affectedFlags[9][9];
bitset<10> g_candidate[9][9];
int g_candidateNum[9][9];
int resultNum;
const int maxNum=5;
int g_map[9][9]={
{8，0，0，0，0，0，0，0，0}，
{0，0，3，6，0，0，0，0，0}，
{0，7，0，0，9，0，2，0，0}，
{0，5，0，0，0，7，0，0，0}，
{0，0，0，0，4，5，7，0，0}，
{0，0，0，1，0，0，0，3，0}，
{0，0，1，0，0，0，0，6，8}，
{0，0，8，5，0，0，0，1，0}，
{0，9，0，0，0，0，4，0，0}，
};
void AddElement（int row，int column，int num）
{
++g_currentIndex;
g_map[row][column]=num;
int old;
for（int i=0;i<9;++i）
{
if（g_map[row][i]==0 && g_candidate[row][i].test（num））
{
g_candidate[row][i].reset（num）;
--g_candidateNum[row][i];
g_affectedFlags[row][i].set（g_currentIndex）;
}
if（g_map[i][column]==0 && g_candidate[i][column].test（num））
{
g_candidate[i][column].reset（num）;
--g_candidateNum[i][column];
g_affectedFlags[i][column].set（g_currentIndex）;
}
}
int palaceRow=row>2？（row>5？6:3）:0;
int palaceColumn=column>2？（column>5？6:3）:0;
for（int i=0;i<3;++i）
{
for（int j=0;j<3;++j）
{
row=palaceRow+i;
column=palaceColumn+j;
if（g_map[row][column]==0 && g_candidate[row][column].test（num））
{
g_candidate[row][column].reset（num）;
--g_candidateNum[row][column];
g_affectedFlags[row][column].set（g_currentIndex）;
}
}
}
}
void RecoverElement（int row，int column，int num）
{
g_map[row][column]=0;
for（int i=0;i<9;++i）
{
if（g_map[row][i]==0 && g_affectedFlags[row][i].test（g_currentIndex））
{
g_candidate[row][i].set（num）;
++g_candidateNum[row][i];
g_affectedFlags[row][i].reset（g_currentIndex）;
}
if（g_map[i][column]==0 && g_affectedFlags[i][column].test（g_currentIndex））
{
g_candidate[i][column].set（num）;
++g_candidateNum[i][column];
g_affectedFlags[i][column].reset（g_currentIndex）;
}
}
int palaceRow=row>2？（row>5？6:3）:0;
int palaceColumn=column>2？（column>5？6:3）:0;
for（int i=0;i<3;++i）
{
for（int j=0;j<3;++j）
{
row=palaceRow+i;
column=palaceColumn+j;
if（g_map[row][column]==0 && g_affectedFlags[row][column].test（g_currentIndex））
{
g_candidate[row][column].set（num）;
++g_candidateNum[row][column];
g_affectedFlags[row][column].reset（g_currentIndex）;
}
}
}
--g_currentIndex;
}
void Init（）
{
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
g_candidate[i][j].set（）;
g_candidateNum[i][j]=10;
}
}
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
if（g_map[i][j]!=0）
AddElement（i，j，g_map[i][j]）;
}
}
}
bool FindBest（int &row，int &column）
{
int min=999;
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
if（g_map[i][j]==0 && g_candidateNum[i][j]>1 && g_candidateNum[i][j]<min）
{
row=i;
column=j;
min=g_candidateNum[i][j];
}
}
}
if（min==999）
return false;
return true;
}
bool CheckResult（）
{
set<int> elements;
set<int> elements2;
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
elements.（g_map[i][j]）;
elements2.（g_map[j][i]）;
}
if（elements.size（）!=9）
return false;
if（elements2.size（）!=9）
return false;
elements.clear（）;
elements2.clear（）;
}
elements.clear（）;
int row，column;
for（int i=0;i<3;++i）
{
for（int j=0;j<3;++j）
{
row=i3;
column=j3;
for（int k=0;k<9;++k）
{
elements.（g_map[row+k/3][column+k％3]）;
}
if（elements.size（）!=9）
return false;
elements.clear（）;
}
}
return true;
}
void OutputResult（）
{
cout<<endl;
for（int i=0;i<9;++i）
{
for（int j=0;j<9;++j）
{
cout<<g_map[i][j]<< ;
}
cout<<endl;
}
}
bool Try（）
{
int row，column;
if（!FindBest（row，column））
return true;
for（int i=1;i<10;++i）
{
if（!g_candidate[row][column].test（i））
continue;
AddElement（row，column，i）;
if（Try（））
{
if（g_currentIndex==80 && CheckResult（））
{
cout<<endl<<Result:<<++resultNum<<endl;
OutputResult（）;
if（resultNum>=maxNum）
return false;
}
}
else
return false;
RecoverElement（row，column，i）;
}
return true;
}
int main（）
{
double start，end，cost;
start=clock（）;
Init（）;
Try（）;
if（resultNum）
cout<<endl<<OK!<<endl;
else
cout<<endl<<Wrong Input!<<endl;
end=clock（）;
cost=end-start;
cout<<Costed time:<<cost<<ms<<endl;
char c;
cin>>c;
return 0;
}
其他：
小我感觉这种办法已经到了速度的极限，高手的代码竟然可以或许达到几十毫秒，默示自叹不如!
我用的例子是”史上最难数独“，确切只有一个解，代码中maxNum可以限制显示成果数量。
附其他高手的截图一张：
