数独求解

之前写过一个数独的题解,但是那个题解里各个函数是分散的。下面给出完整代码。能够解不需要枚举的数独而是靠逻辑一步步解出数独。
给下面一个例子:
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}};
当这样时传入函数,解不出来,但是通过自己先推出两个数字后,也就是:
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}};
而添加进去的数字逻辑函数没有写,所以运行不出来。这个逻辑是什么呢,通过第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;
}