数独—暴力求解算法
1.基本工作
typedef std::vector<int> vint;//头文件vector
typedef std::vector<vint> vvint;//二位数组
class SudokuCrack
{
public:
SudokuCrack(vvint &);
int beginCrack();//开始求解
private:
vvint vvnum;//0表示没有数字，1-9为正常数字
static vvint result;//用于保存结果，静态成员变量，需要在cpp文件中初始化
};2.求解函数
static std::default_random_engine e(time(0));//c++11，需要头文件random，windows可能还需要头文件ctime static std::uniform_int_distribution<int> u(0,1);//随机数，0和1，用于当最优点有好几个时进行随机选择 //该函数返回值为int，不是bool，这样我们可以发生错误时返回一个错误代码 int SudokuCrack::selectBetter() { vint min_locate ( 2,0 );//保存选择的点的坐标 int min_lack=10;//可能的最大值是9，这个这是初始值，用于被代替 int lack_num = 10; for( int i=0 ; i<9 ;++i ) { for( int j=0; j<9; ++j ) { //此处先进行判断，如果这个点上的有数字，那这个点可能的数字个数就是10 //如果这个点上没有数字，那就计算这个点上可能的数字的个数 lack_num = vvnum[i][j] ? 10 : countLackNum(i,j); if( lack_num < min_lack )//该点是目前的最优点 { min_lack = lack_num; min_locate[0]=i;//保存坐标 min_locate[1]=j; } else if(lack_num == min_lack)//缺少的数字个数一样，都是最优点 { if( u(e) )//就随机进行选择 { min_locate[0]=i; min_locate[1]=j; } } } } if( min_lack == 10 )//最小的点上缺少的个数为10个，就表明所有点上都有数字了，没有下一步可选了，只能判断是否胜利 { if( checkwin() )//如果胜利了 { result=vvnum; return 1;//返回1求值成功，不再继续计算 } else return 0;//不然就失败 } return attemptLocate( min_locate[0] ,min_locate[1] );//对最优点一个一个的“猜”，猜的结果返回 }typedef std::set<int> sint;//需要头文件set int SudokuCrack::attemptLocate( int i, int j )//“猜”数字的函数 { sint d = getLackedNumSet( i , j );//保存有该点可能的所有数字 sint::iterator it=d.begin();//迭代器，用于遍地所有数字，一个一个试 for( ; it!=d.end(); ++it ) { vvint vvnum_new=vvnum;//新的9×9矩阵 vvnum_new[i][j]=*it; SudokuCrack sucr_t(vvnum_new); if( sucr_t.selectBetter() )//对新矩阵进行求解 return 1; } return 0; } sint& SudokuCrack::getLackedNumSet(int i,int j ) { static sint d;//静态成员 sint s_temp={1,2,3,4,5,6,7,8,9};//一个1-9的数组 using std::swap; swap(d , s_temp);//使用swap进行交换，避免复制 for(int m=0; m<9; ++m) { d.erase(vvnum[i][m]);//删除行上的数字，数字是0-9之间的任意值，不用进行检查 d.erase(vvnum[m][j]);//删除列上的数字 } int m =i/3*3, n=j/3*3; for( int q=0; q<3; ++q ) { for( int p=0 ;p<3; ++p ) { d.erase( vvnum[m+q][n+p] );//删除3×3方格上的数字 } } return d; }int SudokuCrack::countLackNum(int i ,int j) { return getLackedNumSet(i,j).size();//调用已有函数 } //用了set确实很方便，插入的时候也不会重复插入 bool SudokuCrack::checkwin() { //sint见上一节的typedef const sint ss={1,2,3,4,5,6,7,8,9};//固定的1-9，用于检查是否和它相等 for( int i=0 ;i<9; ++i ) { sint a,b; for(int j=0; j<9; ++j) { a.insert(vvnum[i][j]);//每行的数字集合 b.insert(vvnum[j][i]);//每列的数字集合 } if( a!=ss || b!=ss )//任意一个不相等，就没有求解成功 return 0; } for( int m=0 ;m<7; m+=3 )//四重循环，但每一重只有3个 { for( int n=0 ;n<7; n+=3 )//3×3个 { sint d; for(int i=0 ;i<3; ++i)//3×3宫格 { for( int j=0 ;j<3; ++j ) { d.insert(vvnum[m+i][n+j]); } } if(d!=ss) return 0;//求解失败 } } return 1;//求解成功！ }int SudokuCrack::isBad() { for( int i=0 ;i<9; ++i ) { sint a,b;//sint见前面的typedef for(int j=0; j<9; ++j) { if(vvnum[i][j]!=0)//数值为0就跳过 { if( a.find(vvnum[i][j])==a.end() ) //是否找到了 a.insert(vvnum[i][j]);//没找到就插入 else//找到了相同值就报错 { return 1;//错误代码1 } } if(vvnum[j][i]!=0) { if( b.find(vvnum[j][i])==b.end() ) b.insert(vvnum[j][i]); else//找到了相同值就报错 return 2; } } } for( int m=0 ;m<7; m+=3 )//3×3×3×3的四重循环 { for( int n=0 ;n<7; n+=3 )//3×3个 { sint d; for(int i=0 ;i<3; ++i)//3×3矩阵 { for( int j=0 ;j<3; ++j ) { if(vvnum[m+i][n+j]==0)//值为0就跳过 continue; if( d.find(vvnum[m+i][n+j])==d.end() ) d.insert(vvnum[m+i][n+j]); else { return 3;//错误代码3 } } } } } return 0;//用户的输入正确 }int SudokuCrack::beginCrack() { int n=isBad(); if( n!=0 ) return n; result = vvint(1,vint(1,0)); selectBetter(); return 0; }const vvint& getResult(){ return result ; }#include<iostream> #include "sudokucrack.h" using namespace std; int main() { vvint d{ {4,0,0,5,2,0,7,0,3}, {0,0,0,0,0,3,0,0,0}, {1,0,0,0,0,7,0,0,0}, {0,1,4,0,0,0,0,0,6}, {7,0,0,0,5,0,0,0,1}, {5,0,0,0,0,0,4,2,0}, {0,0,0,4,0,0,0,0,5}, {0,0,0,8,0,0,0,0,0}, {2,0,1,0,7,6,0,0,8} }; SudokuCrack s(d); int m=s.beginCrack(); if(m==0) { const vvint &r=s.getResult(); for(const vint & a : r)//c++11，基于范围的for循环 { for( int d : a) cout<<d<<" "; cout<<"\n"; } cout<<endl; } else if(m==1) cout<<"数独非法！在某行中有重复数字！"<<endl; else if(m==2) cout<<"数独非法！在某列中有重复数字！"<<endl; else if(m==3) cout<<"数独非法！在某3×3矩阵中有重复数字！"<<endl; return 0; }4 9 6 5 2 8 7 1 3 8 7 5 1 4 3 6 9 2 1 3 2 9 6 7 8 5 4 3 1 4 2 8 9 5 7 6 7 2 9 6 5 4 3 8 1 5 6 8 7 3 1 4 2 9 6 8 7 4 9 2 1 3 5 9 4 3 8 1 5 2 6 7 2 5 1 3 7 6 9 4 8
Last updated