dancing links

现在的位置: 首页 > 综合 > 正文

2017年04月25日 ⁄ 综合 ⁄ 共 20538字 ⁄ 字号小中大 ⁄ 评论关闭

最早接触Dancing Links的时候，是在csdn论坛上逛的时候，发现有人在研究数独程序，由于本人开发过数独游戏，就进去看了看，发现有人说用Dancing Links来求解数独最快了，于是我就决定去了解一下Dancing Links。

1. Dancing Links是什么？

Dancing Links是一类搜索问题的通用优化,对精确覆盖问题有奇效，也可解决重复覆盖问题，DancingLinks的发明者是DonKnuth(《计算机程序设计艺术》的作者)

2. 用途

解决精确覆盖问题。对于接下来的非确定性算法，由于我们没有想到更好的名字，我们将称之为X算法，它能够找到由特定的01矩阵A定义的精确覆盖问题的所有解。X算法是实现试验——错误这一显而易见的方法的一段简单的语句（确实，一般来说，我想不到别的合理的方法来完成这个工作）。

如果A是空的，问题解决；成功终止。

否则，选择一个列c（确定的是选含1最少的列）。

选择一个行r，满足 A[r,c]=1 （不确定的是哪一行）。

把r包含进部分解。

对于所有满足 A[r,j]=1 的j，

　　从矩阵A中删除第j列；

　　对于所有满足 A[i,j]=1 的，

　　　　从矩阵A中删除第i行。

在不断减少的矩阵A上递归地重复上述算法。

3. 舞蹈步骤

一个实现X算法的好方法就是将矩阵A中的每个1用一个有5个域L[x]、R[x]、U[x]、D[x]、C[x]的数据对象（dataobject）x来表示。矩阵的每行都是一个经由域L和R(左和右)双向连接的环状链表；矩阵的每列是一个经由域U和D(上和下)双向连接的环状链表。每个列链表还包含一个特殊的数据对象，称作它的表头（list header）。

这些表头是一个称作列对象（columnobject）的大型对象的一部分。每个列对象y包含一个普通数据对象的5个域L[y]、R[y]、U[y]、D[y]和C[y]，外加两个域S[y]（大小）和N[y]（名字）；这里大小是一个列中1的个数，而名字则是用来标识输出答案的符号。每个数据对象的C域指向相应列头的列对象。

表头的L和R连接着所有需要被覆盖的列。这个环状链表也包含一个特殊的列对象称作根，h，它相当于所有活动表头的主人。而且它不需要U[h]、D[h]、C[h]、S[h]和N[h]这几个域。

我们寻找所有精确覆盖的不确定性算法现在可以定型为下面这个明析、确定的形式，即一个递归过程search(k)，它一开始被调用时k=0：

如果 R[h]=h ，打印当前的解（见下）并且返回

否则选择一个列对象c（见下）。

覆盖列c（见下）。

对于每个r←D[c]，D[D[c]]，……，当 r!=c，

　　设置 Ok<-r；

　　对于每个j←R[r]，R[R[r]]，……，当 j!=r，

　　　　覆盖列j（见下）；

　　search(k+1)；

　设置 r←Ok 且 c←C[r]；

　　对于每个j←L[r]，L[L[r]]，……，当 j!=r，

　　　　取消列j的覆盖（见下）。

取消列c的覆盖（见下）并且返回。

为了选择一个列对象c,我们可以简单地设置c<-R[h]；这是最左边没有覆盖的列。或者如果我们希望使分支因数达到最小，我们可以设置s<-无穷大，那么接下来：

对于每个j←R[h]，R[R[h]]，……，当 j!=h，

　　如果 S[j]<s 设置 c←j 且 s←S[h]。

那么c就是包含1的序数最小的列(如果不用这种方法减少分支的话，S域就没什么用了)。

覆盖列c的操作则更加有趣：把c从表头删除并且从其他列链表中去除c链表的所有行。

设置 L[R[c]]←L[c] 且 R[L[c]]←R[c]。

对于每个i←D[c]，D[D[c]]，……，当 i!=c，

　　对于每个j←R[i]，R[R{i]]，……，当 j!=i，

　　　　设置 U[D[j]]←U[j]，D[U[j]]←D[j]，

　　　　并且设置 S[C[j]]←S[C[j]]-1。

操作（1），就是我在本文一开始提到的，在这里他被用来除去水平、竖直方向上的数据对象。

最后，我们到达了整个算法的尖端，即还原给定的列c的操作。这里就是链表舞蹈的过程：

对于每个i←U[c]，U[U[c]]，……，当 j!=i，

　　对于每个j←L[i]，L[L[i]]，……，当 j!=i，

　　　　设置 S[C[j]]←S[C[j]]+1，

　　　　并且设置 U[D[j]]←j，D[U[j]]←j。

