数独求解算法

#include "Sudoku.h" #include <string> #include<iostream> using namespace std; CSudoku::CSudoku(void) { for(int i=0,j,k;i<9;i++){ for(j=0;j<9;j++){ for(k=0;k<11;k++){ sd[i][j][k]=0; } } } } CSudoku::~CSudoku(void) { } bool CSudoku::get_sudoku(int i_sudo[9][9]){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ sd[i][j][10]=i_sudo[i][j]; } } if(check())return is_exist=create_candidate_key(); else return is_exist=false; } bool CSudoku::deal(){ if(!is_exist)return false; create_candidate_key(); int n=1,flag=0; while(n!=0){ n=0; n+=search_only_candidate_key();//唯一候选码法* n+=search_recessivity_only_candidate_key();//隐性唯一候选码* n+=hidden_pairs();//隐性数对删减法* n+=hidden_triples();//隐性三链数删减法* n+=locked_candidates();//区块删减法* if(n==0){flag++;n=1;}//如果没有成果，那flag加1，表示还有一次机会 else flag=0; if(flag>1)n=0;//如果flag大于1，那表示已经连续两次没有成果了，此时让程序退出 } return true; } int CSudoku::recursion(int n){ if(!is_exist)return 0; int j=n%9; int i=(n-j)/9; int k; if(sd[i][j][10]!=0){ if(n==80)return OK; if(recursion(n+1)==BACK)return BACK; else return OK; } else{ get_candidate_key(i,j); for(k=1;k<=9;k++){ if(sd[i][j][k]==1){ sd[i][j][10]=k; if(n==80)return OK; else if(recursion(n+1)==OK)return OK; } } sd[i][j][10]=0; return BACK; } } void CSudoku::display(){ cout<<"\n********************************"<<endl; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ cout<<sd[i][j][10]<<" "; if(j%3==2)cout<<"|"; } cout<<endl; if(i%3==2)cout<<endl; } cout<<"********************************"<<endl; } void CSudoku::get_result(int r[9][9]){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ r[i][j]=sd[i][j][10]; } } } bool CSudoku::check(){ //行检查 for(int i=0;i<9;i++){ init_temp(0); for(int j=0;j<9;j++){ if(sd[i][j][10]>9||sd[i][j][10]<0)return false;//此检查会遍历一次全表，所以后面可以不用再检查了 if(sd[i][j][10]!=0){ if(temp[sd[i][j][10]]==1)return false; else temp[sd[i][j][10]]=1; } } } //列检查 for(int j=0;j<9;j++){ init_temp(0); for(int i=0;i<9;i++){ if(sd[i][j][10]!=0){ if(temp[sd[i][j][10]]==1)return false; else temp[sd[i][j][10]]=1; } } } //块检查 for(int n=0,a,b;n<9;n++){ a=n-n%3; b=3*(n%3); init_temp(0); for(int k=0;k<9;k++){ if(sd[a+(k-k%3)/3][b+k%3][10]!=0){ if(temp[sd[a+(k-k%3)/3][b+k%3][10]]==1) return false; else temp[sd[a+(k-k%3)/3][b+k%3][10]]=1; } } } return true; } void CSudoku::init_temp(int kind){//初始化temp，全置为kind,实际上非0即1 if(kind!=0)kind=1; for(int i=0;i<10;i++)temp[i]=kind; } bool CSudoku::create_candidate_key(){//创造一个候选码表 for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(sd[i][j][10]==0){//如果该格为空格，则获取该格的所有候选码 get_candidate_key(i,j); } else sd[i][j][0]=0;//否则把该格的候选码数量置为0 } } return true; } bool CSudoku::get_candidate_key(int i,int j){//获取I,J处的候选码 if(i>8||i<0||j>8||j<0)return false; if(sd[i][j][10]!=0)return false;//如果该格不为空，则出错，返回假 int a,b,n=0; init_temp(1);//初始化temp，假设所有候选码都有 for(int k=0;k<9;k++){//然后再把此列中已经存在的数字从候选码中去除 if(sd[k][j][10]!=0)temp[sd[k][j][10]]=0; } for(int k=0;k<9;k++){//处理此行中已经存在的数字 if(sd[i][k][10]!=0)temp[sd[i][k][10]]=0; } a=i-i%3; b=j-j%3; for(int k=0;k<9;k++){//处理此大九宫格中已经存在的数字 if(sd[a+(k-k%3)/3][b+k%3][10]!=0)temp[sd[a+(k-k%3)/3][b+k%3][10]]=0; } for(int k=1;k<=9;k++){//把结果写入候选码表sd if(temp[k]==1)n++; sd[i][j][k]=temp[k]; } sd[i][j][0]=n; return true; } int CSudoku::search_only_candidate_key(){/*唯一候选码法，把那些候选码唯一的方格填好,返回处理的方格数量*/ int n=0; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(sd[i][j][0]==1){ for(int k=1;k<=9;k++){ if(sd[i][j][k]==1){ n++; sd[i][j][10]=k; refresh_candidate_key(i,j); } } } } } return n; } bool CSudoku::refresh_candidate_key(int i,int j){ if(sd[i][j][10]==0)return false; int a,b; init_temp(0);//初始化temp为0 operation_and_with_t(i,j,temp);//让该格的候选码与0进行“与运算”以达到置零的效果 for(int k=0;k<9;k++){ sd[k][j][0]=sd[k][j][0]-(sd[k][j][sd[i][j][10]]==1); sd[k][j][sd[i][j][10]]=0; } for(int k=0;k<9;k++){ sd[i][k][0]=sd[i][k][0]-(sd[i][k][sd[i][j][10]]==1); sd[i][k][sd[i][j][10]]=0; } a=i-i%3; b=j-j%3; for(int k=0;k<9;k++){ sd[a+(k-k%3)/3][b+k%3][0]=sd[a+(k-k%3)/3][b+k%3][0]-(sd[a+(k-k%3)/3][b+k%3][sd[i][j][10]]==1); sd[a+(k-k%3)/3][b+k%3][sd[i][j][10]]=0; } return true; } int CSudoku::search_recessivity_only_candidate_key(){ int n=0,num,adress; //横向扫描 for(int i=0;i<9;i++){ for(int k=1;k<=9;k++){ num=0; for(int j=0;j<9;j++){//看数字候选码k在该行中出现的次数 if(sd[i][j][k]==1){ num++; adress=j; } } if(num==1){//如果出现次数为1次，则k是该行的隐性候选码 n++; sd[i][adress][10]=k;//那么用刚才保存的地址adress定位到此行的拥有候选码k的位置，将K填入 refresh_candidate_key(i,adress);//然后刷新数字k影响的区域 } } } //纵向扫描 for(int j=0;j<9;j++){ for(int k=1;k<=9;k++){ num=0; for(int i=0;i<9;i++){ if(sd[i][j][k]==1){ num++; adress=i; } } if(num==1){ n++; sd[adress][j][10]=k; refresh_candidate_key(adress,j); } } } //九宫格扫描 for(int m=0,i,j,t;m<9;m++){ i=m-m%3; j=3*(m%3); for(int k=1;k<=9;k++){ num=0; for(t=0;t<9;t++){ if(sd[i+(t-t%3)/3][j+t%3][k]==1){ num++; adress=t; } } if(num==1){ n++; sd[i+(adress-adress%3)/3][j+adress%3][10]=k; refresh_candidate_key(i+(adress-adress%3)/3,j+adress%3); } } } return n; } int CSudoku::hidden_pairs(){ int n=0; //横向扫描 for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(sd[i][j][0]==2){//在该行找到第一个只有两个候选码的格 for(int k=j+1;k<9;k++){ if(sd[i][k][0]==2){//找到之后就找第二个只有两个候选码的格 if(compare(i,j,i,k)==2){//如果也找到了，就看这两个格的候选码是否一样 operation_not(i,j);//如果一样的话，就把其中一个取非，用作“与运算”的参照 for(int m=0;m<9;m++){//然后与除了找到的两个格以外的格进行与运算，结果保留在进行与运算的格里 if(m!=j ||m!=k){ int i_temp=sd[i][m][0];//在进行“与运算”前保存此格的候选码数量 operation_and(i,m,i,j); if(i_temp!=sd[i][m][0])n++;//在进行“与运算”之后，如果该格的候选码数量发生变化，说明该算法起到一次作用了，把这次作用统计起来 } } operation_not(i,j);//还原作为“与运算”参照的格 } } } } } } for(int j=0;j<9;j++){ for(int i=0;i<9;i++){ if(sd[i][j][0]==2){ for(int k=i+1;k<9;k++){ if(sd[k][j][0]==2){ if(compare(i,j,k,j)==2){ operation_not(i,j); for(int m=0;m<9;m++){ if(m!=i||m!=k){ int i_temp=sd[m][j][0]; operation_and(m,j,i,j); if(i_temp!=sd[m][j][0])n++; } } operation_not(i,j); } } } } } } for(int m=0,a,b;m<9;m++){ a=m-m%3; b=3*(m%3); for(int i=0;i<9;i++){ if(sd[a+(i-i%3)/3][b+i%3][0]==2){ for(int j=i+1;j<9;j++){ if(sd[a+(j-j%3)][b+j%3][0]==2){ if(compare(a+(i-i%3)/3,b+i%3,a+(j-j%3),b+j%3)==2){ operation_not(a+(i-i%3)/3,b+i%3); for(int k=0;k<9;k++){ if(k!=i||k!=j){ int temp=sd[a+(k-k%3)][b+k%3][0]; operation_and(a+(k-k%3),b+k%3,a+(i-i%3)/3,b+i%3); if(temp!=sd[a+(k-k%3)][b+k%3][0])n++; }