《靶形數(shù)獨(dú)》解題報(bào)告

《靶形數(shù)獨(dú)》解題報(bào)告靶形數(shù)獨(dú)的方格同普通數(shù)獨(dú)一樣，在9格寬×9格高的大九宮格中有9個(gè)3格寬×3格高的小九宮格〔用粗黑色線隔開(kāi)的〕。在這個(gè)大九宮格中，有一些數(shù)字是的，根據(jù)這些數(shù)字，利用邏輯推理，在其他的空格上填入1到9的數(shù)字。每個(gè)數(shù)字在每個(gè)小九宮格內(nèi)不能重復(fù)出現(xiàn)，每個(gè)數(shù)字在每行、每列也不能重復(fù)出現(xiàn)。但靶形數(shù)獨(dú)有一點(diǎn)和普通數(shù)獨(dú)不同，即每一個(gè)方格都有一個(gè)分值，而且如同一個(gè)靶子一樣，離中心越近那么分值越高題目大意右圖具體的分值分布是：最里面一格〔黃色區(qū)域〕為10分，黃色區(qū)域外面的一圈〔紅色區(qū)域〕每個(gè)格子為9分，再外面一圈〔藍(lán)色區(qū)域〕每個(gè)格子為8分，藍(lán)色區(qū)域外面一圈〔棕色區(qū)域〕每個(gè)格子為7分，最外面一圈〔白色區(qū)域〕每個(gè)格子為6分，如上圖所示。比賽的要求是：每個(gè)人必須完成一個(gè)給定的數(shù)獨(dú)〔每個(gè)給定數(shù)獨(dú)可能有不同的填法〕，而且要爭(zhēng)取更高的總分?jǐn)?shù)。而這個(gè)總分?jǐn)?shù)即每個(gè)方格上的分值和完成這個(gè)數(shù)獨(dú)時(shí)填在相應(yīng)格上的數(shù)字的乘積的總和。如圖，在以下的這個(gè)已經(jīng)填完數(shù)字的靶形數(shù)獨(dú)游戲中，總分?jǐn)?shù)為2829。游戲規(guī)定，將以總分?jǐn)?shù)的上下決出勝負(fù)。題目大意樣例輸入700900001100005900000200080005020003000000648413000000007002090201060804080504012樣例輸出2829方案如右圖樣例數(shù)獨(dú)問(wèn)題是個(gè)非常經(jīng)典的NP完全問(wèn)題，沒(méi)有多項(xiàng)式的算法，只能搜索。首先可以想到枚舉，但數(shù)據(jù)給出的數(shù)獨(dú)空格非常多，最多可能有9^57種狀態(tài)，是效率極低的算法，對(duì)于此題的數(shù)據(jù)是無(wú)法得分的。題目分析進(jìn)一步分析可以想到遞歸回溯，遇到每個(gè)空格，枚舉該空格所在的行、列、小九宮已填了哪些數(shù)，得出空格可填的數(shù)，分別填上這些數(shù)并進(jìn)行下一層的搜索。這樣的方法已經(jīng)遠(yuǎn)優(yōu)于枚舉，但對(duì)于此題大局部數(shù)據(jù)還是無(wú)法出解〔實(shí)際測(cè)試可以得到40%的分?jǐn)?shù)〕。題目分析優(yōu)化1：為了加快計(jì)算一個(gè)格子可填的數(shù)的速度，我們可以把每行、每列、每個(gè)九宮格可填的數(shù)用二進(jìn)制集合表示，每個(gè)格子(x,y)當(dāng)前可填的數(shù)的集合就是第x行、第y列以及(x,y)所在小九宮的可填的數(shù)集求交。這個(gè)操作可以用位運(yùn)算實(shí)現(xiàn)。這樣，找可填的數(shù)的時(shí)間就大大縮短了。實(shí)際測(cè)試中可以得到75%的分?jǐn)?shù)。題目分析上面的方法所得的分?jǐn)?shù)在考場(chǎng)上已經(jīng)是相當(dāng)可觀，但此題還有進(jìn)一步的優(yōu)化余地。有時(shí)在數(shù)獨(dú)下方會(huì)有一些格子只有一兩個(gè)可填的數(shù)字，而在數(shù)獨(dú)上方的一些格子可能會(huì)有很多可填的數(shù)字。這時(shí)如果按照從上往下搜索的順序搜索，將會(huì)擴(kuò)展出很多無(wú)用的狀態(tài)。如果是用人腦來(lái)做數(shù)獨(dú)的話，必定會(huì)先填可行方案少的格子，來(lái)給其它格子更多的限制，這樣可以剪去很多不可行的分支。優(yōu)化2：我們可以預(yù)處理求出每個(gè)空格可填的方案數(shù)，并對(duì)它們進(jìn)行排序。按照這個(gè)順序搜索，將可以得到85%的分?jǐn)?shù)。題目分析優(yōu)化3：注意到前面填的數(shù)會(huì)對(duì)后面與它同行、同列、同小九宮的格子造成影響，后面的可填數(shù)大小順序可能有改變?？梢钥紤]在填了一個(gè)格子之后，找出后面待填的格子中可填數(shù)最少的格子，進(jìn)行進(jìn)一步的搜索。這個(gè)方法的表現(xiàn)非常優(yōu)秀，在實(shí)際測(cè)試中得到了總分值。題目分析盡管我們已經(jīng)得到了通過(guò)全部數(shù)據(jù)的正確算法，但是優(yōu)化是無(wú)止境的；解決數(shù)獨(dú)這類搜索問(wèn)題還可以轉(zhuǎn)換為“精確覆蓋”模型，使用一種叫做DLX〔DancingLinks〕的數(shù)據(jù)結(jié)構(gòu)優(yōu)化，優(yōu)化效果非常明顯，但實(shí)現(xiàn)起來(lái)過(guò)于復(fù)雜，本文暫不做討論，有興趣的同學(xué)可以自行查閱資料。拓展優(yōu)化下面分別是樸素的搜索，分別加了優(yōu)化1、1和2、全部的程序通過(guò)官方全部數(shù)據(jù)的運(yùn)行速度：實(shí)際效果樸素搜索優(yōu)化1優(yōu)化1、2優(yōu)化1、2、3DLX535S（40%得分）149S（75%得分）