題目鏈接：點擊查看

題目大意：用更快的方法解數獨

題目分析：這個題和上一個題都是解數獨，但時間限制少了一秒鐘，難度卻上升了一個檔次，上一個題用暴力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)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。