模板

struct DLX{
    const static int maxn=4096+2,maxm=1024+2,maxcnt=maxm*maxn+2;
    int n,m,size,U[maxcnt],D[maxcnt],L[maxcnt],R[maxcnt],Row[maxcnt],Col[maxcnt],H[maxn],S[maxm],ansd,ans[maxn];
    void init(int _n,int _m){
        n=_n,m=_m,size=_m;
        for (int i=0;i<=m;++i){
            S[i]=0;
            U[i]=D[i]=i;
            L[i]=i-1,R[i]=i+1;
        }
        R[m]=0,L[0]=m;
        for (int i=1;i<=n;++i) H[i]=-1;
    }
    void link(int r,int c){
        S[Col[++size]=c]++;
        Row[size]=r;
        D[size]=D[c];
        U[D[c]]=size;
        U[size]=c;
        D[c]=size;
        if (H[r]<0) H[r]=L[size]=R[size]=size;
        else{
            R[size]=R[H[r]];
            L[R[H[r]]]=size;
            L[size]=H[r];
            R[H[r]]=size;
        }
    }
    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[Col[j]]--;
            }
        }
    }
    void resume(int c){
        L[R[c]]=R[L[c]]=c;
        for (int i=U[c];i!=c;i=U[i]){
            for (int j=L[i];j!=i;j=L[j]){
                U[D[j]]=D[U[j]]=j;
                S[Col[j]]++;
            }
        }
    }
    bool dfs(int dep){
        if (R[0]==0){
            ansd=dep;
            return 1;
        }
        int c=R[0];
        for (int i=R[0];i!=0;i=R[i]) if (S[i]<S[c]) c=i;
        remove(c);
        for (int i=D[c];i!=c;i=D[i]){
            ans[dep]=Row[i];
            for (int j=R[i];j!=i;j=R[j]) remove(Col[j]);
            if (dfs(dep+1)) return 1;
            for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);
        }
        resume(c);
        return 0;
    }
}dlx;

解数独模板 自定义LV

#include <bits/stdc++.h>
using namespace std;
#define LV 3
const static int len=LV*LV,sq=LV*LV*LV*LV;
struct DLX{
    const static int maxn=len*len*len+2,maxm=len*len*4+2,maxcnt=4*maxn+2;
    int n,m,size,U[maxcnt],D[maxcnt],L[maxcnt],R[maxcnt],Row[maxcnt],Col[maxcnt],H[maxn],S[maxm],ansd,ans[maxn];
    void init(int _n,int _m){
        n=_n,m=_m,size=_m;
        for (int i=0;i<=m;++i){
            S[i]=0;
            U[i]=D[i]=i;
            L[i]=i-1,R[i]=i+1;
        }
        R[m]=0,L[0]=m;
        for (int i=1;i<=n;++i) H[i]=-1;
    }
    void link(int r,int c){
        S[Col[++size]=c]++;
        Row[size]=r;
        D[size]=D[c];
        U[D[c]]=size;
        U[size]=c;
        D[c]=size;
        if (H[r]<0) H[r]=L[size]=R[size]=size;
        else{
            R[size]=R[H[r]];
            L[R[H[r]]]=size;
            L[size]=H[r];
            R[H[r]]=size;
        }
    }
    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[Col[j]]--;
            }
        }
    }
    void resume(int c){
        L[R[c]]=R[L[c]]=c;
        for (int i=U[c];i!=c;i=U[i]){
            for (int j=L[i];j!=i;j=L[j]){
                U[D[j]]=D[U[j]]=j;
                S[Col[j]]++;
            }
        }
    }
    bool dfs(int dep){
        if (R[0]==0){
            ansd=dep;
            return 1;
        }
        int c=R[0];
        for (int i=R[0];i!=0;i=R[i]) if (S[i]<S[c]) c=i;
        remove(c);
        for (int i=D[c];i!=c;i=D[i]){
            ans[dep]=Row[i];
            for (int j=R[i];j!=i;j=R[j]) remove(Col[j]);
            if (dfs(dep+1)) return 1;
            for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);
        }
        resume(c);
        return 0;
    }
}dlx;

int cnt=0,tmp[len*len*len+1],a[len+1][len+1];
char s[901];

void add(int x,int y,int v){
    cnt++;
    dlx.link(cnt,len*(x-1)+y);
    dlx.link(cnt,len*(x-1)+v+sq);
    dlx.link(cnt,len*(y-1)+v+sq*2);
    int t=((x-1)/LV)*LV+((y-1)/LV);
    dlx.link(cnt,len*t+v+sq*3);
    tmp[cnt]=160000*x+400*y+v;
}

bool sq_read(){
    // for (int i=1;i<=len;++i){
    //     for (int j=1;j<=len;++j){
    //         int t=(i-1)*len+j;
    //         if (s[t]=='.') a[i][j]=0,cnt+=len;
    //         else a[i][j]=s[t]-'0',cnt++;
    //     }
    // } //CNT changes
    return 1;
}

void sq_write(){
    // for (int i=1;i<=len;++i){
    //     for (int j=1;j<=len;++j){
    //         printf("%d",a[i][j]);
    //     }
    // }
}

void solve(){
    sq_read();
    dlx.init(cnt,sq*4);
    cnt=0;
    for (int i=1;i<=len;++i){
        for (int j=1;j<=len;++j){
            if (a[i][j]) add(i,j,a[i][j]);
            else for (int k=1;k<=len;++k) add(i,j,k);
        }
    }
    dlx.dfs(1);
    for (int i=1;i<=sq;++i){
        int t=tmp[dlx.ans[i]];
        int x=t/160000; t%=160000;
        int y=t/400; t%=400;
        int v=t;
        a[x][y]=v;
    }
    cnt=0;
    sq_write();
    puts("");
}

int main(){
    while (scanf("%s",s+1)){
        if (s[1]=='e') break;
        solve();
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/79/