设置 L[R[c]]←c 且 R[L[c]]←c。

注意到还原操作正好与覆盖操作执行的顺序相反，我们利用操作（2）来取消操作（1）。（其实没必要严格限制“后执行的先取消”，由于j可以以任何顺序穿过第i行；但是从下往上取消对行的移除操作是非常重要的，因为我们是从上往下把这些行移除的。相似的，对于第r行从右往左取消列的移除操作也是十分重要的，因为我们是从左往右覆盖的。）

以上部分，可能太过专业，太抽象，你可能也看不明白，反正我就是一直没弄明白过上面的描述,但是后面会有我自己通过分析程序代码给出的示意图，详细描述了舞蹈的过程，非常直观易懂，所以不懂上面的可直接跳过，不必纠结。

4. Dancing Links的具体实现方法

Dancing Links这种数据结构的实现方法有两种，一个是用双向十字链表来实现，这种方法比较容易理解,另一个是用几个数组来实现，这种方法较另类，较难理解

双向十字链表实现

L[x]和R[x]分别表示x的前驱节点和后继节点。每个程序员都知道如下操作：

L[R[x]] ← L[x],R[L[x]] ← R[x] （1）

是将x从链表删除的操作；但是只有少数程序员意识到如下操作

L[R[x]] ← x,R[L[x]] ← x （2）

dancingLinks的精髓就体现在第二个公式，因为它很方便很高效的实现了链表的恢复

图1：dancingLinks的链表结构示意图

dancing links的数组实现

其实是用数组来模拟双向十字链表结构，为方便理解，直接举个例子。

对于如下的01矩阵：

1 1 00

0 0 01

0 1 11

1 0 10

我们把它的dancinglinks结构描述到如下4个数组中：（Up,Down,Left,Right）

如下：

为什么这4个数组的长度都是13呢？

因为上面的01矩阵有4个列，8个1，我们把头节点head编号为0。列分别编号为1,2,3,4。第一行的两个1编号为5,6，第二行的一个1编号为7，第三行三个1编号为8,9,10。第四行两个1，编号为11,12。编号的顺序都是从左到右。

这样一来，1列的下一个节点就是编号为5的1，编号为5的1的下面又是编号11的1，编号为5的1的左边和右边都是编号为6的1

为便于理解，可以结合图1来看

Remove(5) L[R[1]]=L[1]; R[L[1]]=R[1]; L[R[11]]=L[11]; R[L[11]]=R[11];

Remove(6) L[R[8]]=L[8]; R[L[8]]=R[8]; L[R[2]]=L[2]; R[L[2]]=R[2];

Resume(5) L[R[1]]=R[L[1]]=1 L[R[11]]=R[L[11]]=11

Resume(6) L[R[2]]=R[L[2]]=2 L[R[8]]=R[L[8]]=8

可见数组是可以用来表示双向十字链表结构的

Dancing Links一般都用来解决精确覆盖问题，什么是精确覆盖问题呢？就是下面这种：

DancingLinks精确覆盖

题目描述

对于如下01矩阵，选择若干行，使得矩阵的每一列都有且仅有一个1

1,4,5行，是精确覆盖的一个解，如何用Dancing Link得到这个解的，可以参考代码

http://blog.csdn.net/acmer1183/article/details/6320437

接下来重点讲解，对于这个题目，dance links的具体的舞蹈步骤和过程，也就是对如上参考程序的详解

首先，选择2行1列后（即绿框所在的行）,带来效应是：1,4,7列都被删除了，2,4,5,6行也被删除了

x			x			x
0	0	1	0	1	1	0
1	0	0	1	0	0	1	x
0	1	1	0	0	1	0
1	0	0	1	0	0	0	x
0	1	0	0	0	0	1	x
0	0	0	1	1	0	1	x

图中被染色的行列，表示这些行列已经被删除了，绿框所在的行表示，当前选择的是第几行

尚有2,3,5,6列有待删除，dancinglink还需继续dancing

我们选择包含1最少的列来删除,现在包含1最少的列是第2列

x	x	x	x		x	x
0	0	1	0	1	1	0	x
1	0	0	1	0	0	1	x
0	1	1	0	0	1	0	x
1	0	0	1	0	0	0	x
0	1	0	0	0	0	1	x
0	0	0	1	1	0	1	x

此时，只有第5列还没有删除，由于第5列没有1，(本来第5列有两个1，但分别在第一步和第二步被删掉了，分别被染成蓝色和绿色)所以要进行回溯

在进行回溯时，由于第3行2列的单元格没有兄弟节点；也就是说这个单元格所在的列，当时有且仅有一个1

这里着重解释一下“当时”：本来，3行2列的单元格（绿色单元格）是有一个兄弟节点(5行2列的单元格)的，

