分析：
dlx是从数据结构角度优化01矩阵精确覆盖和重复覆盖的数据结构，它用十字链表只存贮矩阵中的非0元，而01矩阵精确覆盖dfs过程中矩阵会越来越稀疏而且每次恢复现场会浪费大量时间，，dlx恰好能解决这两个问题。本题关键是将数独问题转化为01矩阵精确覆盖。数独转化为精确覆盖问题的方法还是参照Knuth的论文，如果读取到一个格子是空的，那么加9行，分别表示这个格子填1到9这9个数字，如果读取到的格子是一个数字，那么就加一行就可以了，然后列有9*9*4列，前81列表示这一行表示填的是第i行第j列的格子，接下来81列表示第i行填写k，接下来81列表示第j列填写k，最后81列表示对应九宫格填写k。//poj 3074//sep9#include <cstdio>#include <cstdlib>#define INT_MAX 2147483647using namespace std;const int MAX=1024;const int col_num=9*9*4;const int head=0;const int delta[]={1,82,163,244};int cnt[MAX],st[MAX];int left[MAX*MAX],right[MAX*MAX],up[MAX*MAX],down[MAX*MAX];int row[MAX*MAX],col[MAX*MAX];int K,M;//k:node's idx M:row's numberstruct ANS{int r,c,k;}ans[MAX*MAX];void init(){left[head]=col_num;right[head]=1;up[head]=down[head]=head;for(int i=1;i<=col_num;++i){left[i]=i-1;right[i]=(i+1)%(col_num+1);up[i]=down[i]=i;cnt[i]=0;col[i]=i;row[i]=0;}M=0;K=col_num;}int make_col_head(int c){++K;++cnt[c];col[K]=c;row[K]=M;left[K]=right[K]=K;up[K]=c;down[K]=down[c];up[down[K]]=K;down[up[K]]=K;return K;}void addcol(int ids,int c){++K;++cnt[c];col[K]=c;row[K]=M;left[K]=ids;right[K]=right[ids];left[right[K]]=K;right[left[K]]=K;up[K]=c;down[K]=down[c];up[down[K]]=K;down[up[K]]=K;}void addrow(int i,int j,int k){++M;ans[M].r=i;ans[M].c=j;ans[M].k=k+1;int ids=make_col_head(9*i+j+delta[0]);addcol(ids,9*i+k+delta[1]);addcol(ids,9*j+k+delta[2]);addcol(ids,9*(i/3*3+j/3)+k+delta[3]);}void remove(int c){left[right[c]]=left[c];right[left[c]]=right[c];for(int i=down[c];i!=c;i=down[i])for(int j=right[i];j!=i;j=right[j]){up[down[j]]=up[j];down[up[j]]=down[j];–cnt[col[j]];}}void resume(int c){for(int i=up[c];i!=c;i=up[i])for(int j=left[i];j!=i;j=left[j]){down[up[j]]=j;up[down[j]]=j;++cnt[col[j]];}left[right[c]]=c;right[left[c]]=c;}bool dfs(int k){if(right[head]==head){char s[128];for(int i=0;i<k;++i)s[ans[st[i]].r*9+ans[st[i]].c]=ans[st[i]].k+'0';s[81]='\0';puts(s);return true;}int s=INT_MAX,c=0;for(int i=right[head];i!=head;i=right[i]){if(cnt[i]<s){s=cnt[i];c=i;}}remove(c);for(int i=down[c];i!=c;i=down[i]){st[k]=row[i];for(int j=right[i];j!=i;j=right[j])remove(col[j]);if(dfs(k+1))return true;for(int j=left[i];j!=i;j=left[j])resume(col[j]);}resume(c);return false;} int main(){char s[128];while(scanf("%s",s)==1&&s[0]!='e'){init();for(int i=0;i<9;++i)for(int j=0;j<9;++j)if(s[i*9+j]=='.'){for(int k=0;k<9;++k)addrow(i,j,k);}elseaddrow(i,j,s[i*9+j]-'1');dfs(0);}return 0;}
往往为了自己的不能失败，而处心积虑前怕狼后怕虎，
