C++解数独的算法（内含三种）

#include "sudoku.h" #define SDK_HANDLE {sudoku9[i][j].reset();sudoku9[i][j].set(k);flag=1;if(STD_Remove(i,j)) while(STD_Remove());break;} //#define TEST sudoku::sudoku() //构造函数,通过输入初始化数独矩阵 { int i,j,num; #ifdef TEST //为了方便测试而使用的，将数独数据写在程序中，每次调试时不必重新输入 const char testSDK[9][10]={{"600009000"},{"039000500"},{"504030809"},{"000005300"},{"050398020"},{"003700000"},{"302060904"},{"007000630"},{"000400008"}}; for(i=0;i<9;++i) for(j=0;j<9;++j) { num=testSDK[i][j]-48; if(num>0 &&num<10) sudoku9[i][j].set(num-1); else sudoku9[i][j].set(); } #else char temp[10]; for(i=0;i<9;++i) { cin.read(temp,10); //输入数独数据，每9个一组 for(j=0;j<9;++j) { num=temp[j]-48; if(num>0 && num<10) sudoku9[i][j].set(num-1); else sudoku9[i][j].set(); } } #endif s_index=-1; //暂时不需要这2个用于假设的变量。 s_num=0; } sudoku::sudoku(const sudoku &original,int index,int num) { (*this)=original; this->sudoku9[index/9][index%9].reset(); this->sudoku9[index/9][index%9].set(num); this->s_index=-1; //暂时不需要这2个用于假设的变量。 this->s_num=0; } void sudoku::display() //输出数独结果 { int i,j,k; for(i=0;i<9;++i,cout<<endl) for(j=0;j<9;++j) { if(sudoku9[i][j].count()!=1) //判断每一元素中1的个数，如果数量不为1，证明该位置还没有确定的值，则打印0 { cout<<0<<' '; continue; } else { for(k=0;k<9;++k) if(sudoku9[i][j].test(k)) { cout<<k+1<<' '; break; } } } } bool sudoku::check_possible() //检验此种情况是否有解，即数独中是否有任何数都不能填的位置。返回 1:没有; 0:有 { int i,j; bool flag=1; for(i=0;i<9;++i) for(j=0;j<9;++j) if(sudoku9[i][j].count()==0) { flag=0; //没有候选,返回0 goto BREAK; } BREAK: return flag; } bool sudoku::check_finish() //检查数独是否完成，1:完成;0:未完成 { int i,j; bool flag=1; for(i=0;i<9;++i) for(j=0;j<9;++j) { if(sudoku9[i][j].count()!=1) { flag=0; goto BREAK; } } BREAK: return flag; } bool sudoku::STD_Remove() //标准排除法，即在横、纵及3x3方向上不能有重复的排除法。返回0:没有修改; 1:存在修改 { int i,j,x,y,posbit; bool flag=0; for(i=0;i<9;++i) for(j=0;j<9;++j) { if(sudoku9[i][j].count()==1) //如果已经有确定值 { for(posbit=0;posbit<9;++posbit) //获得为1的位的位置 if(sudoku9[i][j].test(posbit)) break; for(y=0;y<9;++y) //横向扫描,排除候选 { if(y==j) continue; else { if(sudoku9[i][y].test(posbit)) { sudoku9[i][y].reset(posbit); if(sudoku9[i][y].count()==1) flag=1; //排除使得该位置出现确定值时，置标志位 } } } for(x=0;x<9;++x) //纵向扫描,排除候选 { if(x==i) continue; else { if(sudoku9[x][j].test(posbit)) { sudoku9[x][j].reset(posbit); if(sudoku9[x][j].count()==1) flag=1; //排除使得该位置出现确定值时，置标志位 } } } for(x=(i/3)*3;x<(i/3)*3+3;++x) //3*3扫描,排除候选 for(y=(j/3)*3;y<(j/3)*3+3;++y) { if((y==j) || (x==i)) continue; else { if(sudoku9[x][y].test(posbit)) { sudoku9[x][y].reset(posbit); if(sudoku9[x][y].count()==1) flag=1; //排除使得该位置出现确定值时，置标志位 } } } } } return flag; //flag取值 0:没有修改; 1:存在修改 } bool sudoku::STD_Remove(int i,int j) { int x,y,posbit; bool flag=0; if(sudoku9[i][j].count()==1) //如果已经有确定值 { for(posbit=0;posbit<9;++posbit) //获得为1的位的位置 if(sudoku9[i][j].test(posbit)) break; for(y=0;y<9;++y) //横向扫描,排除候选 { if(y==j) continue; else { if(sudoku9[i][y].test(posbit)) { sudoku9[i][y].reset(posbit); if(sudoku9[i][y].count()==1) flag=1; //排除使得该位置出现确定值时，置标志位 } } } for(x=0;x<9;++x) //纵向扫描,排除候选 { if(x==i) continue; else { if(sudoku9[x][j].test(posbit)) { sudoku9[x][j].reset(posbit); if(sudoku9[x][j].count()==1) flag=1; //排除使得该位置出现确定值时，置标志位 } } } for(x=(i/3)*3;x<(i/3)*3+3;++x) //3*3扫描,排除候选 for(y=(j/3)*3;y<(j/3)*3+3;++y) { if((y==j) || (x==i)) continue; else { if(sudoku9[x][y].test(posbit)) { sudoku9[x][y].reset(posbit); if(sudoku9[x][y].count()==1) flag=1; //排除使得该位置出现确定值时，置标志位 } } } } return flag; } bool sudoku::alone_determine() { int i,j,k,x,y; bool flag=0,alone=1; //flag是返回值，1：数独有新变化，0：数独无变化。alone是独立值标志位，1：未发现独立值，0：发现独立值 for(i=0;i<9;++i) for(j=0;j<9;++j) { if(sudoku9[i][j].count()>1) { for(k=0;k<9;k++) if(sudoku9[i][j].test(k)) { alone=1; //标志位复位 for(y=0;y<9;++y) //横向扫描 if(y==j) continue; else if(sudoku9[i][y].test(k)) //测试同一数独集合的第k位，发现有重复的候选 { alone=0; //不是唯一 break; } if(alone) SDK_HANDLE //如果发现该数字是唯一的,则可以确定该为数字,同时在进行标准排除法 alone=1; //标志位复位 for(x=0;x<9;++x) //纵向扫描 if(x==i) continue; else if(sudoku9[x][j].test(k)) { alone=0; //不是唯一 break; } if(alone) SDK_HANDLE //如果发现该数字是唯一的,则可以确定该为数字,同时在进行标准排除法 alone=1; //标志位复位 for(x=(i/3)*3;x<(i/3)*3+3;++x) //3*3扫描 for(y=(j/3)*3;y<(j/3)*3+3;++y) { if((y==j)&&(x==i)) continue;