Dancing Links X 算法

2014.12.05 13:00 Fri| 4 visits oi_2015| 2015_算法笔记| Text

舞蹈链其实明明就是一个名字比较有爱的十字链表嘛~

感谢18357同志不厌其烦地对我等蒟蒻的讲解令我学习到了这么高端的算法,虽然它貌似只是用来解数独的……

三种覆盖问题

  • 精确覆盖问题(Exact Cover Problem)
    在一个全集X中若干子集的集合为S,精确覆盖是指,S的子集S*,满足X中的每一个元素在S*中恰好出现一次。在计算机科学中,精确覆盖问题指找出这样的一种覆盖,或证明其不存在。这是一个NP-完全问题,也是卡普的二十一个NP-完全问题之一。
    例如01矩阵问题,需要求解在给定一个由0和1组成的矩阵中,是否能找到一个行的集合,使得集合中每一列都恰好包含一个1?

  • 重复覆盖问题
    在上述精确覆盖问题的基础上,取消对于每一个元素仅出现一次的限制。

  • 数独问题
    Sudoku!
    数独问题满足如下约束条件:

    1. 每一个数(1到9)在每一行出现且仅出现一次。
    2. 每一个数(1到9)在每一列出现且仅出现一次。
    3. 每一个数(1到9)在每一个九宫格出现且仅出现一次。
    4. 每一个格子出现且仅出现一个数。 可转化为01矩阵问题求解。

算法X(Algorithm X)

递归求解精确覆盖问题,每次选择一个没被覆盖的元素,然后选一个包含它的集合进行覆盖。对应到矩阵中,每次选择一个没有被删除的列,然后枚举该列为1的所有行,尝试删除该行,递归搜索后恢复该行。删除行时,除标记“此行已删除”外还要把该行中值为1的列删除,恢复时同样。

舞蹈链(Dancing Links)

双向(循环)十字链表。

支持元素的高速删除与恢复的数据结构。可用于优化算法X。使用了Dancing Links的算法X通常称为DLX算法。

用DLX算法求解数独问题

如下套用DLX算法框架。

  • 行代表着决策。
    每个决策可用一个三元组(r,c,v)表示,意思是将(r,c)这个格子填上数字v。
    共有9*9*9=729行。

  • 列代表着任务。
    共有如下四种需要达成的任务:

    1. Slot(a,b)表示第a行和第b列的格子需要有数字b。
    2. Row(a,b)表示第a行需要有数字b。
    3. Col(a,b)表示第a列需要有数字b。
    4. Sub(a,b)表示第a个九宫格要有数字b。 共有9*9*4=324列。
  • “1”代表着一个决策达成了一个任务。
    决策三元组(i,j,k)达成了Slot(i,j)、Row(i,k)、Col(j,k)、Sub(P_ij,k)。共有729*4=2916个节点。

同理,16*16的数独中,共有4096行,1024列,16384个节点。

至此,数独问题已被成功转化成01矩阵问题。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define N 400
#define M 800
#define P 4000
const int coln=324;

char sudoku[10][10];

inline int encode(int x,int y,int z)
{
    return x*81+y*9+z+1;
}

inline void decode(int x,int &a,int &b,int &c)
{
    x--; c=x%9; x/=9; b=x%9; x/=9; a=x;
}

struct dlx
{
    int tot;
    int ansd,ans[N];
    int S[M],row[P],col[P];
    int L[P],R[P],U[P],D[P];

    void build()
    {
        for(int i=0;i<=coln;i++)
            U[i]=D[i]=i, L[i]=i-1, R[i]=i+1;
        R[coln]=0; L[0]=coln; tot=coln+1;
        memset(S,0,sizeof S);
    }

    void addrow(int now,int r,int c,int v)
    {
        int temp=tot;
        addpoint(now,encode(0,r,c));
        addpoint(now,encode(1,r,v));
        addpoint(now,encode(2,c,v));
        addpoint(now,encode(3,r/3*3+c/3,v));
        R[tot-1]=temp; L[temp]=tot-1;
    }

    void addpoint(int r,int c)
    {
        L[tot]=tot-1; R[tot]=tot+1;
        D[tot]=c; U[tot]=U[c]; D[U[c]]=tot; U[c]=tot;
        row[tot]=r; col[tot]=c;
        S[c]++; tot++;
    }

    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)
    {
        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]]++;
        L[R[c]]=c;
        R[L[c]]=c;
    }

    bool dfs(int deep)
    {
        if(R[0]==0){
            ansd=deep;
            return true;
        }
        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[deep]=row[i];
            for(int j=R[i];j!=i;j=R[j])
                remove(col[j]);
            if(dfs(deep+1)) return true;
            for(int j=L[i];j!=i;j=L[j])
                resume(col[j]);
        }
        resume(c);
        return false;
    }
}dlx;

int main()
{
    for(int i=0;i<9;i++)
        scanf("%s",sudoku[i]);
    dlx.build();
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            for(int k=0;k<9;k++)
                if(sudoku[i][j]=='0'||sudoku[i][j]-'1'==k)
                    dlx.addrow(encode(i,j,k),i,j,k);
    dlx.dfs(0);
    for(int i=0;i<dlx.ansd;i++)
    {
        int r,c,v;
        decode(dlx.ans[i],r,c,v);
        sudoku[r][c]=v+'1';
    }
    for(int i=0;i<9;i++)
        puts(sudoku[i]);
    return 0;
}