首页 > 代码库 > 数独破解c++代码

数独破解c++代码

数独破解c++代码

#include <iostream>#include <cstring>#include <cstdio>#include <stack>using namespace std;int grup_start[9][2] = {{0,0} ,{0,3}, {0,6} ,{3,0} ,{3,3}, {3,6} ,{6,0} ,{6,3}, {6,6}};int get_grup(int x,int y){    return x /3 * 3 + y/3;}bool judge(int a[][9],int i,int j,int k){    for(int ii = 0; ii < 9; ii++){        if(a[i][ii] == k && ii != j)            return false;        if(a[ii][j] == k && i != ii)            return false;    }    int grup_int = get_grup(i,j);    for(int ii = grup_start[grup_int][0]; ii < grup_start[grup_int][0] + 3; ii++)        for(int jj = grup_start[grup_int][1]; jj < grup_start[grup_int][1] + 3; jj++){            if(a[ii][jj] == k && ii != i && j != jj)                return false;        }   return true;}void print(int a[][9]){     for(int ii = 0; ii < 9; ii++){            for(int jj =0; jj < 9; jj++)            cout<<a[ii][jj];            cout<<endl;        }}bool DFS(int a[9][9],int i,int j){    if(i > 8){       // cout<<endl;        print(a);        //cout<<endl;       return true;    }    else{         bool flag_tmp;    if(a[i][j] == 0)    {        int ii;        for(ii =1 ;ii <= 9; ii++){            if(judge(a,i,j,ii) == true){                a[i][j] = ii;                if(j + 1 > 8 &&  !(flag_tmp = DFS(a,i+1,0)) )                    a[i][j] = 0;                else if(j + 1 <= 8 && !(flag_tmp = DFS(a,i,j+1)) )                    a[i][j] = 0;                else break;            }        }        if(!flag_tmp && ii > 9)            return false;        else return true;    }    else    {        if(j +1 > 8)            flag_tmp = DFS(a,i+1,0);        else            flag_tmp = DFS(a,i,j+1);        if(!flag_tmp)            return false;        else return true;    }    }}int main(){   // freopen("2.txt","w",stdout);   int n;   cin>>n;    int a[9][9];    char tmp;   while(n--){    memset(a,0,sizeof(a));    for(int i = 0; i < 9; i++)        for(int j = 0; j < 9; j ++)            {                cin>>tmp;                a[i][j] = tmp - ‘0‘;            }        //print(a);    DFS(a,0,0);   }    return 0;}