关键词:  精确覆盖   数独   舞蹈链(DLX)   数据结构-交叉十字循环双向链 相关题目: 靶形数独  数独大赛

问题简述: 给定一些条件(常为矩阵),求满足所有条件的精确覆盖问题。 思想方法: 舞蹈链 (Dancing links)算法

靶形数独 (NOIp 2009 提高组 T4)

题目描述

    小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独游戏,好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了,于是他们向 Z 博士请教,Z 博士拿出了他最近发明的“靶形数独”,作为这两个孩子比试的题目。靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫格中有9个3格宽×3格高的小九宫格(用粗黑色线隔开的)。在这个大九宫格中,有一些数字是已知的,根据这些数字,利用逻辑推理在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现,每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同,即每一个方格都有一个分值,而且如同一个靶子一样,离中心越近则分值越高。(如图) 28     上图具体的分值分布是:最里面一格(黄色区域)为 10 分,黄色区域外面的一圈(红色区域)每个格子为 9 分,再外面一圈(蓝色区域)每个格子为 8 分,蓝色区域外面一圈(棕色区域)每个格子为 7 分,最外面一圈(白色区域)每个格子为 6 分,如上图所示。比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有不同的填法),而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图,在以下的这个已经填完数字的靶形数独游戏中,总分数为 2829 。游戏规定,将以总分数的高低决出胜负。 29

输入输出格式

输入格式:     一共 9 行。每行 9 个整数(每个数都在 0―9 的范围内),表示一个尚未填满的数独方格,未填的空格用“0”表示。每两个数字之间用一个空格隔开。 输出格式:     输出共 1 行。     输出可以得到的靶形数独的最高分数。如果这个数独无解,则输出整数-1。

数据规模

    对于100%的数据,数独中非 0 数的个数不少于 24。


解决方案

    这里推荐一篇不错的文章:舞蹈链(Dancing Links)算法——求解精确覆盖问题     文章内容引用:使用dancing links算法求解数独     第一想法:采用记忆化搜索(因为这是一道加强的数独题)。但是必须回溯好,剪枝优化。在这里就不作赘述。    评测详情     但是在求解过程中缓存矩阵和回溯矩阵的过程不断调用函数,时间浪费较为大,并且代码有一定的复杂度。为此本文重点介绍的是一种新的数据结构 Dancing links X ,与传统相比,有很多意想不到的优化。

介绍:

    Dancing Links适用于精确覆盖问题。     精确覆盖问题的定义:给定一个由 0-1 组成的矩阵,是否能找到一个行的集合,使得集合中每一列都恰好包含一个 1     右图就属于经典的该类问题。dlx     Dancing Links的核心是基于双向链的方便操作(移除、恢复加入),这样可以避免大量的内存占用和回溯空间。下面是一个例子:

假设双向链的三个连续的元素,A1、A2、A3,每个元素有两个分量Left和Right,分别指向左边和右边的元素。由定义可知:     A1.Right=A2,A2.Right=A3     A2.Left=A1 , A3.Left=A2 移除:执行下面的操作就即可     A1.Right=A3,A3.Left=A1 恢复:可以注意到,移除A2的时候。我们并没有改变A2的值。所以我们只需执行如下操作即可     A1.Right=A2,A3.Left=A2 优点:不用缓存数据,赋值即可。不管是在时间,内存还是代码复杂度上都有明显优化

构建

    Dancing Links用的数据结构是交叉十字循环双向链,每个元素都有6个分量:Left指向左边的元素、Right指向右边的元素、Up指向上边的元素、Down指向下边的元素、Col指向列标元素、Row指示当前元素所在的行。

辅助元素:

  1. Ans[]:Ans数组,在求解的过程中保留当前的答案,以供最后输出答案用。
  2. Head元素:判断是否求解是否还能进行。当判断出Head.Right=Head(也可以是Head.Left=Head)时,元素全部移除,求解结束,输出答案。
  3. C元素:辅助元素,称列标元素,每列有一个列标元素,并且这些元素互相连接。列标元素的分量Row=0,表示是处在第0行。 pic 解释一下:     每个绿色方块是一个元素,其中Head和 Ci 是辅助元素。橙色框中的元素是原矩阵中1的元素,给他们标上号(从1到16)     左侧的红色,标示的是行号,辅助元素所在的行是0行,其余元素所在的行从1到6 每两个元素之间有一个双向箭头连线,表示双向链中相邻两个元素的关系(水平的是左右关系、垂直的是上下关系)。     单向的箭头并不是表示单向关系,而因为是循环双向链,左侧的单向箭头和右侧的单向箭头(上边的和下边的)组成了一个双向箭头,例如元素14左侧的单向箭头和元素16右侧的单项箭头组成一个双向箭头,表示14.Left=16、16.Right=14;同理,元素14下边的单项箭头和元素C4上边的单向箭头组成一个双向箭头,表示14.Down=C4 、C4.Up=14

至此,交叉十字循环双向链结构构建完成。

————————————分割线———————————— 那么问题来了 (回看一下题目,怎样将Dancing links算法应用到数独 (Sudoku) 上呢 ??) emm......这里我们需要将问题进行等价转换。

先来看一下数独规则:

  1. 每个格子只能填一个数字;
  2. 每行每个数字只能填一遍;
  3. 每列每个数字只能填一遍;
  4. 每宫每个数字只能填一遍。

