题目链接：点击查看

题目大意：用更快的方法解数独

题目分析：这个题和上一个题都是解数独，但时间限制少了一秒钟，难度却上升了一个档次，上一个题用暴力dfs完全可以跑出来，不过要用1.5秒左右的时间，所以这个题目直接暴力跑肯定是不行的，我们可以考虑优化一下，比如更巧妙的剪枝，或者用位运算CSP（constraint satisfaction problem)来解决，不过我觉得最好的办法还是用DLX算法，这是半年之前从网上就看到过的一个很厉害的算法，可以完美解决精确覆盖问题，当时看了别人的博客学了有一阵子但还是没学懂，这两天又碰到了这个数独题，就决定去学一下，原理差不多搞明白了，主要是把模板学会了，然后就可以为所欲为的用模板了（菜鸡行为），也算是对DLX的一个初步了解入门吧，实际上应该将这个算法当做一个工具来使用，而不是当做一种固定的模板来使用，不然会很大程度上的限制住思维，从而陷入思维定式，现在说这个还有点远了，眼前的目标就是用DLX解决掉最简单的数独问题吧。。

这里有个大佬的博客：DLX详解

还有用DLX解数独的思路：DLX解数独

这里有必要解释一下代码中的encode和decode函数，一开始我也是不太理解的，为什么增加节点的时候encode(0,i,j)什么的，最后输出答案的时候却是decode(x,y,v)？不应该是decode(0,x,y)吗？这都什么乱七八糟的，这里需要结合一下DLX这个算法来解释一下，DLX精确覆盖，我自己理解的定义是这样的：

在一个01矩阵中选出某几行，以列为单位，使得这几行中的所有1所在的列的交集为∅，所有1所在的列的并集为矩阵的宽度。

在看过上面两个博客后，应该不难理解上面这个定义的意思，那么我们在一开始初始化(init)的时候，输入的那个n就是矩阵的宽度，也就是一共有多少列

随后增加节点，加入的节点的格式是这样的AddNode(int r,int c)，要求输入的形参为行+列，列的话我们已经规定好了谁是谁，那么行的话我们该怎么确定呢？因为针对于数独这个题目，最大的行数只有9*9*9行，为什么呢？因为最坏情况是一个空的矩阵，也就是一开始的数独全都是0，那么每个点都有九种情况需要加入节点，也就是(矩阵长度*矩阵宽度)*每个点的情况种类=9*9*9种，那么我们完全可以用九进制来表示这样一个数，比如(x,y,v)，就表示在点（x，y）的值为v，我们可以直接用这个九进制的数来表示矩阵中的行，矩阵中的列我就不用过多赘述了，上面的博客已经讲得很清楚了

这样一来，最后DLX求出的答案，也就是dlx.A数组中储存的到底是什么呢，储存的都是第几行，针对于数独这个题目，因为肯定会有81个数字才能组成9*9的数字矩阵，所以一定会有81个不同的行储存在最后的答案中，也就是说最后解码的是行的序列，而行的序列是由一个九进制的数字来表示的(x,y,v)，所以我们就解码出来了在点（x，y）的值为v

过多的我就不赘述了，这个代码跑了79ms，真的惊艳到我了

直接挂代码吧：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=9*9*9+100;//行数const int M=9*9*4+100;//列数const int NODE=9*9*9*4+100;//节点数struct DancingLink{int n,s,ansd;//列数 节点总数 int S[M],A[N],H[N];//S[]该列节点总数 A[]答案 H[]行首指针 int L[NODE],R[NODE],U[NODE],D[NODE]; //L[],R[],U[],D[] 上下左右 int X[NODE],C[NODE];//X[] C[] 行列编号 void init(int n){//初始化 this->n=n;for(int i=0;i<=n;i++)U[i]=i,D[i]=i,L[i]=i-1,R[i]=i+1;R[n]=0,L[0]=n;s=n+1;memset(S,0,sizeof(S));memset(H,-1,sizeof(H));}void DelCol(int c){//删除列 L[R[c]]=L[c];R[L[c]]=R[c];for(int i=D[c];i!=c;i=D[i])for(int j=R[i];j!=i;j=R[j])U[D[j]]=U[j],D[U[j]]=D[j],--S[C[j]];}void ResCol(int c){//恢复列 for(int i=U[c];i!=c;i=U[i])for(int j=L[i];j!=i;j=L[j])++S[C[j]],U[D[j]]=j,D[U[j]]=j;L[R[c]]=c,R[L[c]]=c;}void AddNode(int r,int c){//添加节点 ++S[c],C[++s]=c,X[s]=r;D[s]=D[c],U[D[c]]=s,U[s]=c,D[c]=s;if(H[r]<0) H[r]=L[s]=R[s]=s;//行首节点else R[s]=R[H[r]],L[R[H[r]]]=s,L[s]=H[r],R[H[r]]=s;}bool dfs(int d){//深度，深搜遍历 if(!R[0]){ansd=d;return true;}int c=R[0];for(int i=R[0];i;i=R[i]) if(S[i]<S[c]) c=i;DelCol(c);for(int i=D[c];i!=c;i=D[i]){A[d]=X[i];for(int j=R[i];j!=i;j=R[j]) DelCol(C[j]);if(dfs(d+1)) return true;for(int j=L[i];j!=i;j=L[j]) ResCol(C[j]);}ResCol(c);return false;}}dlx; int maze[10][10];char ans[100];int encode(int x,int y,int v) {return x*9*9+y*9+v+1; }void decode(int num,int &x,int &y,int &v) {num--;v=num%9;num/=9;y=num%9;num/=9;x=num%9; }int main() { // freopen("input.txt","r",stdin);string s;while(cin>>s&&s!="end"){for(int i=0;i<9;i++)for(int j=0;j<9;j++)maze[i][j]=s[i*9+j]=='.'?0:s[i*9+j]-'0';dlx.init(9*9*4);for(int i=0;i<9;i++)for(int j=0;j<9;j++)for(int k=0;k<9;k++)if(!maze[i][j]||maze[i][j]==k+1){int x=encode(i,j,k);dlx.AddNode(x,encode(0,i,j));dlx.AddNode(x,encode(1,i,k));dlx.AddNode(x,encode(2,j,k));dlx.AddNode(x,encode(3,i/3*3+j/3,k));}dlx.dfs(0);for(int i=0;i<dlx.ansd;i++){int x,y,v;decode(dlx.A[i],x,y,v);ans[x*9+y]=v+'0'+1;}ans[dlx.ansd]=0;printf("%s\n",ans);} return 0; }

 

总结

以上是生活随笔为你收集整理的POJ - 3074 Sudoku(DLX)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。