数独(shù dú)是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。
数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。
bool judge(int count){ //判断这个数字能不能放进去
int row=count/9;
int col=count%9;
//同一行不能有相同的
for(int i=0;i<9;i++){
if(maps[row][i]==maps[row][col] && i!=col){
return false;
}
}
//同一列不能有相同的
for(int i=0;i<9;i++){
if(maps[i][col]==maps[row][col]&& i!=row){
return false;
}
}
//同一个3*3小方块里不能有相同的
int x=row/3*3;
int y=col/3*3; //找到所在小方块左上角的位置
for(int i=x;i<x+3;i++){
for(int j=y;j<y+3;j++){
if(maps[i][j]==maps[row][col]&&i!=row&&j!=col){
return false;
}
}
}
}
上面这一段是精髓所在,从3个方面把数独的规则满足了。1同一行不能有相同的,2同一列不能有相同的,3同一个3 * 3小方块里不能有相同的。只要满足这个条件,那么姑且可以认为这数字暂时可以写在这里。
void retrace(int count){
if(count==81){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cout<<maps[i][j];
}
}
cout<<endl;
return;
}
int row=count/9;
int col=count%9;
if(maps[row][col]=='.'){
for(int i=0;i<9;i++){
maps[row][col]=(char)('1'+i);
if(judge(count)){
retrace(count+1); //扫描下一个小方格
}
}
maps[row][col]='.'; //回溯
}
else
{
retrace(count+1);
}
}
剩下的就是利用上面写好的判断方法进行回溯,如果满足就继续写下去,如果不满足那就回溯到上一步。如果所有数字都已经填入,那就是找到正确的答案了。