用舞蹈链(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为例:

  • 首先是对状态进行编号
1
2
3
4
5
6
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就可以啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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