POJ3074 sudoku

给定一个未完成的数独，要求把数独填完。

保证只有唯一解。

显然 每个格子最多填一个 每行每个数字最多一个 每列每个数字最多填一个 每个九宫格每个数字最多填一个 所以是个精确覆盖问题 可以用到DLX。

我们构造01矩阵A的时候可以这么构造：

第$9(i-1)+j$行($1\le j \le 9$)表示第i个格子填j。

第$1..81$列表示第1..81个格子。

第82..162列中第$9(i-1)+j+81$列表示第i行填j。

第163..243列中第$9(i-1)+j+162$列表示第i列填j。

第244..324列中第$9(i-1)+j+243$列表示第i个九宫格的填j。

然后对于第a个格子，设它在第b行第c列，属于第d个九宫格。

则$A_{a*9+s,a}=A_{a*9+s,(b-1)*9+s+81}=A_{a*9+s,(c-1)*9+s+162}=A_{a*9+s,(d-1)*9+s+243}=1$

其中$1\le s \le 9$，当第a个格子有固定值的时候s只能为这个值（千万注意后面三个位置也一样不然你会T飞的）。

然后就是裸的精确覆盖问题了，直接上DLX。

/*
Author: CNYALI_LK
LANG: C++
PROG: 3074.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
    int cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
    putchar(end);
}
const int fx[9]={0,0,0,3,3,3,6,6,6};
const int fy[9]={0,3,6,0,3,6,0,3,6};

struct node{
    node *l,*r,*u,*d;
    int x,y,del;
    node(int a=0,int b=0){
        x=a;y=b;del=0;
        l=r=u=d=NULL;
    } 
};
node *de[888],*re[888];
int n,m;
char s[888];
int cnt[888],dl[888],sel[888],Succ[888];
int need(char s){
    return isdigit(s)||s=='.';
}
int mygets(char *s){
    while(!need(*s=getchar()))if(*s=='e')return 0;
    ++s;
    while(need(*s=getchar()))++s;
    *s=0;
    return 1;
}
void Add(int x,int y){
    if(!Succ[x])return;
    ++x;++y;
    node *s=new node(x,y);
    s->l=re[x];
    s->u=de[y];
    if(re[x])re[x]->r=s;
    if(de[y])de[y]->d=s;
    re[x]=s;
    de[y]=s;
    ++cnt[y];
}
int a[10242],top;

void insert(int x){
    for(node *s=re[x];s;s=s->l){
        s->del=0;
        if(s->u)
        s->u->d=s;
        if(s->d)
        s->d->u=s;
        ++cnt[s->y];
    }
}
void remove(int x){
    if(re[x]->del)return;
    a[++top]=x;
    for(node *s=re[x];s;s=s->l){
        s->del=1;
        if(s->u)
        s->u->d=s->d;
        if(s->d)
        s->d->u=s->u;
        --cnt[s->y];
    }
}
void Remove(int x){
    for(node *a=re[x];a;a=a->l){
        dl[a->y]=1;
        for(node *b=a->u;b;b=b->u)remove(b->x);
        for(node *b=a->d;b;b=b->d)remove(b->x);
    }
    remove(x); 
}
int DLX(){
    int na=0,nb=n+5;    
    for(int i=1;i<=m;++i)if((!dl[i])&&chkmin(nb,cnt[i]))na=i;
    if(!na)return 1;
    if(!nb)return 0;
    int f=top;
    for(node *s=de[na];s;s=s->u)if(!s->del){
        sel[s->x]=1;
        Remove(s->x);
        if(DLX())return 1;
        sel[s->x]=0;
        for(node *a=re[s->x];a;a=a->l)dl[a->y]=0;
        while(top>f){
            insert(a[top]);
            --top;
        }
    }
    return 0;
}
int main(){
#ifdef cnyali_lk
    freopen("3074.in","r",stdin);
    freopen("3074.out","w",stdout);
#endif

    n=729;m=324;
    while(mygets(s)){
        for(int i=0;i<=n;++i)re[i]=NULL,sel[i]=Succ[i]=0;
        for(int i=0;i<=m;++i)de[i]=NULL,cnt[i]=dl[i]=0;
        top=0;
        for(int j=0;j<81;++j){
            if(s[j]=='.'){
                for(int i=0;i<9;++i){Succ[j*9+i]=1;Add(j*9+i,j);}
//              printf("%d!\n",j);
            }
            else{
                Succ[j*9+s[j]-'1']=1;
                Add(j*9+(s[j]-'1'),j);
            }
        }
        for(int i=0;i<81;++i){
            for(int j=0;j<9;++j){
                Add(((i/9)*9+j)*9+(i%9),81+i);
            }
        }
        for(int i=0;i<81;++i){
            for(int j=0;j<9;++j){
                Add((j*9+(i/9))*9+(i%9),162+i);
            }
        }
        for(int i=0;i<81;++i){
            for(int j=0;j<9;++j){
                Add(((fx[i/9]+j/3)*9+fy[i/9]+j%3)*9+(i%9),243+i);
            }
        }
        DLX();      
        for(int i=1;i<=n;++i)if(sel[i])putchar((i-1)%9+'1');
        putchar('\n');
    }   
    return 0;
}