但这个兄弟节点在dancing的前一步就已经被剔除掉了并且被染成蓝色，是因为我们之前选择了1列2行的元素

兄弟关系：在同一列不同行的值为1的单元格，并且这些单元格的颜色相同，这样这些单元格才有兄弟关系

发现选择2,3行无解，开始回溯，直接回溯成下图这样：

继续dancing，选择含1最少的列

现在，所有的列都被删除了，所以选择1,4,5行，是精确覆盖的一个解

Dancing Links除了能解决精确覆盖问题，还能解决重复覆盖问题，这里重点讲重复覆盖

题目：高手做题

描述

SubRaY被布置了n道作业题,可是他一道也不会..但他知道有w位高手,并知道每位高手

会做哪些题,请问SubRaY至少请多少位高手,才能把所有的题都做出来?

输入

第一行两个整数n,w表示有n道作业题和w位高手,作业题以1..n编号.接下来w行,第i+1

行第一个数li表示第i位高手会做的题目的数量,接下来li个数表示第i位高手会做哪

些题目.

3<=n,w<=60,1<=li<=6

输出

一个数,SubRaY至少要请多少位高手.

样例输入

4 4

2 1 2

1 4

3 2 3 4

2 1 3

样例输出

代码参考：http://blog.sina.com.cn/s/blog_51cea4040100gwpv.html

为了详细讲解Dancing links 重复覆盖的过程，我们先把样例输入转换为如下01矩阵

和精确覆盖一样，先选择含1最少的列，这里选择的1行1列的，选择后，

第1和2列被删除了，第一步，效果如下：

选择3行3列后，第3,4列也被删除了，至此重复覆盖的一个解已经被找到了，即1,3行，

但还不能确定这个解是最优的（可能只需一行就可以把所有列都覆盖）,还需要继续搜索，

第二步

第三步，开始回溯，选择3行3列的兄弟节点4行3列后的效果如下

上图那样不能得到解，继续回溯到如下效果，第四步

第五步

第六步

至此重复覆盖的另一个解已经被找到了，即3行和4行，

现在，所有的节点都被遍历过了，这个重复覆盖总共有两个解；1行和3行，3行和4行，每个解都是最优的，都需要两个高手

可供参考的剪枝函数：

[cpp]view

 plaincopy

int Hash()        

{         

    int ans=0;        

    bool hash[maxn]={0};          

    for (int c=R[0];c!=0;c=R[c])          

 {        

        if (!hash[c])         

        {         

            hash[c]=1;        

            ans++;        

            for (int i=D[c];i!=c;i=D[i])          

                for (int j=R[i];j!=i;j=R[j])          

                    hash[nCol[j]]=1;          

        }         

 }        

    cout << "Hash =>" << ans << endl;        

    return ans;       

}

这个函数实际上是在对当前状态进行重复覆盖，只是覆盖列时，不是删除列，而是把相应列的标志位置1 ，这个函数的目的是，预先估计当前这样选择后，还需要多少行才能覆盖所有列。

函数返回值越大，越可能被剪枝

Dancing links 精确覆盖和重复覆盖的区别

1.精确覆盖更能体现dancing links 的威力，因为在剪枝的时候，精确覆盖不仅对列剪枝，对行也进行了剪枝，

而重复覆盖只对列进行剪枝，要想提高重复覆盖的效率还需要自己写剪枝函数

2.重复覆盖问题一般是求解最优解的，不像精确覆盖找到一个解就算完事，因此重复覆盖需要遍历和考察所有的分支，来找到最优的

全部代码：

#include<iostream>
using namespace std;
const int maxn=20;
int L[maxn],R[maxn],U[maxn],D[maxn];
int S[maxn]={0};
int nCol[maxn];
int nRow[maxn];
bool answer[4]={0};
int n,w;
int best=INT_MAX;

int sample[4][4] = { 
                 {1,1,0,0},
                 {0,0,0,1}, 
                 {0,1,1,1},
                 {1,0,1,0}
                };

