[探究] 用舞蹈链(DLX)解决一类数独问题

考虑精准覆盖问题的本质——我们把行看做决策，把列看做任务，那么其实质就是通过决策来完成任务。

那么我们来考虑数独问题的本质，对于一个\(n^2\cdot n^2\)的数独而言，他的目标函数有四个：

• 1、\(r(i,j):\)对于第\(i\)行，必须要有数字\(j\)

• 2、\(c(i,j):\)对于第\(i\)列，必须要有数字\(j\)

• 3、\(p(i,j):\)对于第\(i\)个宫，必须要有数字\(j\)

• 4、\(e(i,j):\)对于第\((i,j)\)个格子，必须要有数字

由此可知，我们有\(4\times (n^2\cdot n^2)\)的任务量。

同时我们可以用\(n^6\)的状态表示我们的决策，即\((i,j,k)\)表示第\(i\)行\(j\)列填了数字\(k\)。

结合两者考虑，我们可以建出一个新的网格图，有\(n^6\)行、\(4n^4\)列。考虑向网格中填“\(1\)”表示一个决策完成了一个任务，那么对于每一个决策\((i,j,k)\)，它理应可以完成\(4\)个任务，所以一共有\(16n^4\)个1.

至此建模完毕，一个\(n^2\cdot n^2\)的数独问题可以转化成一个\(n^6\)行、\(4n^4\)列，有\(16n^4\)个\(1\)的精准覆盖问题。

下面是代码实现部分，以SPOJ1110-SUDOKU为例：

• 首先是对状态进行编号

il int encode(int a, int b, int c){ 
    return (a << 8) + (b << 4) + c + 1 ; 
}
il void decode(int x, int &a, int &b, int &c){ 
    x --, c = x % 16, x /= 16, b = x % 16, x /= 16, a = x ; 
}

原理其实也很简单，就是i的后续状态(j,k)有\(n^4=256\)种组合，同理j的后续状态有\(n^2=16\)种组合。

然后就是连边，对于每个点判断一下，如果当前枚举到的数字是这个点的数字那么就需要insert，同理如果没有数字的话那就都insert一遍，毕竟比起有数字的点，可行的决策数要更多。至此我们就保证了原图中存在数字的方格被insert了，不存在数字的方格的所有可能情况也被insert了，之后直接dance就可以啦。

int t[O][O], op ;
const int POS = 0, Row = 1, Col = 2, Sub = 3 ; 
int main(){
    cin >> T ;
    while (T --){
        read(), Init() ;
        for (int i = 0 ; i < 16 ; ++ i)
            for (int j = 0 ; j < 16 ; ++ j){
                t[i][j] = base[i][j] == '-' ? 0 : base[i][j] - 64 ;
                for (int k = 0 ; k < 16 ; ++ k){
                    if (t[i][j] && t[i][j] != k + 1) continue ;
                    op = encode(i, j, k) ; 
          Insert(op, encode(POS, i, j)),
                    Insert(op, encode(Row, i, k)), 
          Insert(op, encode(Col, j, k)), 
          Insert(op, encode(Sub, (i / 4) * 4 + j / 4, k)) ;
                }
            }       
        dance(0) ;
        for (int i = 0 ; i < 16 ; ++ i, puts(""))
            for (int j = 0 ; j < 16 ; ++ j) printf("%c", (char)(res[i][j] + 65)) ;
        puts("") ;
    }
}

然后是一道要求出所有解的题：NOIP2009D 靶形数独

此处需要我们求出所有可能的精准覆盖方案然后取最大值，于是小小改动一下dance就好。

il int gs(const int &x, const int &y){
    if (x == 1 || y == 1 || x == 9 || y == 9 )   return 6 ;
    if (x == 2 || y == 2 || x == 8 || y == 8 )   return 7 ;
    if (x == 3 || y == 3 || x == 7 || y == 7 )   return 8 ;
    if (x == 4 || y == 4 || x == 6 || y == 6 )   return 9 ; return 10 ; 
}
void dance(const int &step){
    int now_c = B[0].r ; 
    if (!now_c){
        int x, y, z, ret = 0 ;
        for (rr int i = 0 ; i < step ; ++ i)
            decode(ans[i], x, y, z), g[x][y] = z + 1 ; 
        for (rr int i = 0 ; i < 9 ; ++ i)
            for (rr int j = 0 ; j < 9 ; ++ j)
                ret += g[i][j] * gs(i + 1, j + 1) ;
        res = max(res, ret) ; return ;
    }
    for (rr int i = now_c ; i ; i = B[i].r) 
    now_c = Cs[i] < Cs[now_c] ? i : now_c ; Del(now_c) ;  
    for (rr int i = B[now_c].d ; i != now_c ; i = B[i].d){
        ans[step] = B[i].ro ; 
    for (rr int j = B[i].r ; j != i ; j = B[j].r) Del(B[j].co) ;
        dance(step + 1) ; 
    for (rr int j = B[i].l ; j != i ; j = B[j].l) Back(B[j].co) ;
    }
    Back(now_c) ; return  ; 
}

撒花~ （撒自己XD

[探究] 用舞蹈链(DLX)解决一类数独问题

原文：https://www.cnblogs.com/pks-t/p/11753819.html