首页 > 代码库 > 数独破解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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。