https://blog.csdn.net/xiaozhuaixifu/article/details/12253507
给定一个不完整9*9数独,
未填部分用0表示,
恢复数独,并打印
在读入的时候,
我们开几个数组,
sudoku[9][9],相当于这张数独地图,上面记录值
checkrow[9][10],第i行,是否出现过数v,1<=v<=9
checkcol[9][10],第j列,是否出现过数v,1<=v<=9
square[9][10],第k块,是否出现过数v,1<=v<=9
块的定义,
即图片中汉字数字顺序,对应0-8块,
k=i/3*3+j/3可表示。
//图片来源于网络http://blog.sina.com.cn/s/blog_4e92a29f010171dc.html
我们从(0,0)开始dfs,
如果行末,就dfs下一行行首;
如果非行末,就dfs本行下一列,
如果到(9,0)了,说明前面均无冲突。
然后就是dfs经典三段论。
①试数,对应修改
②向更深层次搜索
③(如果能到这里,说明②失败)将①还原
博主这篇文章真的是好评,
代码风格也很好,剪枝也减的恰到好处,
搜到一个可行解,isdone就返回,
虽然没加一句注释,但通俗易懂。
QAQ数独的确是一种经典题,还是要多练为妙
全oj大概有那么五六个数独题吧,
16*16的,靶型数独的,以后再补吧
讲道理,贴代码里面的i,个人觉得,好吃藕
#include <iostream> #include <algorithm> #include <cstring> #include <string.h> #include <cstdio> #include <cmath> #include <set> #include <vector> #include <stack> #include <queue> #include <map> const double INF=0x3f3f3f3f; const int maxn=1e5+10; const int mod=1e9+7; const int MOD=998244353; const double eps=1e-7; typedef long long ll; #define vi vector<int> #define si set<int> #define pii pair<int,int> #define pi acos(-1.0) #define pb push_back #define mp make_pair #define lowbit(x) (x&(-x)) #define sci(x) scanf("%d",&(x)) #define scll(x) scanf("%lld",&(x)) #define sclf(x) scanf("%lf",&(x)) #define pri(x) printf("%d",(x)) #define rep(i,j,k) for(int i=j;i<=k;++i) #define per(i,j,k) for(int i=j;i>=k;--i) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; char tmp[9]; int sudoku[9][9]; bool square[9][10];//第i个3*3块,数j是否已经出现 bool checkrow[9][10];//第i行,数j是否已经出现 bool checkcol[9][10];//第i列,数j是否已经出现 bool isdone;//是否搜到一个可行解 void init() { mem(checkrow,0); mem(checkcol,0); mem(square,0); isdone=0; } void dfs(int i,int j)//当前判sodaku[i][j]是否合法 { if(i==9) { isdone=1;//搜到一个答案 rep(i,0,8) { rep(j,0,8) { printf("%d",sudoku[i][j]); } puts(""); } return; } if(isdone)return;//已经搜到一个可行解了,把剩下的剪枝 if(sudoku[i][j])//这里已经置入一个数了 { if(j==8)dfs(i+1,0);//搜到行末了,新开一行 else dfs(i,j+1); } else { rep(v,1,9) { int k=i/3*3+j/3;//第k块 if(!checkrow[i][v]&&!checkcol[j][v]&&!square[k][v])//o(1)查重的操作 { //先试试,v能不能行 sudoku[i][j]=v; checkrow[i][v]=1; checkcol[j][v]=1; square[k][v]=1; //向后续搜索 if(j==8)dfs(i+1,0); else dfs(i,j+1); //能运行到这句,说明不行,改回来 sudoku[i][j]=0; checkrow[i][v]=0; checkcol[j][v]=0; square[k][v]=0; } } } } int main() { int t; sci(t); while(t--) { init(); rep(i,0,8) { scanf("%s",tmp); rep(j,0,8) { int v=tmp[j]-'0'; sudoku[i][j]=v; if(v) { int k=i/3*3+j/3;//第k块 checkrow[i][v]=1;//i行出现过v checkcol[j][v]=1;//j列出现过v square[k][v]=1;//k块出现过v } } } dfs(0,0); } return 0; }