Dancing Link在數(shù)獨(dú)求解中的應(yīng)用

柯建平 陳昱宇

泉州市兒童醫(yī)院

“數(shù)獨(dú)”（sudoku）一詞來自日語(yǔ)，意思是“單獨(dú)的數(shù)字”或“只出現(xiàn)一次的數(shù)字。”概括來說，它就是一種填數(shù)字游戲。數(shù)獨(dú)作為人類的一種經(jīng)典的益智游戲，它的計(jì)算機(jī)解決對(duì)于人們對(duì)計(jì)算機(jī)能做什么，可以做到怎樣有很大的啟發(fā)意義，本文從搜索的角度，也是最基本的一種方法，但是對(duì)其程序?qū)崿F(xiàn)的一個(gè)較大的優(yōu)化，使用Dancing Link 技術(shù)，十字鏈表的使用和啟發(fā)式的搜索方法，大大提高了程序的運(yùn)行效率。

雙向鏈表又叫雙鏈表，是鏈表的一種。雙向鏈表的存儲(chǔ)結(jié)構(gòu)往往是有一個(gè)空的結(jié)點(diǎn)來表示頭指針。然后每一個(gè)結(jié)點(diǎn)有一個(gè)直接前驅(qū)值域和一個(gè)直接后驅(qū)值域。

如果是十字鏈表的話，結(jié)點(diǎn)中指針的值域會(huì)變成四個(gè)。在單向鏈表中刪除一個(gè)結(jié)點(diǎn)是非常麻煩，而且低效的。雙向鏈表有著優(yōu)美的結(jié)構(gòu)，可以方便的刪除任意一個(gè)結(jié)點(diǎn)。公式如下：L[R[x]] = L[x]； R[L[x]] = R[x]；其中x指的是編號(hào)，LR來記錄左右方向的雙向鏈表。

這邊用的靜態(tài)數(shù)組的實(shí)現(xiàn)方式，同指針其實(shí)是一樣的，如果你實(shí)現(xiàn)過雙向鏈表的話，那你一定會(huì)覺得很熟悉。雙向鏈表的結(jié)點(diǎn)恢復(fù)，請(qǐng)看公式如下：L[R[x]] = x； R[L[x]]= x； 其中x指的是編號(hào)，LR來記錄左右方向的雙向鏈表[4]。

Dancing Links的核心思想就是對(duì)于稀疏矩陣采用雙向十字鏈表存儲(chǔ)的搜索[5]。對(duì)于雙向鏈表結(jié)點(diǎn)刪除和恢復(fù)操作，大家在平時(shí)只想怎樣刪除，而從沒想過把刪除掉的結(jié)點(diǎn)恢復(fù)。有些人可能覺得這是不好的，如果沒有把分配出去的內(nèi)存刪除掉，很容易造成內(nèi)存泄漏。但這里，我們卻需要這樣做。我們?cè)阪湵碇袆h除結(jié)點(diǎn)，只做標(biāo)記，不做真正的清空內(nèi)存操作。這樣我們后來便可以用(2) 進(jìn)行恢復(fù)操作了。(2)才是Dancing Links的核心.接下來我們來看一個(gè)經(jīng)典的搜索問題，精確覆蓋問題：

給定一個(gè)由0和1組成的矩陣，是否能找到一個(gè)行的集合，使得集合中每一列都恰好包含一個(gè)1？例如，下面這個(gè)矩陣

圖1-1 矩陣

就包含了這樣一個(gè)集合（第1，4，5行）。我們把列想象成全集的一些元素，而行看作全集的一些子集；或者我們可以把行想象成全集的一些元素，而把列看作全集的一些子集；那么這個(gè)問題就是要求尋找一批元素，它們與每個(gè)子集恰好有一個(gè)交點(diǎn)。這是一個(gè)NP問題。自然，作為首選的算法就是回溯了。下面給出算法過程：

上述代碼和普通的搜索本質(zhì)上是相同的，但看上去不太一樣我在下面將會(huì)給出源碼。這段代碼的算法框架已經(jīng)固定了 ，幾乎沒有可優(yōu)化的余地，就算用非遞歸來優(yōu)化也不會(huì)得到多少的效率提升，反而會(huì)使編碼復(fù)雜度和出錯(cuò)率大大增加。如何去實(shí)現(xiàn)代碼行(1) (2) (3) (4) 是優(yōu)化的關(guān)鍵，也是Dancing Links發(fā)揮其作用的地方。我們可以直觀的去想到一個(gè)簡(jiǎn)單的方法：

Step (1)：把矩陣進(jìn)行掃描，選出未做刪除標(biāo)記的列中元素個(gè)數(shù)最少的。

Step (2): 對(duì)當(dāng)前列和行做標(biāo)記，標(biāo)記其已經(jīng)刪除。

Step (3): 同Step (2)

Step (4): 把相應(yīng)的標(biāo)記刪除。

Step (5): 同Step (4)

然而，這個(gè)方法很明顯是非常低效的，做標(biāo)記是快速的。但是相應(yīng)的帶來的問題，是查找的時(shí)候會(huì)變得非常慢。復(fù)雜度始終是O(n)(n為矩陣大小)。在step (1) (2) (3) (4)(5) 中我們都用到了查找操作，所以我們不能忽視查找的復(fù)雜度。在這個(gè)實(shí)現(xiàn)方式中，把查找的效率提升多少，整個(gè)程序便可提升多少。

下面我們來細(xì)細(xì)展開Dancing Links的雙向十字鏈表。

由于經(jīng)常要用到2級(jí)指針，如果用真正的指針實(shí)現(xiàn)的話代碼可讀性很差，代碼也不好看，所以我用靜態(tài)數(shù)組實(shí)現(xiàn)，這樣既可方便的建立矩陣，也可以加快運(yùn)行速度。對(duì)每一個(gè)對(duì)象，記錄如下幾個(gè)信息：

L[x], R[x], U[x], D[x], C[x]；

雙向十字鏈表用LRUD來記錄，LR來記錄左右方向的雙向鏈表，UD來記錄上下方向的雙向鏈表。 head 指向總的頭指針，head通過LR來貫穿的列指針頭。 每一列都有列指針頭。C[x]是指向其列指針頭的地址。行指針頭可有可無(wú)，在我的實(shí)現(xiàn)中沒有顯示的表示出來。在某些題目中，加個(gè)行指針頭還是很有必要的。

另外，開兩個(gè)數(shù)組cnt[x], ans[x]；cnt[x]記錄列鏈表中結(jié)點(diǎn)的總數(shù)。ans[x]用來記錄搜索結(jié)果。

本設(shè)計(jì)主要研究Dancing Links算法與實(shí)現(xiàn)。本文設(shè)計(jì)了精確覆蓋模型的建立模型建立并編程實(shí)現(xiàn)，通過暴力搜索算法的比較，得出Dancing Links搜索時(shí)間上的明顯的優(yōu)勢(shì)。Dancing Links與暴力搜索的搜索時(shí)間相差在100倍以上。