void init()
{
    n=4;
	w=4;
    for (int i=0;i<=n;i++)
    {
        L[i]=i-1; R[i]=i+1;
        U[i]=D[i]=i;
	}
    L[0]=n; 
	R[n]=0;
    int cnt=n+1;
    for (int i=0;i<w;i++)
    {
        int head=cnt,tail=cnt;
        for (int j=0;j<n;j++)
        {
            int c = j+1;
			if(sample[i][j]==1)
			{
				S[c]++;
				nCol[cnt]=c;
				nRow[cnt]=i;
				U[D[c]]=cnt;
				D[cnt]=D[c];
				U[cnt]=c;
				D[c]=cnt;
				L[cnt]=tail; R[tail]=cnt;
				R[cnt]=head; L[head]=cnt;
				tail=cnt;
				cnt++;
			}
        }
    }
}
void Remove(int x)
{
	cout << "remove=>" << x << endl;
    for (int i=D[x];i!=x;i=D[i])
    {
        L[R[i]]=L[i];
        R[L[i]]=R[i];
        S[nCol[i]]--;
    }
}
void Resume(int x)
{
	cout << "Resume=>" << x << endl;
    for (int i=U[x];i!=x;i=U[i])
    {
        L[R[i]]=R[L[i]]=i;
        S[nCol[i]]++;
    }
}
int Hash()
{
    int ans=0;
    bool hash[maxn]={0};
    for (int c=R[0];c!=0;c=R[c])
	{
        if (!hash[c])
        {
            hash[c]=1;
            ans++;
            for (int i=D[c];i!=c;i=D[i])
                for (int j=R[i];j!=i;j=R[j])
                    hash[nCol[j]]=1;
        }
	}
	cout << "Hash =>" << ans << endl;
    return ans;
}
void dfs(int ans)
{
	int best2 = ans + Hash();
    if (best2>=best) 
		return;
    if (R[0]==0)
    {
        best=ans;
		for (int i = 0; i < 4; i++) 
		{
			if ( answer[ i ] ) 
			{
			   for (int j = 0; j < 4; j++) cout << sample[ i ][ j ] << " ";
			   cout << endl;
			}
		}
        return;
    }
    int c,minnum=INT_MAX;
    for (int i=R[0];i!=0;i=R[i])
    {
        if (S[i]==0) return;
        if (S[i]<minnum)
        {
            minnum=S[i];
            c=i;
        }
    }
    for (int i=U[c];i!=c;i=U[i])
    {
		answer[nRow[i]]=true;
        Remove(i);
        for (int j=R[i];j!=i;j=R[j])
            Remove(j);
        dfs(ans+1);
        for (int j=L[i];j!=i;j=L[j])
            Resume(j);
        Resume(i);
		answer[nRow[i]]=false;
    }
}
int main()
{
   // freopen("data.in","r",stdin);
   // freopen("data.out","w",stdout);
    init();
    dfs(0);
	   printf("%d\n",best);
   // fclose(stdin);
   // fclose(stdout);
	getchar();
    return 0;
}

DancingLinks的应用

把dancingLink应用于实际问题时，只有一个难点，就是如何把具体的问题转换为可以精确覆盖的01矩阵模型，一旦完成了这个步后，直接套用模板就可以解决问题了。

应用之一：伤脑筋十二块

伤脑筋十二块是dancing links精确覆盖的典型应用，理解起来最容易

图2,12片5格骨牌的拼图

题目描述：

给你12个如上图的5格骨牌，如何让程序拼出如上的“口”字图形。

上图是题目的一个答案，你知道程序如何得到这个答案的吗？没错，就是用dancinglink的精确覆盖

我们想象一个有72列的矩阵，其中12列是12个骨牌，剩下60列是60个非中心部分的格子，构造出

所有可能的行来代表在一块骨牌在棋盘上得放置方案；每行有一些‘’1“，用来标识被覆盖的格子，5个1标识一个骨牌放置的位置（恰有1568个这样的行）

我们将最前面的12列命名为F,I,L,P,N,T,U,V,W,X,Y,Z,并且我们可以用两个数字i,j给矩阵中对应棋盘上的第i行第j列格子的那一列命名。通过给出那些出现了‘’1"的列的名字，可以很方便地表示每一行。

例如，图2就是与下面12行的对应的精确覆盖。

1568个行指的是12个骨牌可放置方案的总和，比如长条骨牌I共有64种放置方案，1568中就包含了这64种

这1568行中，每行都有6个1，分布在72个列中

这个矩阵的构造思路是：

首先找约束关系，这里只有两个约束关系，

（1）12个骨牌，每种只有1个，

（2）60个空格中，一个位置只能放一种骨牌（否则就要重叠着放了）

因为第一个约束关系，有了12个列来区分骨牌种类，因为第二个约束关系，有了60个选5个来表示骨牌放置

应用之二：数独问题 sudoku

解数独，生成数独，都可以使用精确覆盖，要把数独问题构造成01矩阵还是有一定的难度

首先找约束关系，这里只有四个约束关系，

(1)81个格子中每个格子只能放一个数字

(2)每一行的数字不能重复

(3)每一列的数字不能重复

(4)每一九宫内的数字不能重复

四个约束关系中，每个约束对应一个列域，对于第二个约束关系，数独中共有9行，每行可以填9个不同的数字

因此第二个列域，共有9* 9，81个列，依此类推，数独问题共有列324个。

由于81个格子，每个格子都最多有9种选择，所以行最多有81*9=729行

