假设给定的数独只有唯一的解法
给出一个独特的解法，从数独做法本身出发，每个空也就是行、列、格可填数字集合的交集。
首先定义3个长度为9的vector<vector<char>>型的数组，H,L,G（H表示行，L表示列，G表示格）。
初始化H，L，G，然后循环遍历一遍数独，当board[i][j]不为空时，更新H[i]，L[j]，G[j/3+i/3*3]。
那么我们就可以从交集出发，循环遍历数据，如果board[i][j]是空的，就求其交集，然后如果交集
长度是1，说明只有一个数字同时满足行、列、格的要求。此时只需要更新数独，同时更新
H[i]，L[j]，G[j/3+i/3*3]。
定义一个vector<vector<vector<char> > > IJ_R存放board[i][j]位置的交集。
Check_num()函数是查找 IJ_R[i][j]中每个元素在相关相邻两行、两列中出现的次数，如果出现4次，说明
IJ_R[i][j]中有元素只能填在board[i][j]的位置上。然后更新 H[i],L[j],G[j/3+i/3*3]。
这个算法应该能解一些简单的数独，因为都是靠逻辑的计算，没有枚举和递推，所以碰到一些比较难的需要
枚举的数独就无能为力。
代码后面增加了一个函数check_num2()，做过数独的人应该知道他的作用。
计算出了所有位置的交集，即 IJ_R，那么后面枚举或者递归的时候可以大大减少次数，每次只从 IJ_R[i][j]中
寻找元素枚举和递归。
这个算法有时候会出现什么问题呢，当遍历完所有元素，都没有交集长度为1的点且查找完所有元素的交集
都没有符合c_num=4的点，此时就需要退出循环。
做过数独的人都知道这个时候是需要从同一行或同一列看是否有相同交集的，且交集长度等于其有相同交集的
元素个数，此时直接把交集里的元素暂时确定为已知数据，然后填后面的数据。这个算法还没设计。但应该是可行的。
而当出现上面那种情况就需要用到差集，当差集长度为1时，说明该位置就确定了需要填写的数字，这个函数还没有设计。
代码后面有求两个集合差集的函数。
上面所说的函数在代码后面增加了，但是没有测试过，整体逻辑应该是没问题的。
下面的代码能够填写部分数据，且正确，给出下面代码对示例的运行结果。
[[.,.,9,7,4,8,.,.,2],[7,.,.,6,.,2,.,.,9],[.,2,.,1,.,9,.,.,.],
[.,.,7,9,8,6,2,4,1],[2,6,4,3,1,7,5,9,8],[1,9,8,5,2,4,3,6,7],
[9,.,.,8,6,3,.,2,.],[.,.,2,4,9,1,.,.,6],[.,.,.,2,7,5,9,.,.]]
可以看到还有很多空没有填，把每个元素的交集输出出来发现用常规的推理已经行不通，所以还是要枚举其余还空着的
位置，此时每次枚举需要修改 H，L，G中的元素，当碰到后面填数字时求的交集为空时说明当前错误，需要重新从
IJ_R[i][j]中选取元素进行枚举。然后重复以上操作，直至num=0即填满所有空。
而要实现以上功能要回溯，回溯算法我不大懂，有懂的人可以在这个基础上完成整个代码的设计。
Intersection()，Difference()，ChangeDHG()，Check_num()，Check_num2()和Diff()这6个函数应该是通常做数独的整个过程。
这6个函数也能解大部分不需要试错的（也就是不需要枚举）的数独。
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
vector<char> ivec{'1','2','3','4','5','6','7','8','9'};
vector<vector<char> > IR{{'1'},{'2'},{'3'},{'4'},{'5'},{'6'},{'7'},{'8'},{'9'}};
vector<char> R;//交集
vector<char> tmp;
int num=0,k=0,c_num=0;//num统计总共多少个空
char c;
vector<char>::iterator it;
vector<vector<char> > G;//格可填数字的集合
vector<vector<char> > H;//行可填数字集合
vector<vector<char> > L;//列可填数字集合
vector<vector<vector<char> > > IJ_R;//board中所有元素的交集
vector<vector<char> > HL_R;//行中每个元素的交集。
for(int i=0;i<9;++i) {
G.push_back(ivec);//开始初始化9个格的集合为1~9
L.push_back(ivec);//开始初始化9个列的集合为1~9
H.push_back(ivec);//开始初始化9个行的集合为1~9
}
for(int i=0;i<9;++i) {
HL_R.clear();
for(int j=0;j<9;++j) {
if(board[i][j]!='.') {
ChangeHLG(i,j,H,L,G,board[i][j]);
R.clear();
R=IR[board[i][j]-'0'-1];
HL_R.push_back(R);//交集为单个元素
}
else {
++num;
R.clear();
R=ivec;
HL_R.push_back(R);//碰到空格初始化为1~9的集合，后面再修改
}
}
IJ_R.push_back(HL_R);//插入每行得到的交集。
}
while(num>0) {
k=num;
for(int i=0;i<9;++i) {
for(int j=0;j<9;++j) {
if(board[i][j]=='.') {
tmp.clear();
R.clear();
Intersection(H[i],L[j],tmp);//求得行、列的交集
Intersection(tmp,G[j/3+i/3*3],R);//求得行，列，格的交集
if(R.size()==1) {//交集长度为1，说明该点是确定的值。
board[i][j]=R[0];//修改数独中的数字
ChangeHLG(i,j,H,L,G,R[0]);
--num;
}
else{
for(it=R.begin();it!=R.end();++it) {
c=*it;
c_num=Check_num(board,c,i,j);
//如果c_num=4，说明相关的相邻两行和两列出现4次该元素，则该格只能填入c
if(4==c_num) {
board[i][j]=c;
ChangeHLG(i,j,H,L,G,c);
R.clear();
R.push_back(c);
--num;
break;
} }
}
IJ_R[i][j].clear();
IJ_R[i][j]=R;//更新每个元素的交集
}
}
}
if(k==num) break;
}
}
//求两个集合的交集
void Intersection(vector<char> &lhs,vector<char> &rhs,vector<char> &R)
{
R.clear();
sort(lhs.begin(),lhs.end());
sort(rhs.begin(),rhs.end());
set_intersection(lhs.begin(),lhs.end(),rhs.begin(),rhs.end(),back_inserter(R));
}
//求集合的差集
void Difference(vector<int> &lhs,vector<int> &rhs,vector<int> &R)
{
R.clear();
sort(lhs.begin(),lhs.end());
sort(rhs.begin(),rhs.end());
R.resize(lhs.size());
vector<int>::iterator retEndPos;
retEndPos=set_difference(lhs.begin(),lhs.end(),rhs.begin(),rhs.end(),R.begin());
R.resize(retEndPos-R.begin());
}
//修改行，列，格
void ChangeHLG(int i,int j,vector<vector<char> > &H,vector<vector<char> > &L,vector<vector<char> > &G,char r) {
vector<char>::iterator it;
it=find(H[i].begin(),H[i].end(),r);//寻找对应元素在行中的位置
H[i].erase(it);//在行中删除对应元素
it=find(L[j].begin(),L[j].end(),r);//寻找对应元素在列中的位置
L[j].erase(it);//在列中删除元素
it=find(G[j/3+i/3*3].begin(),G[j/3+i/3*3].end(),r);//寻找对应元素在格中的位置
G[j/3+i/3*3].erase(it);//在格中删除元素
}
//统计相关相邻行、列在交集中元素出现的个数
int Check_num(vector<vector<char> >&board,char c,int i,int j) {
int c_num=0;
vector<char>::iterator it;
if(i%3==0) {
it=find(board[i+1].begin(),board[i+1].end(),c);
if(it!=board[i+1].end()) ++c_num;
it=find(board[i+2].begin(),board[i+2].end(),c);
if(it!=board[i+2].end()) ++c_num;
}
else if(i%3==1) {
it=find(board[i-1].begin(),board[i-1].end(),c);
if(it!=board[i-1].end()) ++c_num;
it=find(board[i+1].begin(),board[i+1].end(),c);
if(it!=board[i+1].end()) ++c_num;
}
else {
it=find(board[i-1].begin(),board[i-1].end(),c);
if(it!=board[i-1].end()) ++c_num;
it=find(board[i-2].begin(),board[i-2].end(),c);
if(it!=board[i-2].end()) ++c_num;
}
if(j%3==0) {
for(int k=0;k<9;++k) {
if(board[k][j+2]==c) {
++c_num;
break;
} }
for(int k=0;k<9;++k) {
if(board[k][j+1]==c) {
++c_num;
break;
} }
}
else if(j%3==1) {
for(int k=0;k<9;++k) {
if(board[k][j+1]==c) {
++c_num;
break;
} }
for(int k=0;k<9;++k) {
if(board[k][j-1]==c) {
++c_num;
break;
} }
}
if(j%3==2) {
for(int k=0;k<9;++k) {
if(board[k][j-2]==c) {
++c_num;
break;
} }
for(int k=0;k<9;++k) {
if(board[k][j-1]==c) {
++c_num;
break;
} }
}
return c_num;
}
};
增加一个函数check_num2();检查交集中的元素在该行所有列的元素为空的整列是否出现该元素，并统计空的列数num和
出现的次数num_c，如果num-1=num_c，说明该元素一定在board[i][j]的位置上。
同样再检查该列，检查交集中的元素在该列所有行的元素为空的整行是否出现该元素，通统计num和num_c.
如果num-1=num_c,说明该元素一定在board[i][j]的位置上。
bool check_num2(vector<vector<char> > &board,char c,int i,int j) {
int num=0,num_c=0;
for(int k=0;k<9;++k) {
if(board[i][k]=='.'){
++num;
for(int m=0;m<9;++m) {
if(board[m][k]==c) {
++num_c;
break;}
}
}
}
if(num-1==num_c) return true;
num=0,num_c=0;
for(int k=0;k<9;++k) {
if(board[k][j]=='.'){
++num;
for(int m=0;m<9;++m) {
if(board[k][m]==c){
++num_c;
break;
}
}
}
}
if(num-1==num_c) return true;
return false;
}
继续增加一个函数Diff()实现上面说的循环检查当前行和列是否有相同的交集，且交集长度等于相同个数时
修改当前行和列的其他交集。修改交集可以用当前交集与找到的交集做差，即差集来实现。
具体过程看下面代码，有相应的注释。
因为是自己在编译器上写，为了方便，修改了数独数据类型为int
下面这个函数没有测试过，不知道是否有错误，但整体逻辑应该是没问题的。
void Diff(vector<vector<int> > &board,vector<vector<int> > &H,vector<vector<int> > &L,
vector<vector<int> > &G,vector<vector<vector<int> > > &IJ_R,int &num){
vector<int>::size_type ij_size,ji_size;
vector<int> R;
int k;
while(num>0){
k=num;
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
if(IJ_R[i][j].size()>1){//逐个检查
ij_size=0,ji_size=0;
for(int k=j;k<9;++k){//统计当前行有几个和IJ_R[i][j]相同的
if(IJ_R[i][j]==IJ_R[i][k]) ++ij_size;
}
for(int k=i;k<9;++k) {//统计当前列有几个和IJ_R[i][j]相同的
if(IJ_R[k][j]==IJ_R[i][j]) ++ji_size;
}
//如果当前行有IJ_R[i][j]长度个相同的交集，修改当前行其他不同的交集
if(ij_size==IJ_R[i][j].size()){
for(int k=0;k<9;++k) {
if(IJ_R[i][k]!=IJ_R[i][j]&&IJ_R[i][k].size()>1){
Difference(IJ_R[i][k],IJ_R[i][j],R);
if(R.size()==1) {//如果得到的差集长度为1，说明当前位置可填数字唯一
board[i][k]=R[0];
ChangeHLG(i,k,H,L,G,R[0]);
--num;
}
IJ_R[i][k].clear();
IJ_R[i][k]=R;//修改当前位置交集为差集
}
}
}
//如果当前例有IJ_R[i][j]长度个相同的交集，修改当前列其他交集
if(ji_size==IJ_R[i][j].size()){
for(int k=0;k<9;++k) {
if(IJ_R[k][j]!=IJ_R[i][j]&&IJ_R[k][j].size()>1){
Difference(IJ_R[k][j],IJ_R[i][j],R);
if(R.size()==1) {//如果得到的差集长度为1，说明当前位置可填数字唯一
board[k][j]=R[0];
ChangeHLG(k,j,H,L,G,R[0]);
--num;
}
IJ_R[k][j].clear();
IJ_R[k][j]=R;//修改当前位置的交集
}
}
}
}
}
}
solveSudoku(board,H,L,G,IJ_R,num);//修改完后因为已经影响了其他位置的交集，调用一次主函数
if(num==k) break;
}
}
京公网安备 11010502036488号