POJ 3074 Sudoku （Dancing Links）

#include<iostream>  
#include<cstring>  
#include<string>  
#include<cstdio>  
#include<algorithm>  
#include<vector>  
#include<algorithm>  
  
using namespace std;  
//   列：（行+列+塊）*9種可能+9*9個格子  
//   行： 9*9*9  表示第i行第j列填k  
const int MAXN=(9+9+9)*9+9*9+9*9*9*9*9*4+10;  
#define INF 0xFFFFFF  
int size;  
int head,sz;  
int U[MAXN],D[MAXN],L[MAXN],R[MAXN];  
int H[MAXN],ROW[MAXN],C[MAXN],S[MAXN],O[MAXN];  
  
void remove(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 resume(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;  
}  
  
bool dfs(int k)  
{  
    if(R[head]==head)  
    {  
        sort(O,O+9*9);  
        int p=0;  
        for(int i=0;i<9;i++)  
        {  
            for(int j=0;j<9;j++)  
            {  
                int num=O[p++];  
                //cout<<num<<endl;  
                num=num-(i*9+j)*9;  
                printf("%d",num);  
            }  
        }  
        printf("\n");  
        return  true;  
    }  
    int s=INF,c;  
    for (int t=R[head];t!=head;t=R[t])  
    {  
        if (S[t]<s)  
        {  
            s=S[t];  
            c=t;  
        }  
     }  
     remove(c);  
     for(int i=D[c];i!=c;i=D[i])  
     {  
          O[k]=ROW[i];  
          for(int j=R[i];j!=i;j=R[j])  
              remove(C[j]);  
          if(dfs(k+1))  
               return  true;  
          for(int j=L[i];j!=i;j=L[j])  
               resume(C[j]);  
     }  
     resume(c);  
     return  false;  
}  
  
void initDL(int n)  
{  
    head=0;  
    for(int i=0;i<=n;i++)  
    {  
        U[i]=i;D[i]=i;  
        L[i]=i-1;R[i]=i+1;  
        S[i]=0;  
    }  
    R[n]=0;L[0]=n;S[0]=INF+1;  
    sz=n+1;  
    memset(H,0,sizeof(H));  
}  
  
void insert(int i, int j)  
{  
    if(H[i])  
    {  
        L[sz]=L[H[i]];  
        R[sz]=H[i];  
        L[R[sz]]=sz;  
        R[L[sz]]=sz;  
    }  
    else  
    {  
        L[sz]=sz;  
        R[sz]=sz;  
        H[i]=sz;  
    }  
    U[sz]=U[j];  
    D[sz]=j;  
    U[D[sz]]=sz;  
    D[U[sz]]=sz;  
    C[sz]=j;  
    ROW[sz]=i;  
    ++S[j];  
    ++sz;  
}  
  
char str[200];  
  
void build()  
{  
    int p=0;  
    initDL(9*9*4);  
    for(int i=0;i<9;i++)  
        for(int j=1;j<=9;j++,p++)  
        {  
            int base=(i*9+j-1)*9;  
            if(str[p]=='.')  
            {  
                for(int k=1;k<=9;k++)  
                {  
                    int r;  
                    r=base+k;  
                    //第i行有數字k  
                    insert(r,i*9+k);  
                    //第j列有數字k  
                    insert(r,9*9+(j-1)*9+k);  
                    //第k塊有數字k  
                    int block=(j-1)/3*3+i/3;  
                    insert(r,9*9*2+block*9+k);  
                    //第i行j列有一個數字（限制一個格子只填一個數）  
                    insert(r,9*9*3+i*9+j);  
                }  
            }  
            else  
            {  
                int k=str[p]-'0';  
                int r=base+k;  
                //第i行有數字k  
                insert(r,i*9+k);  
                //第j列有數字k  
                insert(r,9*9+(j-1)*9+k);  
                //第k塊有數字k  
                int block=(j-1)/3*3+i/3;  
                insert(r,9*9*2+block*9+k);  
                //第i行j列有一個數字（限制一個格子只填一個數）  
                insert(r,9*9*3+i*9+j);  
            }  
        }  
}  
  
int main()  
{  
    size=9; //9*9數獨  
    while(~scanf("%s",str))  
    {  
        if(strcmp(str,"end")==0)  
            break;  
        build();  
        dfs(0);  
    }  
    return 0;  
}