舞蹈链（dancing links X）

舞蹈链算法，用于求解精确覆盖或者重复覆盖问题，目的是保证每一列的值最后为1或大于1，搜索中选用某一行后就将这一行以及它所解决的所有列删去，最后如果发现有列无法删去则失败，回溯并将之前删去的都恢复；如果最后发现所有列都被删去了，则说明问题解决。

它首先可以用来解决数独问题：转化为每行，每列，每个宫都有1~9，每格只有一个数字这个条件。是精确覆盖问题。

HDU3111题目链接

#include<bits/stdc++.h>
using namespace std;

const int N=350;
const int M=740;
const int inf=0x3f3f3f3f;

int m,n;
int u[M*N],d[M*N],r[M*N],l[M*N];
int cntc[N];
int c[M*N];
int head;
int op[M][N];
int res[M],idx;
int ans[10][10];

bool build(){
    int i,j,now,pre,first;
    idx=head=0;
    for(i=0;i<n;i++){
        r[i]=i+1;
        l[i+1]=i;
    }
    r[n]=0;
    l[0]=n;

    for(j=1;j<=n;j++){
        pre=j;
        cntc[j]=0;
        for(i=1;i<=m;i++){
            if(op[i][j]){
                now=i*n+j;
                c[now]=j;
                cntc[j]++;
                u[now]=pre;
                d[pre]=now;
                pre=now;
            }
        }
        u[j]=pre;
        d[pre]=j;
        if(cntc[j]==0)
            return false;
    }

    for(int i=1;i<=m;i++){
        pre=first=-1;
        for(j=1;j<=n;j++){
            if(op[i][j]){
                now=i*n+j;
                if(first==-1)
                    first=now;
                else{
                    r[pre]=now;
                    l[now]=pre;
                }
                pre=now;
            }
        }
        if(first!=-1){
            l[first]=pre;
            r[pre]=first;
        }
    }
    return true;
}

void remove(int col){
    int i,j;
    l[r[col]]=l[col];
    r[l[col]]=r[col];
    for(i=d[col];i!=col;i=d[i]){
        for(j=r[i];j!=i;j=r[j]){  //这一列的所有行都变为不可用，因为每列仅可覆盖一次
            u[d[j]]=u[j];
            d[u[j]]=d[j];
            cntc[c[j]]--;
        }
    }
}
void resume(int col){
    int i,j;
    r[l[col]]=col;
    l[r[col]]=col;
    for(i=d[col];i!=col;i=d[i]){
        for(j=r[i];j!=i;j=r[j]){
            u[d[j]]=j;
            d[u[j]]=j;
            cntc[c[j]]++;
        }
    }
}

bool dfs(){
    int i,j,col;
    if(r[head]==head)
        return true;
    int min=inf;
    for(i=r[head];i!=head;i=r[i]){
        if(cntc[i]<min){
            min=cntc[i];
            col=i;
        }
    }
    remove(col);
    for(i=d[col];i!=col;i=d[i]){
        res[idx++]=(i-1)/n;
        for(j=r[i];j!=i;j=r[j]){
            remove(c[j]);
        }
        if(dfs())
            return true;
        for(j=l[i];j!=i;j=l[j]){
            resume(c[j]);
        }
        idx--;
    }
    resume(col);
    return false;
}

void print(){
    int i,j,x,y,val;
    for(i=0;i<idx;i++){
        val=res[i]%9;
        if(val==0)
            val=9;
        int tmp=((res[i]-val)/9+1);
        y=tmp%9;
        if(y==0)
            y=9;
        x=(tmp-y)/9+1;
        ans[x][y]=val;
    }
    if(idx==0){
        cout<<"impossible"<<endl;
    }else{
        for(i=1;i<=9;i++){
            for(j=1;j<=9;j++)
                cout<<ans[i][j];
            cout<<endl;
        }
    }
}

int main(){
    int t;
    char s[10][10];
    char sep[10];
    cin>>t;
    for(int i=1;i<=t;i++){
        for(int i=1;i<=9;i++){
            scanf("%s",&s[i][1]);
        }
        if(i<t)
            scanf("%s",sep);
        memset(op,0,sizeof(op));

        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                int val=(i-1)*9+j;
                if(s[i][j]=='?'){
                    for(int k=1;k<=9;k++){
                        op[(val-1)*9+k][val]=1;
                        op[(val-1)*9+k][81+(i-1)*9+k]=1;
                        op[(val-1)*9+k][162+(j-1)*9+k]=1;
                        op[(val-1)*9+k][243+9*((i-1)/3*3+(j+2)/3-1)+k]=1;
                    }
                }else{
                    int k=s[i][j]-'0';
                    op[(val-1)*9+k][val]=1;
                    op[(val-1)*9+k][81+(i-1)*9+k]=1;
                    op[(val-1)*9+k][162+(j-1)*9+k]=1;
                    op[(val-1)*9+k][243+9*((i-1)/3*3+(j+2)/3-1)+k]=1;
                }
            }
        }
        n=324;
        m=729;
        build();
        dfs();
        print();
        if(i<t)
            cout<<"---"<<endl;
    }
    return 0;
}

接下来我们看另外一种问题，即重复覆盖问题，由于允许某一列的值累加大于1，故删除列的函数需要进行修改。之前我们删去某一列时，需要把这一列上所有的点对应的行都删去，因为我们已经选择了这一列，所以这些点只需要一个就够了；现在则没有这么强的限制，删去某一列时需要删掉这一列和其他列的连接，这一点是为了防止重复删去，因为还是要尽量避免选取某个值的位置重复的行。

舞蹈链 （dancing links X）

全站热榜

舞蹈链（dancing links X）