数独求解算法

  • d1_101694
    了解作者
  • 5.5KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-11 10:17
    上传日期
自己写的一个求解数独的算法,对此有兴趣的朋友可以交流下。自己调试没什么问题,不知道经不经得起别人的考验。
sudoku.rar
  • Sudoku.h
    3.1KB
  • Sudoku.cpp
    13.6KB
内容介绍
#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++; }
评论
    相关推荐
    • 程序员算法
      这是一个算法文档压缩包,其中包括《可能与不可能的边界》、《具体数学》、《算法的乐趣》、《啊哈!算法》。这些书很适合对算法感兴趣的朋友,书籍讲解算法非常有趣。注意,其中有些文档是试读版本。
    • 算法实验
      算法实验算法实验算法实验算法实验算法实验算法实验算法实验算法实验
    • 大数据算法
      本书共分为10章,第1章概述大数据算法,第2章介绍时间亚线性算法,第3章介绍空间亚线性算法,第4章概述外存算法,第5章介绍大数据外存查找结构,第6章讲授外存图数据算法,第7章概述MapReduce算法,第8章通过一系列...
    • 算法
      算法 算法
    • SIFT 算法
      SIFT 算法SIFT 算法SIFT 算法SIFT 算法
    • RSA算法
      RSA算法是公钥加密算法中重要的算法之一,本算法即实现RSA的加解密过程。
    • 分词算法介分词算法
      算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语分词介绍分词算法 汉语...
    • unify算法
      unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法unify算法
    • 寻路算法
      寻路算法 寻路封装
    • dsp算法算法算法算法
      dsp各种算法