题解 P1784 【数独】

2018-07-05 13:19:11


做完靶形数独发现可以水经验,还能水题解

对于数独问题dancing links是很好的选择

先梳理一下关系:

  1. 每个点只能填一个数
  2. 每个行只能填每种数各一个
  3. 每个列只能填每种数各一个
  4. 每个宫只能填每种数各一个

于是我们把点对应成一个集合,包含4个元素,分别表示对应的数,行,列,宫。然后精确覆盖即可。

直接上代码吧,注释应该算比较详尽的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mx 100100//其实不用这么大只要大于729*324即可 
int sum=0;
int a[10][10];//每个点的数
inline int Read(){
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}//快读好习惯 
struct DLX{
    int n,m,cnt;//矩阵的长,宽,点的数量
    int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];//每个点的左,右,上下,行,列信息 
    int h[mx];//每行的头结点 
    int s[mx];//每列的结点数 
    int ansk[mx];//ansk[] 装答案(选了哪几行)
    void init(int _n,int _m){
        n=_n,m=_m;
        int i;
        for(i=0;i<=m;i++){
            r[i]=i+1;l[i]=i-1;u[i]=d[i]=i;
        }
        r[m]=0;//m右边是0 
        l[0]=m;//0左边是m 
        memset(h,-1,sizeof(h));
        memset(s,0,sizeof(s));
        cnt=m+1;//开始时有m个结点(0结点和各列头结点) 
    }//初始化,生成每列的头
    void link(int R,int C){
        s[C]++;
        row[cnt]=R;
        col[cnt]=C;
        u[cnt]=C;
        d[cnt]=d[C];
        u[d[C]]=cnt;
        d[C]=cnt;
        if(h[R]<0)h[R]=r[cnt]=l[cnt]=cnt;//该行没有别的点,把第一个加入的点作为该行的行头结点 
        else{
            r[cnt]=h[R];
            l[cnt]=l[h[R]];
            r[l[h[R]]]=cnt;
            l[h[R]]=cnt;
        }
        cnt++;
    }//在r行c列插入点
    void remove(int c){
        r[l[c]]=r[c],l[r[c]]=l[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]]--;
            }
        }
    }//删除c列和c列上有点的行
    void resume(int c){
        for(int i=u[c];i!=c;i=u[i]){
            for(int j=l[i];j!=i;j=l[j]){
                u[d[j]]=j;
                d[u[j]]=j;
                s[col[j]]++;
            }
        }
        r[l[c]]=c;
        l[r[c]]=c;
    }//恢复c列和c列上有点的行
    bool dance(int deep){
        if(r[0]==0){
            int x,y,v;
            for(int i=0;i<deep;i++){
            x=(ansk[i]-1)/9/9;
            y=(ansk[i]-1)/9%9;
            v=(ansk[i])%9;//把行信息转换成对应的点的值 
            if(v==0)v=9;//防止9的倍数%9==0 
            a[x][y]=v;
            }
            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]){
            ansk[deep]=row[i];
            for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
            if(dance(deep+1)==1)return 1;//只要找一组解 
            for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
        }
        resume(c); 
        return false;
    }
}dlx;
int main(){
    dlx.init(729,324);
    //729:
    //9^4种情况对应9^4行;
    //324:
    //对应数独的规则:每个格子,每行,每列,每个九宫只能填1~9各一次 
    //对于第m列:
    //若m在[1,81]表示在(m/9,m%9)填数 
    //若m在[81*1,81*2]在第1+(m-81)/9行填1+(m-81)%9 
    //若m在[81*2,81*3]在第1+(m-81*2)/9列填1+(m-81*2)%9 
    //若m在[81*3,81*4]在第1+(m-81*3)/9宫填1+(m-81*3)%9
    int x;
    int o;
    for(int i=0;i<=8;i++){
        for(int j=0;j<=8;j++){
        a[i][j]=x=Read();
         for(int k=1;k<=9;k++){
            if(x!=k&&x!=0)continue;//已经填好的点就不用考虑了 
            o=i*9*9+j*9+k;
            dlx.link(o,i*9+j+1);
            dlx.link(o,i*9+81+k);
            dlx.link(o,j*9+81*2+k);
            dlx.link(o,81*3+(i/3*3+j/3)*9+k);//把点对应成行(集合) 
         }
         }
     }
     dlx.dance(0);
    for(int i=0;i<=8;i++){
        for(int j=0;j<=8;j++)printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}

看不懂可以发讨论

求赞

另外,如果想练dancing links 可以试一下靶形数独八皇后