我们进行一下转换:

  1. 每行1-9的这9个数字都得填一遍(也就意味着每个数字只能填一遍);
  2. 每列1-9的这9个数字都得填一遍;
  3. 每宫1-9的这9个数字都得填一遍。
  4. 每个格子只能填一个数字;

例:(约束条件②) 我们可以将第     第82列定义成:在第1列填了数字1     第83列定义成:在第1列填了数字2     ...     第90列定义成:在第1列填了数字9     第91列定义成:在第2列填了数字1     ...     第99列定义成:在第2列填了数字9     ...     第162在第9列填了数字9 于是,我们用i表示行,j表示列 (0<=i, j<9),s表示填入的数字。 那么满足上述条件的列所对应的序号为:9*9+j*9+s

这不就成了精确覆盖问题了吗(#qwq

Tips: 我们先对于每一个条件创建矩阵列(此矩阵列非此矩阵列),很显然每个条件的列的个数为9*9。每次填入合法的数字,一定会产生满足不同条件的列。那么由数独的定义,这些列已经不能够被后面填入的数再次满足。进而只需对这些列进行精确覆盖,也便转换为Dancing Links的模型。

求解过程

  1. 首先判断Head.Right==Head,若是,求解结束,输出解;若不是,求解还没结束,执行②(也可以判断Head.Left==Head)
  2. 选定要填入的一个行。(这里有个小小的优化:用数组S[]储存列标元素,每次选取剩余元素最少的一行填)
  3. 每次先从列标元素删除,后牵动最近行删除。并约定:从下向右删除,从上向右恢复。

AC代码

改写自Vijos用户:lyyyzx

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio>
#include <cstring>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define maxn 666
#define nmax maxn*maxn
int W[9][12]={
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};
bool flag;

struct DLX{
int n,m,index,head,ansk;
int S[maxn],ans[nmax];//不难看出 S[] 是为了优化时间
int row[nmax],col[nmax];
int L[nmax],R[nmax],U[nmax],D[nmax],H[nmax];
inline void link(int r,int c){//r为行,c为列 插入循序从左到右 从上到下
S[c]++;//该列元素个数
row[index]=r; col[index]=c;
U[index]=U[c]; D[U[c]]=index; D[index]=c; U[c]=index;
if(H[r]==-1)
H[r]=L[index]=R[index]=index;
else {
L[index]=L[H[r]];
R[index]=H[r];
R[L[H[r]]]=index;
L[H[r]]=index;
}//添加双向链
index++;
}
inline void init(){
int i; head=0;
rep(i,0,m){
R[i]=(i+1)%(m+1);
L[i]=(i-1+m+1)%(m+1);
U[i]=D[i]=i;
}
memset(H,-1,sizeof(H)); memset(S,0,sizeof(S));
index=m+1;
}//初始化

#define FOR(i,A,k) for(int i=A[k];i!=k;i=A[i])//
inline void remove(int c){
L[R[c]]=L[c]; R[L[c]]=R[c];//删除该元素
FOR(i,D,c)FOR(j,R,i){//(链)牵动删除该元素的连接元素 向下
U[D[j]]=U[j];
D[U[j]]=D[j];
S[col[j]]--;
}
}//元素移除

inline void restore(int c){
FOR(i,U,c)FOR(j,L,i){
++S[col[j]];
U[D[j]]=j;
D[U[j]]=j;
}//(链)牵动恢复该元素的连接元素 向上
L[R[c]]=c; R[L[c]]=c;//恢复该元素
}//元素恢复

//---------------------Dancing links 模板---------------------
inline void dfs(int k){
if(R[head]==head){
flag=true;
int cnt=0;
rep(j,0,k-1){
int i=ans[j];
cnt+=W[chess[i].x][chess[i].y]*chess[i].w;
}
if(cnt>ansk) ansk=cnt;
return ;
}
int c=R[head];
FOR(i,R,head) if(S[i]<S[c]) c=i;//选定需排除项最少的行的列标元素

remove(c);//牵动删除
FOR(i,D,c){//向下搜索行
ans[k]=row[i];//储存填入数对应的行号
FOR(j,R,i) remove(col[j]);//移除该行牵动的向右元素
dfs(k+1);
FOR(j,L,i) restore(col[j]);//恢复该行牵动的向左元素
}
restore(c);//牵动恢复

return ;
}
struct Piece{
int x,y,w;
//坐标位置,数字
};
Piece chess[maxn];

inline void slove(){
int i,j,tmp,s,t;
m=4*9*9;//矩阵大小
n=0;//计数
ansk=0;
init();
rep(i,0,8)rep(j,0,8){
scanf("%d",&tmp);
if(tmp) s=tmp,t=tmp;
else s=1,t=9;
while(s<=t){
n++;
chess[n].x=i; chess[n].y=j; chess[n].w=s;
link(n,i*9+s);//行
link(n,9*9+j*9+s);//列
link(n,2*9*9+((i/3)*3+j/3)*9+s);//宫
link(n,3*9*9+i*9+j+1);//每次格子只能放一个
//构建图
s++;
}
}
dfs(0);
if(flag)
printf("%d\n",ansk);
else
puts("-1");
}
};
DLX T;

int main(){
T.slove();
return 0;
}

2018.02.18 0:27 正式完工