这样01矩阵的每行都有4个1，第一个1分布在1到81列，第二个1分布在82到162列，第三个1分布在163到243列，

最后一个1分布在其余列区域。

思考：为什么不能这样构造01矩阵，用5个1，第一个1表示格子序号，有81个列，第二个1表示数字，从1到9有9个列，第三个1表示行号，有9行，第四个1表示列号也有9个，第五个1表示九宫格序号，也有9个，这样共有117列。

为了便于理解，举个例子

9,2,0,0,0,0,0,0,0,

5,0,0,8,7,0,0,0,0,

0,3,8,0,9,1,0,0,0,

0,5,2,9,3,0,1,6,0,

0,9,0,0,0,0,0,3,0,

0,7,3,0,6,4,9,8,0,

0,0,0,4,1,0,2,5,0,

0,0,0,0,5,3,0,0,1,

0,0,0,0,0,0,0,7,3

如上数独有空格40个，已知格子41个，把这个数独构造成01矩阵，矩阵的行有

40*9+41 共401行

对于第一个数字9，在1到81列的第一列，在82到162列的第9个，即90列，在163列到243列的第9个，在244到324列的第9个各占一个1

对于第三个数字0，由于有9个选择，所以在构造01矩阵时，要向矩阵插入9个行，来表示各种可能

对于数独的生成

总体思路是一行一行的生成，第一行可以用一个随机的1到9的排列，接下来的8行，每行都要用dancinglink求解可行的排序

（1）先对1到9这9个数进行随机排列，把这个排列作为数独终盘布局的第一行

（2）自己写函数筛选出下一行，每个格子可以填写的数字集合，筛选时不用考虑行冲突

比如对于排列5,9,7,4,2,6,8,3,1

筛选结果如下： 123468,123468,123468,135789,135789,135789,245679,245679,245679

表示对于下一行的1,2,3列，可以选择的数字集合有1,2,3,4,6,8.

下一行的4,5,6列，可以选择的数字集合有1,3,5,7,8,9

下一行的7,8,9列，可以选择的数字集合有2,4,5,6,7,9

这时，构造01矩阵，就只有2个约束关系

1 对于下一行的9个格子，每个格子只能放一个数字

2 对于下一行的9个格子中的数字，每个数字都不能重复

因为第3个和4个约束，已经在筛选时考虑进去，这里不需再多此一举

这时的01矩阵，列有9+ 9=18个，行有6* 9 = 54行（6+6+6+6+6+6+6+6+6）。

应用之三：N皇后

N皇后问题也可以转换为dancinglinks的精确覆盖问题

这里只讲如何把n皇后问题转换为01矩阵，首先有四个约束关系

（1）所有皇后不能在同一行

（2）所有皇后不能在同一列

（3）所有皇后不能在同一左斜线

（4）所有皇后不能在同一右斜线

为了便于理解，举个例子

n=8时，有8行,8列，15个左斜线，15个右斜线（2*n-1）

这样构造的矩阵有46个列，8*8=64个行

矩阵的每行都有4个1，分别分布在行域，列域，左斜线域，右斜线域

在编程求解这个问题时，需要做一点变通，因为左斜线域，右斜线域的列不可能被全部覆盖

因此只需行域和列域被完全覆盖就算找到问题的一个解了。

附：

dancing LInks 求解数独的C++代码

#include<iostream>
#include<string.h>

using namespace std;


struct Node 
{
	Node *up;
	Node *down;
	Node *left;
	Node *right;
	Node *colRoot; //列首
	int row; //所在行
	int sum; //此列节点总数
};

#define R 729
#define C 324


class Dlx
{
public:
	Node *nodes,*row,*col,*head;//可用节点，行首，列首，总头节点
	int rowNum,colNum,nodeCount;//行数，列数,总节点数
	int *result,resultCount;//结果,结果行数

	Dlx()
	{
		nodes=new Node[R*C];//直接用数组竟然运行不起，栈溢出了，还得放在堆里
		row=new Node[R];
		col=new Node[C+1];
		result=new int[R];
	}
	~Dlx()
	{
		delete []nodes;
		delete []row;
		delete []col;
		delete []result;

	}
	void init(int r,int c);//初始化
	void cover(Node *t);//覆盖一列
	void uncover(Node *t);//取消覆盖
	bool solove(int k=0);//搜索出结果
	void addNode(int r,int c);//添加一个节点
};


void Dlx::init(int r,int c)
{
	int i;
	
	rowNum=r;
	colNum=c;
	//将各列连起来,col[colNum]为总头节点
	for(i=0;i<=colNum;i++)
	{
		col[i].up=col[i].down=col+i;
		col[i].left=col + (i+colNum)%(1+colNum);
		col[i].right=col + (i+1)%(1+colNum);
		col[i].sum=0;
	}
	head=col+colNum;

	//将各行节点数清零
	for(i=0;i<rowNum;i++)
	{
		row[i].up=row[i].down=row[i].left=row[i].right=row[i].colRoot=row+i;
	}
	
	nodeCount=0;//总节点数清零
}

