B32 Dancing Links 舞蹈链 数独

B32 Dancing Links 舞蹈链 数独

9*9的dancing links代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3245; //点729*4+列头324
int n,m,cnt; //矩阵的长,宽,点的编号
int u[N],d[N],l[N],r[N]; //每个点的上下左右
int row[N],col[N]; //每个点所在行,列
int h,t;  //每行的头,尾指针
int s[N]; //每列的节点数
int ans[N]; //选了那些行
int a[10][10];//数独的数

void init(){ //初始化第0行的列表头
  for(int y=0; y<=m; y++){
    u[y]=d[y]=y;
    l[y]=y-1; r[y]=y+1;
  }
  l[0]=m; r[m]=0; cnt=m+1; //下一个点的编号
}
void link(int x,int y){ //在x行y列插入点 
  row[cnt]=x; col[cnt]=y; s[y]++;
  u[cnt]=u[y]; //y...u[y]←→cnt←→y
  d[u[y]]=cnt;
  d[cnt]=y;
  u[y]=cnt;
  l[cnt]=t; //h...t←→cnt←→h
  r[t]=cnt;
  r[cnt]=h;
  l[h]=cnt;
  t=cnt++; //t指向cnt, 然后cnt+1
}
void remove(int y){ //删除y列与关联行
  r[l[y]]=r[y], l[r[y]]=l[y]; 
  for(int i=d[y]; i!=y; 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 y){ //恢复y列与关联行
  r[l[y]]=y, l[r[y]]=y;  
  for(int i=u[y]; i!=y; i=u[i])   //向上
    for(int j=l[i]; j!=i; j=l[j]) //向左
      u[d[j]]=j, d[u[j]]=j, s[col[j]]++;
}
bool dance(int dep){
  if(r[0]==0){
    for(int i=0,x,y,v;i<dep;i++){
      x=(ans[i]-1)/9/9; //链表行→数独
      y=(ans[i]-1)/9%9;
      v=(ans[i])%9;
      a[x][y]=v?v:9; 
    }
    for(int i=0;i<=8;i++){
      for(int j=0;j<=8;j++)printf("%d ",a[i][j]);
      puts("");

B32 Dancing Links 舞蹈链 数独

9*9的dancing links代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3245; //点729*4+列头324 int n,m,cnt; //矩阵的长,宽,点的编号 int u[N],d[N],l[N],r[N]; //每个点的上下左右 int row[N],col[N]; //每个点所在行,列 int h,t; //每行的头,尾指针 int s[N]; //每列的节点数 int ans[N]; //选了那些行 int a[10][10];//数独的数

void init(){ //初始化第0行的列表头 for(int y=0; y<=m; y++){ u[y]=d[y]=y; l[y]=y-1; r[y]=y+1; } l[0]=m; r[m]=0; cnt=m+1; //下一个点的编号 } void link(int x,int y){ //在x行y列插入点 row[cnt]=x; col[cnt]=y; s[y]++; u[cnt]=u[y]; //y...u[y]←→cnt←→y d[u[y]]=cnt; d[cnt]=y; u[y]=cnt; l[cnt]=t; //h...t←→cnt←→h r[t]=cnt; r[cnt]=h; l[h]=cnt; t=cnt++; //t指向cnt, 然后cnt+1 } void remove(int y){ //删除y列与关联行 r[l[y]]=r[y], l[r[y]]=l[y]; for(int i=d[y]; i!=y; 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 y){ //恢复y列与关联行 r[l[y]]=y, l[r[y]]=y;
for(int i=u[y]; i!=y; i=u[i]) //向上 for(int j=l[i]; j!=i; j=l[j]) //向左 u[d[j]]=j, d[u[j]]=j, s[col[j]]++; } bool dance(int dep){ if(r[0]0){ for(int i=0,x,y,v;i<dep;i++){ x=(ans[i]-1)/9/9; //链表行→数独 y=(ans[i]-1)/9%9; v=(ans[i])%9; a[x][y]=v?v:9; } for(int i=0;i<=8;i++){ for(int j=0;j<=8;j++)printf("%d ",a[i][j]); puts(""); } return True; } int y=r[0]; //找到点最少的列 for(int i=r[0];i;i=r[i]) if(s[i]<s[y])y=i; remove(y); for(int i=d[y];i!=y;i=d[i]){ ans[dep]=row[i]; for(int j=r[i];j!=i;j=r[j]) remove(col[j]); if(dance(dep+1)) return True; for(int j=l[i];j!=i;j=l[j]) resume(col[j]); } resume(y); return False; } int main(){ n=729; m=324; init(); for(int i=0; i<9; i++){ //数独的行 for(int j=0,x; j<9; j++){ //数独的列 scanf("%d",&x);a[i][j]=x; for(int k=1; k<=9; k++){ //9个数 if(x0||x==k){ h=t=cnt; //每行的第一个点 int r=i99+j9+k; //数独→链表行 link(r,i9+j+1); link(r,811+i9+k); link(r,812+j9+k); link(r,813+(i/33+j/3)*9+k); } } } } dance(0); }</pre>

//by:hansang 代码来源于 y总
//注释里的方格指Sudoku中的196个小方格,大方格指16个大方格 
//代码很长,分段记比较好 
#include<bits/stdc++.h>
using namespace std;
 
const int N = 16;
 
int Map[1 << N], ones[1 << N]; //Map[i]表示 i是2的几次方,ones[i]表示 i里面有几个1 
int state[N][N]; //state[i][j]是一串二进制数,第 k位的1表示这个位置能填 k+'A'-1
int bstate[N*N + 1][N][N], bstate2[N*N + 1][N][N]; //备份  
char str[N][N + 1];
char bstr[N*N + 1][N][N + 1];
 
inline int lowbit(int x){return x&-x;} //是 x的二进制数中最低位的 1所对应的值
 
void draw(int x, int y, int c)
{
    str[x][y]='A'+c;
 
    for(int i=0; i<N; i++) //同行同列的数都不能填 'A'+c
    {
        state[x][i] &= ~(1 << c); //其他位都不变,第 c位如果是 1的话变成 0 
        state[i][y] &= ~(1 << c);
    }
 
    int sx=x/4*4, sy=y/4*4; //x y所在的大方格的左上角 
    //同一个方格的数都不能填 'A'+c
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++) 
            state[sx+i][sy+j] &= ~(1 << c);
 
    state[x][y] = 1 << c; //这个方格填了 'A'+c
}
 
bool dfs(int cnt)
{
    if (!cnt) return 1;
 
    int kcnt=cnt;
    memcpy(bstate[kcnt], state, sizeof state);
    memcpy(bstr[kcnt], str, sizeof str); //备份 
     
    for(int i=0; i<N; i++ )
        for(int j=0; j<N; j++ )
            if(str[i][j]=='-')
            {
                if(!state[i][j]) // 每个空方格如果不能填则返回 0
                {
                    memcpy(state, bstate[kcnt], sizeof state);
                    memcpy(str, bstr[kcnt], sizeof str); //拷回去
                    return 0;
                }
 
                if(ones[state[i][j]]==1)//如果只有一个选项,则直接填上
                {
                    draw(i, j, Map[state[i][j]]);
                    cnt--;
                }
            }
 
    // 每一行如果某个字母不能填，则返回False；如果某个字母只有一种填法，则直接填
    for(int i=0; i<N; i++)
    {
        int sor=0, sand=(1<<N) - 1; //sor是一串二进制数,第 k位的1表示这行能填k-'A'+1 (判断用)    sand和sor一样 (计算用)
        int drawn=0; //drawn是一串二进制数,第 k位的1表示这行   *填了*   k-'A'+1
        for(int j=0; j<N; j++)
        {
            int s = state[i][j];
            sand &= ~(sor & s); //要是有以前的方格也能填和 str[i][j]一样能填的数,就在 sand中删去 
            sor |= s; //str[i][j]能填的,这一行也能填 
 
            if (str[i][j]!='-') drawn |= s;
        }
 
        if(sor!=(1 << N)-1) //正常来说,一行能填所有数,否则无解 
        {
            memcpy(state, bstate[kcnt], sizeof state);
            memcpy(str, bstr[kcnt], sizeof str);
            return 0;
        }
 
        for(int j=sand; j; j-=lowbit(j)) //能填的先填 
        {
            int t=lowbit(j);
            if (!(drawn&t)) //没填过的 
            {
                for(int k=0; k<N; k++)
                    if(state[i][k]&t) //在第 k个位置上是 1 
                    {
                        draw(i, k, Map[t]);
                        cnt -- ;
                        break;
                    }
            }
        }
    }
 
    // 每一列，如果某个字母不能填，则返回False；如果某个字母只有一种填法，则直接填
    //打完行的直接复制就好,注意 i j 交换和 k i 交换     (懒得打注释啦) 
    for(int i=0; i<N; i++)
    {
        int sor=0, sand=(1 << N)-1;
        int drawn=0;
        for(int j=0; j<N; j++)
        {
            int s=state[j][i];
            sand &= ~(sor & s);
            sor|=s;
 
            if (str[j][i] != '-') drawn |= s;
        }
 
        if(sor!=(1 << N)-1)
        {
            memcpy(state, bstate[kcnt], sizeof state);
            memcpy(str, bstr[kcnt], sizeof str);
            return 0;
        }
 
        for(int j=sand; j; j-=lowbit(j))
        {
            int t=lowbit(j);
            if(!(drawn & t))
            {
                for(int k=0; k<N; k++)
                    if(state[k][i]&t)
                    {
                        draw(k, i, Map[t]);
                        cnt -- ;
                        break;
                    }
            }
        }
    }
 
    // 每个16宫格，如果某个字母不能填，则返回False；如果某个字母只有一种填法，则直接填
    //打完行的直接复制就好,注意 i j 替换 sx+dx sy+dy,特殊情况 i k 替换 sx+dx sy+dy
    for(int i=0; i<N; i++)
    {
        int sor=0, sand=(1 << N)-1;
        int drawn=0;
        for(int j=0; j<N; j++)
        {
            int sx=i/4 *4, sy=i%4 *4; //i所在的大方格的左上角 
            int dx=j/4, dy=j%4; //每个九宫格里的相对位置 
            int s=state[sx+dx][sy+dy];
            sand &= ~(sor & s);
            sor|=s;
 
            if (str[ sx+dx ][ sy+dy ]!='-') drawn|=state[ sx+dx ][ sy+dy ];
        }
 
        if(sor!=(1<<N)-1)
        {
            memcpy(state, bstate[kcnt], sizeof state);
            memcpy(str, bstr[kcnt], sizeof str);
            return 0;
        }
        for(int j=sand; j; j-=lowbit(j))
        {
            int t=lowbit(j);
            if(!(drawn&t))
            {
                for(int k=0; k<N; k++)
                {
                    int sx=i/4 *4, sy=i%4 *4;
                    int dx=k/4, dy=k%4;
                    if(state[sx+dx][sy+dy] & t)
                    {
                        draw(sx+dx, sy+dy, Map[t]);
                        cnt -- ;
                        break;
                    }
                }
            }
        }
    }
 
    if (!cnt) return 1; //注意这里改成cnt==0可能过不了！ 
 
    int x, y, s=100; 
    for(int i=0; i<N; i++) //寻找选择最少的方格 
        for(int j=0; j<N; j++)
            if(str[i][j]=='-' && ones[state[i][j]]<s)
            {
                s=ones[state[i][j]];
                x=i; y=j;
            }
 
    memcpy(bstate2[kcnt], state, sizeof state);
    for(int i=state[x][y]; i; i-=lowbit(i)) //把还有选择的方格都过一遍 
    {
        memcpy(state, bstate2[kcnt], sizeof state); //每做一次就拷回去 
        draw(x, y, Map[lowbit(i)]);
        if(dfs(cnt-1)) return 1;
    }
 
    memcpy(state, bstate[kcnt], sizeof state);
    memcpy(str, bstr[kcnt], sizeof str);
    return 0;
}
 
int main()
{
    for(int i=1; i<N; i++) Map[1<<i]=i; //2的i次方=i 
    for(int i=0; i<(1<<N); i++) for(int j=i; j; j-=lowbit(j)) ones[i]++; //i里面有几个1 
 
    while(cin>>str[0]) //用cin能避免读入空格 换行 
    {
        for(int i=1; i<N; i++) cin>>str[i];
 
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                state[i][j]=(1<<N) - 1; //初始化为15个1 
 
        int cnt=0;
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                if(str[i][j] != '-')draw(i, j, str[i][j]-'A'); //格子里有数就表记 
                else cnt++; //有cnt个要填的格子 
 
        dfs(cnt);
        for(int i=0; i<N; i++) printf("%s\n",str[i]);
        printf("\n");
    }
    return 0;
}