前面的文字介紹了舞蹈鏈，這里就不詳細(xì)描述什么是舞蹈鏈了，舞蹈鏈（Dancing links）是一種數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)實(shí)現(xiàn)X算法，以解決精確覆蓋問(wèn)題。本篇的內(nèi)容主要把舞蹈鏈Dancing links應(yīng)用于實(shí)際問(wèn)題，通過(guò)實(shí)踐才能幫助大家更好的理解，片面的了解理論知識(shí)，最終不能落到實(shí)處，也就沒(méi)有意義了。
當(dāng)然，把Dancing links應(yīng)用于實(shí)際問(wèn)題時(shí)，只有一個(gè)難點(diǎn)，就是如何把具體的問(wèn)題轉(zhuǎn)換為可以精確覆蓋的01矩陣模型，一旦完成了這個(gè)步后，直接套用模板就可以解決問(wèn)題了。
應(yīng)用之一：傷腦筋十二塊
傷腦筋十二塊是Dancing links精確覆蓋的典型應(yīng)用，理解起來(lái)最容易
圖1：12片5格骨牌的拼圖
題目描述：
給你12個(gè)如上圖的5格骨牌，如何讓程序拼出如上的“口”字圖形。
上圖是題目的一個(gè)答案，你知道程序如何得到這個(gè)答案的嗎？沒(méi)錯(cuò)，就是用Dancing links的精確覆蓋。
我們想象一個(gè)有72列的矩陣，其中12列是12個(gè)骨牌，剩下60列是60個(gè)非中心部分的格子。
所有可能的行來(lái)代表在一塊骨牌在棋盤(pán)上得放置方案；每行有一些“1”，用來(lái)標(biāo)識(shí)被覆蓋的格子，5個(gè)1標(biāo)識(shí)一個(gè)骨牌放置的位置（恰有1568個(gè)這樣的行）
我們將最前面的12列命名為F,I,L,P,N,T,U,V,W,X,Y,Z,并且我們可以用兩個(gè)數(shù)字i,j給矩陣中對(duì)應(yīng)棋盤(pán)上的第i行第j列格子的那一列命名。通過(guò)給出那些出現(xiàn)了“1”的列的名字，可以很方便地表示每一行。
例如，圖2就是與下面12行的對(duì)應(yīng)的精確覆蓋。
1568個(gè)行指的是12個(gè)骨牌可放置方案的總和，比如長(zhǎng)條骨牌I共有64種放置方案，1568中就包含了這64種 這1568行中，每行都有6個(gè)1，分布在72個(gè)列中
這個(gè)矩陣的構(gòu)造思路是：
首先找約束關(guān)系，這里只有兩個(gè)約束關(guān)系，
（1）12個(gè)骨牌，每種只有1個(gè)；
（2）60個(gè)空格中，一個(gè)位置只能放一種骨牌（否則就要重疊著放了）；
因?yàn)榈谝粋€(gè)約束關(guān)系，有了12個(gè)列來(lái)區(qū)分骨牌種類(lèi)，因?yàn)榈诙€(gè)約束關(guān)系，有了60個(gè)選5個(gè)來(lái)表示骨牌放置 。
應(yīng)用之二：數(shù)獨(dú)問(wèn)題 sudoku
解數(shù)獨(dú)，生成數(shù)獨(dú)，都可以使用精確覆蓋，要把數(shù)獨(dú)問(wèn)題構(gòu)造成01矩陣還是有一定的難度。
首先找約束關(guān)系，這里只有四個(gè)約束關(guān)系，
(1)81個(gè)格子中每個(gè)格子只能放一個(gè)數(shù)字
(2)每一行的數(shù)字不能重復(fù)
(3)每一列的數(shù)字不能重復(fù)
(4)每一九宮內(nèi)的數(shù)字不能重復(fù)
四個(gè)約束關(guān)系中，每個(gè)約束對(duì)應(yīng)一個(gè)列域，對(duì)于第二個(gè)約束關(guān)系，數(shù)獨(dú)中共有9行，每行可以填9個(gè)不同的數(shù)字；
因此第二個(gè)列域，共有9* 9，81個(gè)列，依此類(lèi)推，數(shù)獨(dú)問(wèn)題共有列324個(gè)；
由于81個(gè)格子，每個(gè)格子都最多有9種選擇，所以行最多有81*9=729行；
這樣01矩陣的每行都有4個(gè)1，第一個(gè)1分布在1到81列，第二個(gè)1分布在82到162列，第三個(gè)1分布在163到243列；
最后一個(gè)1分布在其余列區(qū)域。
思考：為什么不能這樣構(gòu)造01矩陣，用5個(gè)1，第一個(gè)1表示格子序號(hào)，有81個(gè)列，第二個(gè)1表示數(shù)字，從1到9有9個(gè)列，第三個(gè)1表示行號(hào)，有9行，第四個(gè)1表示列號(hào)也有9個(gè)，第五個(gè)1表示九宮格序號(hào)，也有9個(gè)，這樣共有117列。
為了便于理解，舉個(gè)例子
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
如上數(shù)獨(dú)有空格40個(gè)，已知格子41個(gè)，把這個(gè)數(shù)獨(dú)構(gòu)造成01矩陣，矩陣的行有40*9+41共401行。
對(duì)于第一個(gè)數(shù)字9，在1到81列的第一列，在82到162列的第9個(gè)，即90列，在163列到243列的第9個(gè)，在244到324列的第9個(gè)各占一個(gè)1 ；
對(duì)于第三個(gè)數(shù)字0，由于有9個(gè)選擇，所以在構(gòu)造01矩陣時(shí)，要向矩陣插入9個(gè)行，來(lái)表示各種可能；
對(duì)于第四個(gè)數(shù)字8，它在二行四列，把這個(gè)數(shù)字寫(xiě)入dancing link的網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)時(shí)，需要新增四個(gè)節(jié)點(diǎn)，這四個(gè)節(jié)點(diǎn)都在同一行，它們的列序號(hào)分別為13， 81 + 9 + 8 - 1，81 + 81 + 3 * 9 + 8 - 1，81 + 81 + 81 + 9 + 8 - 1， 序號(hào)是從0開(kāi)始的，所有要減去一。
現(xiàn)在假設(shè)，2行6列的空格是數(shù)字8，那么這個(gè)數(shù)字也會(huì)對(duì)應(yīng)四個(gè)節(jié)點(diǎn)，列序號(hào)分別為15，81 + 9 + 8 - 1， 81 + 81 + 5 * 9 + 8 - 1， 81 + 81 + 81 + 9 + 8 - 1，
可以看到， 這兩個(gè)8的行域，九宮格域都是相同的，表示這兩個(gè)數(shù)字的行和九宮格都相沖了，四個(gè)列域，只要有一個(gè)相沖，兩條記錄就不能共存。這兩個(gè)8顯然不能共存。
數(shù)獨(dú)還有一個(gè)變種，對(duì)角線數(shù)獨(dú)，兩條對(duì)角線的數(shù)字也不能重復(fù)，這時(shí)構(gòu)造01矩陣模型時(shí)，就需要額外增加兩個(gè)列域，左對(duì)角線域，右對(duì)角線域。增加的兩個(gè)列域都只有9列，
對(duì)于1行1列的數(shù)字，會(huì)在01矩陣模型中對(duì)應(yīng)5個(gè)節(jié)點(diǎn)，
對(duì)于2行3列的數(shù)字，由于不位于兩條對(duì)角線上，會(huì)在01矩陣模型中只對(duì)應(yīng)4個(gè)節(jié)點(diǎn)，
對(duì)于5行5列的數(shù)字，恰好在兩條對(duì)角線的交匯處，會(huì)在01矩陣模型中對(duì)應(yīng)6個(gè)節(jié)點(diǎn)
對(duì)于數(shù)獨(dú)的生成
總體思路是一行一行的生成，第一行可以用一個(gè)隨機(jī)的1到9的排列，接下來(lái)的8行，每行都要用dancinglink求解可行的排序
（1）先對(duì)1到9這9個(gè)數(shù)進(jìn)行隨機(jī)排列，把這個(gè)排列作為數(shù)獨(dú)終盤(pán)布局的第一行
（2）自己寫(xiě)函數(shù)篩選出下一行，每個(gè)格子可以填寫(xiě)的數(shù)字集合，篩選時(shí)不用考慮行沖突
比如對(duì)于排列5,9,7,4,2,6,8,3,1
篩選結(jié)果如下：123468,123468,123468,135789,135789,135789,245679,245679,245679
表示對(duì)于下一行的1,2,3列，可以選擇的數(shù)字集合有1,2,3,4,6,8.
下一行的4,5,6列，可以選擇的數(shù)字集合有1,3,5,7,8,9
下一行的7,8,9列，可以選擇的數(shù)字集合有2,4,5,6,7,9
這時(shí)，構(gòu)造01矩陣，就只有2個(gè)約束關(guān)系
（1）對(duì)于下一行的9個(gè)格子，每個(gè)格子只能放一個(gè)數(shù)字
（2）對(duì)于下一行的9個(gè)格子中的數(shù)字，每個(gè)數(shù)字都不能重復(fù)
因?yàn)榈?個(gè)和4個(gè)約束，已經(jīng)在篩選時(shí)考慮進(jìn)去，這里不需再多此一舉
這時(shí)的01矩陣，列有9+ 9=18個(gè)，行有6* 9 = 54行（6+6+6+6+6+6+6+6+6）。
應(yīng)用之三：N皇后
N皇后問(wèn)題也可以轉(zhuǎn)換為Dancing links的精確覆蓋問(wèn)題，這里只講如何把n皇后問(wèn)題轉(zhuǎn)換為01矩陣，首先有四個(gè)約束關(guān)系
（1）所有皇后不能在同一行
（2）所有皇后不能在同一列
（3）所有皇后不能在同一左斜線
（4）所有皇后不能在同一右斜線
為了便于理解，舉個(gè)例子：n=8時(shí)，有8行,8列，15個(gè)左斜線，15個(gè)右斜線（2*n-1），這樣構(gòu)造的矩陣有46個(gè)列，8*8=64個(gè)行，矩陣的每行都有4個(gè)1，分別分布在行域，列域，左斜線域，右斜線域，在編程求解這個(gè)問(wèn)題時(shí)，需要做一點(diǎn)變通，因?yàn)樽笮本€域，右斜線域的列不可能被全部覆蓋，因此只需行域和列域被完全覆蓋就算找到問(wèn)題的一個(gè)解了。
附：
dancing LInks 求解數(shù)獨(dú)的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; //此列節(jié)點(diǎn)總數(shù)
};
#define R 729
#define C 324
class Dlx
{
public:
Node *nodes,*row,*col,*head;//可用節(jié)點(diǎn)，行首，列首，總頭節(jié)點(diǎn)
int rowNum,colNum,nodeCount;//行數(shù)，列數(shù),總節(jié)點(diǎn)數(shù)
int *result,resultCount;//結(jié)果,結(jié)果行數(shù)
Dlx()
{
nodes=new Node[R*C];//直接用數(shù)組竟然運(yùn)行不起，棧溢出了，還得放在堆里
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);//搜索出結(jié)果
void addNode(int r,int c);//添加一個(gè)節(jié)點(diǎn)
};
void Dlx::init(int r,int c)
{
int i;
rowNum=r;
colNum=c;
//將各列連起來(lái),col[colNum]為總頭節(jié)點(diǎn)
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;
//將各行節(jié)點(diǎn)數(shù)清零
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;//總節(jié)點(diǎn)數(shù)清零
}
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)
{
//記錄完成覆蓋所用行數(shù)
resultCount=k;
return true;
}
Node *pMin,*p,*q;
//找到節(jié)點(diǎn)數(shù)最少的一列,并覆蓋
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;
//選定此列上的一個(gè)節(jié)點(diǎn)，將此節(jié)點(diǎn)所在行上所有節(jié)點(diǎn)的對(duì)應(yīng)列進(jìn)行覆蓋
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())
{
//結(jié)果存到字符串中
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;
}
C語(yǔ)言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程，并配有習(xí)題和答疑，點(diǎn)擊了解：
一點(diǎn)編程也不會(huì)寫(xiě)的：零基礎(chǔ)C語(yǔ)言學(xué)練課程
解決困擾你多年的C語(yǔ)言疑難雜癥特性的C語(yǔ)言進(jìn)階課程
從零到寫(xiě)出一個(gè)爬蟲(chóng)的Python編程課程
只會(huì)語(yǔ)法寫(xiě)不出代碼？手把手帶你寫(xiě)100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程：算法競(jìng)賽課入門(mén)課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程