void Dlx::addNode(int r,int c)
{
	nodes[nodeCount].up=col[c].up;
	nodes[nodeCount].down=col+c;
	nodes[nodeCount].left=row[r].left;
	nodes[nodeCount].right=row+r;
	nodes[nodeCount].row=r;
	nodes[nodeCount].colRoot=col+c;
	col[c].up=col[c].up->down=row[r].left=row[r].left->right=nodes+nodeCount++;	
	col[c].sum++;
}


void Dlx::cover(Node *t)
{
	Node *p,*q;
	t->left->right=t->right;
	t->right->left=t->left;
	for(p=t->down;p!=t;p=p->down)
	{
		for(q=p->right;q!=p;q=q->right)
		{
			q->up->down=q->down;
			q->down->up=q->up;
			q->colRoot->sum--;
		}
	}	
}

void Dlx::uncover(Node *t)
{
	Node *p,*q;
	for(p=t->up;p!=t;p=p->up)
	{
		for(q=p->left;q!=p;q=q->left)
		{
			q->up->down=q->down->up=q;
			q->colRoot->sum++;
		}
	}
	t->left->right=t->right->left=t;
}

bool Dlx::solove(int k)
{
	//是否还有未覆盖的列
	if(head->right==head)
	{
		//记录完成覆盖所用行数
		resultCount=k;
		return true;
	}
	
	Node *pMin,*p,*q;
	//找到节点数最少的一列,并覆盖
	for(pMin=head->right,p=pMin->right;p!=head;p=p->right)
	{
		if(pMin->sum>p->sum)
			pMin=p;
	}
	cover(pMin);
	

	for(p=pMin->down;p!=pMin;p=p->down)
	{
		result[k]=p->row;
		//选定此列上的一个节点，将此节点所在行上所有节点的对应列进行覆盖
		for(q=p->right;q!=p;q=q->right)
			cover(q->colRoot);
		if(solove(k+1))
			return true;
		//如果不能成功，则取消覆盖
		for(q=p->left;q!=p;q=q->left)
			uncover(q->colRoot);
	}

	uncover(pMin);
	return false;
}
int getRowIndex(int rowNum)
{
	int num = rowNum%9;
	int rowIndex = rowNum / 81;
	return 81 + rowIndex*9 + num;
}
int getColIndex(int rowNum)
{
	int num = rowNum%9;
	int index = rowNum/9;	//位置
	int colIndex = index%9;
	return 162 + colIndex*9+num;
}
int getSquareIndex(int rowNum)
{
	int num = rowNum%9;
	int index = rowNum/9;	//位置
	int rowIndex = index / 9;
	int colIndex = index%9;
	int squareIndex = int(rowIndex/3)*3 + colIndex/3;
	return 243 + squareIndex*9+num;
}
int main3()
{
	int i,j;
	int node4=0;
	char str[82];
	Dlx dlx;
	
	//cin>>n;
	dlx.init(729,324);
	//for(i=0;i<9;i++)
	//{
	//	cin>> (str+i*9);
	//}
	//......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
	const char *input = ".2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.";
	strcpy(str,input);
	for(i=0;i<729;i++)
	{
		//cout << "row=>" << i << "\tcol=> 位置" << i/9 <<"\t行"<<81+i/9/9*9+i%9<<"\t列"<<162+i/9%9*9+i%9<<"\t块"<< 243+(i/9/9/3*3+i/9%9/3)*9+i%9;
		//cout << "row=>" << i << "\tcol=> 位置" << i/9 <<"\t行"<<getRowIndex(i)<<"\t列"<<getColIndex(i)<<"\t块"<<getSquareIndex(i);
		if(str[i/9]=='.' || str[i/9]-'1'==i%9)
		{
			node4++;
			int rowIndex = i;
			int colIndex = i/9;
			dlx.addNode(rowIndex,colIndex);//位置冲突

			dlx.addNode(rowIndex,getRowIndex(i));//行冲突

			dlx.addNode(rowIndex,getColIndex(i));//列冲突

			dlx.addNode(rowIndex,getSquareIndex(i));//块冲突
		//	cout << "\t<=";
		}
		//cout << endl;
	}
	if(dlx.solove())
	{
		//结果存到字符串中
		for(i=0;i<81;i++)
		{
			j=dlx.result[i];
			str[j/9]='1'+j%9;
		}
		//输出字符串
		for(i=0;i<9;i++)
		{
			for(j=0;j<9;j++)
				cout<<str[i*9+j];
			cout<<endl;
		}
	}
	
	return 0;
}

