数独求解
之前写过一个数独的题解，但是那个题解里各个函数是分散的。下面给出完整代码。能够解不需要枚举的数独而是靠逻辑一步步解出数独。
给下面一个例子：
board{{0,0,7,0,0,5,0,0,3},
{0,0,0,6,3,0,0,0,0},
{5,6,0,0,0,0,9,2,0},
{0,0,0,1,2,9,0,0,0},
{4,0,0,0,0,0,0,7,0},
{2,0,0,0,0,0,0,8,0},
{0,0,4,0,0,3,0,0,1},
{0,0,0,8,7,0,0,0,0},
{8,9,0,0,0,0,3,5,0}};
当这样时传入函数，解不出来，但是通过自己先推出两个数字后，也就是：
{0,0,0,6,3,0,0,0,0},
{5,6,0,0,0,0,9,2,0},
{0,0,0,1,2,9,0,0,0},
{4,0,0,0,0,0,0,7,0},
{2,0,0,0,0,0,0,8,0},
{0,0,4,0,0,3,0,0,1},
{0,0,0,8,7,0,0,0,0},
{8,9,0,0,0,0,3,5,0}};
当这样时传入函数，解不出来，但是通过自己先推出两个数字后，也就是：
board{{0,0,7,0,0,5,0,0,3},
{9,0,0,6,3,0,0,0,0},
{5,6,0,0,0,0,9,2,0},
{0,0,0,1,2,9,0,0,0},
{4,0,0,0,0,0,0,7,0},
{2,0,0,0,0,0,0,8,0},
{0,0,4,0,0,3,0,0,1},
{0,0,0,8,7,0,0,9,0},
{8,9,0,0,0,0,3,5,0}};
{9,0,0,6,3,0,0,0,0},
{5,6,0,0,0,0,9,2,0},
{0,0,0,1,2,9,0,0,0},
{4,0,0,0,0,0,0,7,0},
{2,0,0,0,0,0,0,8,0},
{0,0,4,0,0,3,0,0,1},
{0,0,0,8,7,0,0,9,0},
{8,9,0,0,0,0,3,5,0}};
而添加进去的数字逻辑函数没有写，所以运行不出来。这个逻辑是什么呢，通过第3,4,9行的数字9就可以推出来
第二行第一个是9，而第8行的9通过3,4,9行确定第7行中间格有9（不确定具体在那儿）但是确定第7行的9不在
第9格，那么第8行的9位置就确定了。然后当填进去这两个9后，运行结果就出来了。而这个逻辑函数一时半会
还真不好写。也就是还没有关于格的函数，只要增加这个函数，那么所有不需要枚举的数独都能够求解。
关于每个函数的作用和函数需要注意的地方可以查看数独题解http://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280
下面给出运行结果：
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <iterator>
#include <vector>
using namespace std;
//求两个集合的交集
void Intersection(vector<int> &lhs,vector<int> &rhs,vector<int> &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();
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<int> > &H,vector<vector<int> > &L,vector<vector<int> > &G,int r){
vector<int>::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<int> > &board,int c,int i,int j) {
int c_num=0;
vector<int>::iterator it;
if(i%3==0) {
for(int k=0;k<9;++k) {
if(board[i+1][k]==c) {
++c_num;
break;
} }
for(int k=0;k<9;++k) {
if(board[i+2][k]==c) {
++c_num;
break;
}}
}
else if(i%3==1) {
for(int k=0;k<9;++k) {
if(board[i+1][k]==c) {
++c_num;
break;
} }
for(int k=0;k<9;++k) {
if(board[i-1][k]==c) {
++c_num;
break;
}}
}
else {
for(int k=0;k<9;++k) {
if(board[i-1][k]==c) {
++c_num;
break;
} }
for(int k=0;k<9;++k) {
if(board[i-2][k]==c) {
++c_num;
break;
}}
}
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;
} }
}
else {
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;
}
bool check_num2(vector<vector<int> > &board,int c,int i,int j) {
bool l=false;
int num=0,num_c=0;
int num2=0,num_c2=0;
for(int k=0;k<9;++k) {
if(board[i][k]==0){
++num;
for(int m=0;m<9;++m) {
if(board[m][k]==c) {
++num_c;
break;}}
}
}
for(int k=0;k<9;++k) {
if(board[k][j]==0){
++num2;
for(int m=0;m<9;++m) {
if(board[k][m]==c){
++num_c2;
break;}
}
}
}
if(num-1==num_c||num2-1==num_c2) l=true;
return l;
}
bool solveSudoku(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> R;//交集
vector<int> tmp;
int k,c_num=0;
int c;
bool J=true;
while(num>0) {
k=num;
for(int i=0;i<9;++i) {
for(int j=0;j<9;++j) {
if(board[i][j]==0) {
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 if(R.size()>=2){
for(vector<int>::iterator it=R.begin();it!=R.end();++it) {
c=*it;
if(check_num2(board,c,i,j)) {
board[i][j]=c;
ChangeHLG(i,j,H,L,G,c);
R.clear();
R.push_back(c);
--num;
break;
}
c_num=Check_num(board,c,i,j);
if(4==c_num) {
board[i][j]=c;
ChangeHLG(i,j,H,L,G,c);
R.clear();
R.push_back(c);
--num;
break;
} }
}
else {J=false;return J;}
IJ_R[i][j].clear();
IJ_R[i][j]=R;
}
}
}
if(k==num) break;//防止陷入死循环
}
return J;
}
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)
if(IJ_R[i][j]==IJ_R[i][k]) ++ij_size;
for(int k=i;k<9;++k)
if(IJ_R[k][j]==IJ_R[i][j]) ++ji_size;
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) {
board[i][k]=R[0];
ChangeHLG(i,k,H,L,G,R[0]);
--num;
}
IJ_R[i][k].clear();
IJ_R[i][k]=R;
}
}
break;
}
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) {
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;//防止陷入死循环
}
}
int main() {
vector<vector<int> > board{{0,0,7,0,0,5,0,0,3},
{9,0,0,6,3,0,0,0,0},
{5,6,0,0,0,0,9,2,0},
{0,0,0,1,2,9,0,0,0},
{4,0,0,0,0,0,0,7,0},
{2,0,0,0,0,0,0,8,0},
{0,0,4,0,0,3,0,0,1},
{0,0,0,8,7,0,0,9,0},
{8,9,0,0,0,0,3,5,0}};
vector<int> ivec{1,2,3,4,5,6,7,8,9};
vector<vector<int> > IR{{1},{2},{3},{4},{5},{6},{7},{8},{9}};
vector<int> R;//交集
vector<int> tmp;
int num=0,numtmp=0;
vector<int>::iterator it;
vector<vector<int> > G;//格可填数字的集合
vector<vector<int> > H;//行可填数字集合
vector<vector<int> > L;//列可填数字集合
vector<vector<vector<int> > > IJ_R;//所有元素的交集
vector<vector<int> > 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]-1];
HL_R.push_back(R);//交集为单个元素
}
else {
++num;
R.clear();
R=ivec;
HL_R.push_back(R);
}
}
IJ_R.push_back(HL_R);
}//以上完成数独的预处理
while(num>0) {
numtmp=num;
solveSudoku(board,H,L,G,IJ_R,num);
Diff(board,H,L,G,IJ_R,num);
if(num==numtmp) break;//防止陷入死循环
}
for(int i=0;i<9;++i){
for(int j=0;j<9;++j)
cout<<board[i][j]<<",";
cout<<endl;
}
for(int i=0;i<9;++i) {
cout<<"The "<<i<<"'s intersection:"<<endl;
for(int j=0;j<9;++j) {
for(it=IJ_R[i][j].begin();it!=IJ_R[i][j].end();++it)
cout<<*it<<",";
cout<<endl;
}
}
R.clear(), H.clear(),G.clear(),tmp.clear();
HL_R.clear(),IJ_R.clear();
ivec.clear(),board.clear();
return 0;
}
京公网安备 11010502036488号