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;
}