附，生成数独终盘布局的Flex代码

<?xml version="1.0" encoding="utf-8"?>
<s:WindowedApplication xmlns:fx="http://ns.adobe.com/mxml/2009" 
					   xmlns:s="library://ns.adobe.com/flex/spark" 
					   xmlns:mx="library://ns.adobe.com/flex/mx">
	<fx:Declarations>
		<!-- Place non-visual elements (e.g., services, value objects) here -->
	</fx:Declarations>
	<fx:Script>
		<![CDATA[
			import model.DancingNode;
			
			private var sample:String="1279,2367,1369,24789,4578,259,13458,1368,456";
			
			private var rowArr:Array=[];
			private var colArr:Array=[];
			private var head:DancingNode;
			private var nodes:Array=[];
			private var cnt:Array=[];
			private var answer:Array=[];
			private var answerArr:Array=[];
			
			private function _init(restrict:String):void
			{
				answerArr=[];
				answer=[];
				cnt=[];
				nodes=[];
				rowArr=[];
				colArr=[];
				var i:int;
				var colLen:int=18;
				var rowLen:int=restrict.split(',').join('').length;
				for(i=0;i<rowLen;i++)
				{
					var row:DancingNode = new DancingNode(i);
					rowArr.push(row);
				}
				for(i=0;i<=colLen;i++)
				{
					var col:DancingNode = new DancingNode(-1,i);
					colArr.push(col);
					cnt.push(0);
				}
				var colArrLen:int = colArr.length;
				for(i=0;i<colArr.length;i++)
				{
					var left:int = (i+colArrLen-1)%colArrLen;
					var right:int = (i+1)%colArrLen;
					DancingNode(colArr[i]).left=colArr[left];
					DancingNode(colArr[i]).right=colArr[right];
				}
				head = colArr[0];
				
				//create links
				var rowIndex:int=0;
				var arr1:Array = restrict.split(',');
				for(i=0;i<arr1.length;i++)
				{
					var arr2:Array = String(arr1[i]).split('');
					for(var j:int=0;j<arr2.length;j++)
					{
						var colIndex1:int=i+1;
						var colIndex2:int=9+int(arr2[j]);
						addNode(rowIndex,colIndex1,i,int(arr2[j]));
						addNode(rowIndex,colIndex2,i,int(arr2[j]));
						rowIndex++;
					}
				}
				for(i=0;i<rowLen;i++)
				{
					DancingNode(rowArr[i]).left.right=DancingNode(rowArr[i]).right;
					DancingNode(rowArr[i]).right.left=DancingNode(rowArr[i]).left;
				}
			}
			
			private function addNode(r:int,c:int,r1:int,c1:int):void
			{
				var node:DancingNode = new DancingNode(r,c);
				node.rowValue=r1;
				node.colValue=c1;
				node.up = colArr[c].up;
				node.down = colArr[c];
				node.left = rowArr[r].left;
				node.right = rowArr[r];
				cnt[c]++;
				
				colArr[c].up=colArr[c].up.down=rowArr[r].left=rowArr[r].left.right=node;
				nodes.push(node);
			}
			
			private function remove(node:DancingNode):void
			{
				//trace("remove=>",node.col);
				node.left.right = node.right;
				node.right.left = node.left;
				for(var p:DancingNode=node.down;p!=node;p=p.down)
				{
					for(var q:DancingNode=p.right;q!=p;q=q.right)
					{
						q.up.down=q.down;
						q.down.up=q.up;
						cnt[q.col]--;
					}
				}
			}
			
			private function resume(node:DancingNode):void
			{
				//trace("resume=>",node.col);
				for(var p:DancingNode=node.down;p!=node;p=p.down)
				{
					for(var q:DancingNode=p.right;q!=p;q=q.right)
					{
						q.up.down=q;
						q.down.up=q;
						cnt[q.col]++;
					}
				}
				node.left.right = node;
				node.right.left = node;
			}
			
			private function dancing(depth:int):Boolean
			{
				//是否还有未覆盖的列
				if(head.right==head)
				{
					var arr:Array=[];
					for(var i:int=0;i<answer.length;i++)
					{
						var node:DancingNode=answer[i];
						arr[node.rowValue]=node.colValue;
					}
					answerArr.push(arr);
					return true;
				}
				var pMin:DancingNode;
				var p:DancingNode;
				//找到节点数最少的一列,并覆盖
				for(pMin=head.right,p=pMin.right;p!=head;p=p.right)
				{
					if(cnt[pMin.col] > cnt[p.col])
					{
						pMin = p;
					}
				}
				remove(pMin);
				var q:DancingNode;
				for(p=pMin.down;p!=pMin;p=p.down)
				{
					//选定此列上的一个节点，将此节点所在行上所有节点的对应列进行覆盖
					answer[depth]=p;
					for(q=p.right;q!=p;q=q.right)
					{
						remove(colArr[q.col]);
					}
					if(dancing(depth+1))
					{
						if(answerArr.length > 10)
						{
							return true;
						}
					}
					for(q=p.left;q!=p;q=q.left)
					{
						resume(colArr[q.col]);
					}
				}
				resume(pMin);
				if(answerArr.length > 0)
				{
					return true;
				}
				return false;
			}
			
			private function getSudokuLine(restricts:Array):Array
			{
				var arr:Array=[];
				for(var i:int=0;i<restricts.length;i++)
				{
					arr.push((restricts[i] as Array).join(''));
				}
				_init(arr.join(','));
				if(dancing(0))
				{
					var line:Array = answerArr[int(answerArr.length*Math.random())];
					trace('getSudokuLine,answer length=>',answerArr.length);
					return line;
				}
				return [];
			}
			//得到随机的1到9的排列
			private function getRandomArr(value:int):Array
			{
				var bak:Array = [];
				for(var i:int=1;i<=value;i++)
				{
					bak.push(i);
				}
				var randLine:Array=[];
				while(bak.length>0)
				{
					var index:int = bak.length*Math.random();
					randLine.push(bak[index]);
					bak.splice(index,1);
				}
				return randLine;
			}
			
			public function createFullSudoku():Array
			{
				var sudokuArr:Array=[];
				while(sudokuArr.length < 9)
				{
					sudokuArr=[];
					sudokuArr.push(getRandomArr(9));
					for(var i:int=0;i<8;i++)
					{
						var restricts:Array = getRestricts(sudokuArr);
						if(restricts.length==0)
						{
							break;
						}
						var line:Array = getSudokuLine(restricts);
						if(line.length==0)
						{
							break;
						}
						sudokuArr.push(line);
					}
				}
				return sudokuArr;
			}
			
			private function getRestricts(curLayout:Array):Array
			{
				var i:int;
				var ret:Array=[];
				for(i=0;i<9;i++)
				{
					var arr:Array=getCandidateNums(curLayout,i);
					if(arr.length==0)
					{
						return [];
					}
					ret.push(arr);
				}
				return ret;
			}
			//根据当前布局curLayout,得到index列的候选数集合
			private function getCandidateNums(curLayout:Array,index:int):Array
			{
				var i:int;
				var line:Array = [0,1,2,3,4,5,6,7,8,9];
				if(curLayout.length==0)
				{
					return [1,2,3,4,5,6,7,8,9];
				}
				//列排除
				for(i=0;i<curLayout.length;i++)
				{
					line[curLayout[i][index]]=0;
				}
				//九宫格排除
				var col3_3:int = index/3;
				var row3_3:int = curLayout.length/3;
				var inRow3_3:int = curLayout.length%3;
				for(i=row3_3*3;i<row3_3*3+inRow3_3;i++)
				{
					line[curLayout[i][col3_3*3] ]=0;
					line[curLayout[i][col3_3*3+1] ]=0;
					line[curLayout[i][col3_3*3+2] ]=0;
				}
				var ret:Array=[];
				for(i=0;i<line.length;i++)
				{
					if(line[i]!=0)
					{
						ret.push(i);
					}
				}
				return ret;
			}
			
			private function createSudoku():void
			{
				var arr:Array=createFullSudoku();
				var arr2:Array=[];
				for(var i:int=0;i<arr.length;i++)
				{
					arr2.push((arr[i] as Array).join(','));
				}
				area.text = arr2.join('\n');
			}
		]]>
	</fx:Script>
	<s:VGroup horizontalCenter="0" verticalCenter="0">
		<s:TextArea width="300" height="300" id="area"/>
		<s:Button label="get full sudoku" click="createSudoku()"/>
	</s:VGroup>
</s:WindowedApplication>

package model
{
	public class DancingNode
	{
		public var row:int;
		public var col:int;
		public var rowValue:int;
		public var colValue:int;
		public var up:DancingNode;
		public var down:DancingNode;
		public var left:DancingNode;
		public var right:DancingNode;
		
		public function DancingNode(r:int=-1,c:int=-1)
		{
			row = r;
			col = c;
			up = this;
			down = this;
			left = this;
			right = this;
		}
	}
}

【上篇】【容斥原理】【bzoj 1853】: [Scoi2010]幸运数字
【下篇】POJ1426-Find The Multiple

作者: EddyChandler

该日志由 EddyChandler 于7年前发表在综合分类下，最后更新于 2017年04月25日.
转载请注明: dancing links | 学步园 +复制链接

抱歉!评论已关闭.

学步园

dancing links

DancingLinks精确覆盖

DancingLinks的应用

作者: EddyChandler

书签

最新文章New

本站推荐

返回首页