51nod 1211 数独

数独游戏规则如下：在9 * 9的盘面上有些已知的数字及未知的数字，推理出所有未知的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。

 

 

 

有些局面存在多个解或无解，这属于不标准的数独。对于不标准的局面，输出No Solution。

Input

第1 - 9行，每行9个数中间用空格分隔，0表示该格子的数未知。

Output

如果局面是不标准的，输出No Solution，否则数据具体的解。

转化为精确覆盖问题用dlx算法求解

共324列表示每行、列、3x3区域中有且只有每种数字一个，每个位置只能填一个数

共729行表示81个格子，填1~9的所有可能

#include<bits/stdc++.h>
const int N=10007;
int l[N],r[N],u[N],d[N],rid[N],cid[N],idp=325,n0=325;
int stk[1007],stp=0,ed=0;
int ds[753][329];
int vs[11][11],cs[1007];
void del(int mw){
    l[r[mw]]=l[mw];
    r[l[mw]]=r[mw];
    for(int w=d[mw];w!=mw;w=d[w]){
        for(int v=r[w];v!=w;v=r[v]){
            u[d[v]]=u[v];
            d[u[v]]=d[v];
            --cs[cid[v]];
        }
    }
}
void ins(int mw){
    l[r[mw]]=r[l[mw]]=mw;
    for(int w=d[mw];w!=mw;w=d[w]){
        for(int v=r[w];v!=w;v=r[v]){
            u[d[v]]=d[u[v]]=v;
            ++cs[cid[v]];
        }
    }
}
bool dfs(){
    if(r[n0]==n0){
        if(ed)puts("No Solution"),exit(0);
        ed=1;
        for(int i=0;i<stp;++i){
            int x=stk[i]-1;
            vs[x/81+1][x/9%9+1]=x%9+1;
        }
    }
    int mn=100000,mw=0;
    for(int w=r[n0];w!=n0;w=r[w])if(cs[w]<mn)mn=cs[mw=w];
    del(mw);
    for(int w=d[mw];w!=mw;w=d[w]){
        stk[stp++]=rid[w];
        for(int v=r[w];v!=w;v=r[v])del(cid[v]);
        dfs();
        for(int v=r[w];v!=w;v=r[v])ins(cid[v]);
        --stp;
    }
    ins(mw);
    return 0;
}
int main(){
    for(int i=1;i<=9;++i)for(int j=1;j<=9;++j)scanf("%d",vs[i]+j);
    for(int i=1;i<=9;++i)for(int j=1;j<=9;++j)for(int k=1;k<=9;++k)if(!vs[i][j]||vs[i][j]==k){
        int a=(i-1)*81+(j-1)*9+k;
        ds[a][(i-1)*9+k]=++idp;
        ds[a][81+(j-1)*9+k]=++idp;
        ds[a][162+((i-1)/3*3+(j-1)/3)*9+k]=++idp;
        ds[a][243+(i-1)*9+j]=++idp;
    }
    for(int i=1;i<=324;++i){
        l[i+1]=i,r[i]=i+1;
        int p=i;
        for(int j=1;j<=729;++j)if(int w=ds[j][i]){
            d[p]=w,u[w]=p;
            p=w;
            ++cs[i];
        }
        u[i]=p,d[p]=i;
        if(!cs[i])return puts("No Solution"),0;
    }
    l[1]=n0,r[n0]=1;
    for(int i=1;i<=729;++i){
        int p=0,p0;
        for(int j=1;j<=324;++j)if(int w=ds[i][j]){
            if(p)r[p]=w,l[w]=p;
            else p0=w;
            p=w;
            rid[w]=i;
            cid[w]=j;
        }
        if(p)r[p]=p0,l[p0]=p;
    }
    dfs();
    if(!ed)return puts("No Solution"),0;
    for(int i=1;i<=9;++i){
        for(int j=1;j<=9;++j)printf("%d ",vs[i][j]);
        putchar(10);
    }
    return 0;
}