基于策略模式的數(shù)獨(dú)優(yōu)化求解算法研究

1、基于策略模式的數(shù)獨(dú)優(yōu)化求解算法研究 摘 要根據(jù)常規(guī)數(shù)獨(dú)問題的基本規(guī)則，推導(dǎo)了五項(xiàng)數(shù) 獨(dú)求解基礎(chǔ)方法，然后結(jié)合計(jì)算機(jī)程序的實(shí)現(xiàn)，將其設(shè)計(jì)為 可各自獨(dú)立執(zhí)行的算法(策略) 。在此基礎(chǔ)上，以人工求解 數(shù)獨(dú)問題的思維過程為依據(jù)，提出了基于策略模式的數(shù)獨(dú)優(yōu) 化求解算法。該算法實(shí)現(xiàn)了在數(shù)獨(dú)問題的初步推斷和后續(xù)回 溯法求解過程中根據(jù)各單元格出現(xiàn)的不同數(shù)值情況自主判 定并選擇執(zhí)行不同的策略，從而通過較少的運(yùn)算量將未知情 況數(shù)量降至最小，提高了計(jì)算機(jī)求解數(shù)獨(dú)的運(yùn)算效率。 【關(guān)鍵詞】數(shù)獨(dú) 策略模式 回溯法 優(yōu)化算法 1 引言 數(shù)獨(dú)( Sudoku )是一項(xiàng)起源于瑞士，在美國形成雛形， 在日本確立名稱并得以進(jìn)一步發(fā)

2、展的數(shù)學(xué)邏輯游戲。數(shù)獨(dú)以 其千變?nèi)f化的數(shù)字排列和靈活多樣的求解思維方法而迅速 風(fēng)靡全球，被公認(rèn)為一種有效考驗(yàn)和增強(qiáng)大腦邏輯思維能力 的方法。 如圖1 (a)所示，常規(guī)數(shù)獨(dú)是將一個(gè)大正方形平均劃分 為 3 行 3 列共 9 個(gè)九宮格。每個(gè)九宮格中又包含 3 行 3 列共 9個(gè)小單元格。這樣，大正方形就由 9行( R 1 -R9) 、9列( C 1 -C9) 共 81 個(gè)小單元格構(gòu)成。數(shù)獨(dú)的目標(biāo)是根據(jù)有限的提示數(shù)， 在大正方形的每個(gè)單元格內(nèi)填入 1-9 這九個(gè)整數(shù)中的某一個(gè)， 使大正方形中的每一行、每一列及每個(gè)九宮格內(nèi)均包含 1-9 這九個(gè)整數(shù)，不能重復(fù)也不可遺漏。 圖1 （a）為一道常規(guī)數(shù)獨(dú)問題

3、實(shí)例，已給出 17個(gè)數(shù)字 作為提示數(shù)。其中的深色部分代表與單元格R4C6處于同一 行（R4）、同一列（C6）及同一九宮格（R4C4-R6C6的區(qū)域。 在本文中，這 3 個(gè)區(qū)域稱為“相關(guān)限制區(qū)域” 。在這些區(qū)域 中所包含的所有數(shù)字均不可與對(duì)應(yīng)單元格中的數(shù)字相同。而 數(shù)獨(dú)的最終解需要使整個(gè)大正方形中的 81 個(gè)單元格對(duì)應(yīng)的 全部相關(guān)限制區(qū)域均符合約束條件。對(duì)于常規(guī)數(shù)獨(dú)而言，滿 足條件的解唯一存在。圖（b）為該數(shù)獨(dú)問題對(duì)應(yīng)的唯一解， 其中的深色單元格代表給出的作為最初推斷依據(jù)的提示數(shù)。 目前，利用計(jì)算機(jī)程序求解數(shù)獨(dú)問題的主要思路是基于 初步邏輯判斷后的窮舉法或回溯法。窮舉是指將數(shù)獨(dú)中的所 有候選情況

4、以多叉樹的形式逐層遍歷，并根據(jù)規(guī)則逐一排除， 最終在海量候選情況中篩選出問題的唯一解。該方法邏輯結(jié) 構(gòu)簡單，易于計(jì)算機(jī)程序?qū)崿F(xiàn)， 但運(yùn)算量極大， 算法效率低。 而回溯法是在窮舉法的基礎(chǔ)上對(duì)多叉數(shù)每一次子節(jié)點(diǎn)的搜 索增加驗(yàn)證機(jī)制，一旦判定某一節(jié)點(diǎn)不包含問題的解，則該 節(jié)點(diǎn)與其下的子樹全部排除并回溯至父節(jié)點(diǎn)重新搜索，直到 搜索至葉子節(jié)點(diǎn)并驗(yàn)證通過為止，即可得出滿足全部約束條 件的結(jié)果。相較于窮舉法，回溯法在搜索過程中排除了一部 分不必要的分支，明顯減少了運(yùn)算量，但由于缺乏數(shù)獨(dú)問題 所涉及的邏輯推斷成分，所以仍然搜索了大量不必要的候選 情況。 如果在回溯搜索的基礎(chǔ)上依據(jù)邏輯推斷方式增加相互 獨(dú)立的求

5、解策略，并通過策略模式根據(jù)出現(xiàn)的不同情況選擇 適當(dāng)?shù)乃惴ǎ憧梢栽诤艽蟪潭壬蠝p少候選情況的數(shù)量和未 知單元格的個(gè)數(shù)，從而降低回溯搜索的迭代次數(shù)，進(jìn)一步提 高運(yùn)算效率。 2 數(shù)獨(dú)問題的性質(zhì)與基礎(chǔ)求解策略 2.1 數(shù)獨(dú)的基本性質(zhì) 根據(jù)上文所述常規(guī)數(shù)獨(dú)問題的基本規(guī)則： “所有單元格 中的數(shù)字均不可與它的 3 個(gè)相關(guān)限制區(qū)域中所包含的任何數(shù) 字重復(fù)”，可以得出如下性質(zhì)： 性質(zhì) 1：某單元格中的數(shù)字不可能是它的 3 個(gè)相關(guān)限制 區(qū)域中存在的任何一個(gè)數(shù)字； 性質(zhì) 2：每一個(gè)單元格有且僅有唯一的解，它一定是1 到 9 這九個(gè)整數(shù)中的某一個(gè)。 性質(zhì) 3：任何一個(gè)單元格的 3 個(gè)相關(guān)限制區(qū)域都是由 9 個(gè)單元格

6、（包含自身）所構(gòu)成的， 1-9 這九個(gè)數(shù)字會(huì)在每一 個(gè)相關(guān)限制區(qū)域中出現(xiàn)且僅出現(xiàn)一次。 性質(zhì) 4：在某一行、某一列或某一九宮格中，若某一數(shù) 字只可能存在于確定的幾個(gè)單元格中，則其余單元格不可能 出現(xiàn)這一數(shù)字 2.2 數(shù)獨(dú)的基礎(chǔ)求解策略 根據(jù)上述性質(zhì)，可推導(dǎo)出針對(duì)數(shù)獨(dú)問題的 5 項(xiàng)基礎(chǔ)求解 策略，而針對(duì)該策略的描述、應(yīng)用實(shí)例及程序算法實(shí)現(xiàn)如下 所述： 策略 1：根據(jù)性質(zhì) 2 可知，當(dāng)某未知單元格中僅剩一個(gè) 候選數(shù)時(shí)，它必然是該單元格的唯一解。 該策略可能在兩種情況下得到應(yīng)用。其一是該未知單元 格的相關(guān)限制區(qū)域內(nèi)已經(jīng)存在八個(gè)互不相同的數(shù)字，則此單 元格只能選擇未出現(xiàn)的那個(gè)數(shù)字；其二是通過其它策略將

7、單 元格的候選數(shù)個(gè)數(shù)減小到了一個(gè)，從而得出唯一的解。 策略 1 實(shí)例：如圖 2 所示，為某數(shù)獨(dú)問題實(shí)例，深色背 景的單元格代表提示數(shù)的位置。通過候選數(shù)計(jì)算可知，在單 元格 R4C8 中的候選數(shù)列表內(nèi)僅存在一個(gè)數(shù)字“ 5”，則該單 元格的解必然為數(shù)字“ 5”。 策略 1 算法實(shí)現(xiàn)：在計(jì)算過程中，使用一個(gè)整型變量對(duì) 每一個(gè)未知單元格每次候選數(shù)個(gè)數(shù)的變化進(jìn)行記錄，當(dāng)?shù)扔?1 時(shí)，將剩余的唯一候選數(shù)作為該單元格的解。 策略 2 ：根據(jù)性質(zhì) 3 可知，當(dāng)某一數(shù)字在其一個(gè)相關(guān)限 制區(qū)域的所有未知單元格候選數(shù)列表中僅出現(xiàn)一次時(shí)，該數(shù) 字必定為該單元格的解。 策略2實(shí)例：在圖2中，C3列的所有未知單元格的候選

8、 數(shù)列表中僅有 R7C3中存在數(shù)字“ 2”，這說明該列中除 R7C3 以外的位置均不可能出現(xiàn)“2”， 故這一數(shù)字必然只能填在 單元格 R7C3內(nèi)。 策略 2 算法實(shí)現(xiàn)：對(duì)每一行、每一列及每一個(gè)九宮格中 各個(gè)數(shù)字在各未知單元格候選數(shù)列表中出現(xiàn)的次數(shù)進(jìn)行記 錄，當(dāng)某一數(shù)字的出現(xiàn)次數(shù)為 1 時(shí)，則找到候選數(shù)列表包含 該數(shù)字的單元格，將該數(shù)字作為單元格的解。 策略 3 ：根據(jù)性質(zhì) 4，在某一行、某一列或某一九宮格 中，有兩個(gè)單元格的候選數(shù)列表中僅包含相同的兩個(gè)候選數(shù)， 則這兩個(gè)數(shù)字必定只存在于這兩個(gè)單元格中，可在所對(duì)應(yīng)的 相關(guān)限制區(qū)域的其它單元格候選數(shù)列表中刪除這兩個(gè)數(shù)字。 策略3實(shí)例：如圖2中的C8

9、列，單元格 R5C8和R6C8 的候選數(shù)均為 “2”和“9” ，則該列中應(yīng)填的數(shù)字 “2”和“9” 只能在這兩個(gè)單元格中選擇，所以可在C8列其它單元格的 候選數(shù)列表中刪除數(shù)字“ 2”和“ 9”。策略 3算法實(shí) 現(xiàn)：對(duì)候選數(shù)個(gè)數(shù)為 2 的單元格所在的每一個(gè)相關(guān)限制區(qū)域 進(jìn)行搜索，若搜索到和它具有相同候選數(shù)列表的單元格時(shí)， 則在對(duì)應(yīng)的相關(guān)限制區(qū)域的其它單元格的候選數(shù)列表中刪 除這兩個(gè)數(shù)字。 策略 4：依據(jù)性質(zhì) 4，在某一九宮格中，當(dāng)所有候選數(shù) 列表中含有某一數(shù)字的單元格均位于同一行（列）時(shí)，則可 將這一數(shù)字在該行（列）中的其它單元格的候選數(shù)列表中刪 除。 策略4實(shí)例：在圖2的九宮格（R7C7-R9

10、C9中，數(shù)字 “3”僅在R7行出現(xiàn)（R7C7和R7C9，說明該九宮格中的數(shù) 字“ 3”只可能出現(xiàn)在 R7行。這也說明整個(gè) R7行中的數(shù)字 “3”僅會(huì)在九宮格（R7C7-R9C9的區(qū)域內(nèi)出現(xiàn)。因此，可 以在R7行的其它位置（九宮格 R7C7-R9C9以外）的候選數(shù) 列表中刪除數(shù)字“ 3”。 策略 4 算法實(shí)現(xiàn)：遍歷每個(gè)九宮格，依次記錄每個(gè)候選 數(shù)在該九宮格中出現(xiàn)的行數(shù)和列數(shù)。當(dāng)某一數(shù)字對(duì)應(yīng)可能出 現(xiàn)的行數(shù)或列數(shù)全部相同時(shí)，則刪除該行（列）中處于其它 九宮格范圍的單元格候選數(shù)列表中的這一數(shù)字。 策略 5：同樣依據(jù)性質(zhì) 4，在某一行或某一列中，當(dāng)所 有候選數(shù)列表中含有某一數(shù)字的單元格均位于同一九宮格

11、 時(shí)，則可將這一數(shù)字在該九宮格其它單元格的候選數(shù)列表中 刪除。 策略5實(shí)例：如圖2,在R7行中，數(shù)字8僅出現(xiàn)在R7C5 和R7C4這兩個(gè)單元格中，而它們同屬于一個(gè)九宮格 （R7C4-R9C6的區(qū)域內(nèi)。則該行中的數(shù)字“ 8”必然位于這 一九宮格中。故該九宮格中的數(shù)字“ 8”也應(yīng)該在R7行，所 以可將九宮格中其它位置候選數(shù)列表中的數(shù)字“ 8”刪除。 策略 5 算法實(shí)現(xiàn)：遍歷每一行（列 ，記錄每個(gè)候選數(shù) 所出現(xiàn)的列（行 ，當(dāng)某個(gè)數(shù)字所出現(xiàn)的位置均在同一九宮 格區(qū)域中時(shí)，則在該九宮格中其它行（列）的單元格候選數(shù) 列表中刪除這一數(shù)字。 3 數(shù)獨(dú)優(yōu)化求解算法 3.1 策略判斷算法 上文所述 5 項(xiàng)策略涵蓋

12、了數(shù)獨(dú)問題求解過程中的主要邏 輯推斷方式，且它們之間可以相互獨(dú)立存在。但是在各個(gè)策 略的執(zhí)行過程中也會(huì)互相影響和制約：一部分策略的執(zhí)行可 能會(huì)為其它策略的應(yīng)用創(chuàng)造新的條件，而也有可能會(huì)消除原 本具備執(zhí)行某項(xiàng)策略的初始條件。因此，在計(jì)算過程的不同 情況下，自主合理的選擇適宜的策略進(jìn)行逐步推導(dǎo)，會(huì)對(duì)提 高求解效率起到積極的作用。 為使整個(gè)算法能夠獨(dú)立于用戶運(yùn)行，從而實(shí)現(xiàn)自主根據(jù) 數(shù)值分布狀態(tài)選擇適當(dāng)?shù)牟呗赃M(jìn)行逐步求解，需要采用策略 模式。 策略模式是一種將一系列可獨(dú)立存在的具體策略進(jìn)行 封裝，并利用策略提取函數(shù)在程序運(yùn)行的各個(gè)階段自主選擇 適宜的策略進(jìn)行求解的特殊算法。 對(duì)于數(shù)獨(dú)問題而言，要實(shí)現(xiàn)在

13、推導(dǎo)過程中對(duì)各項(xiàng)策略的 自主提取，需要用到針對(duì)上述五項(xiàng)求解策略的提取算法。根 據(jù)這些策略執(zhí)行的先決條件，可設(shè)計(jì)提取算法如下： 對(duì)每一個(gè)未知單元格使用變量（CountCand （r, c）,記 錄并更新單元格（r, c）中的候選數(shù)個(gè)數(shù)。此外，依次對(duì)每 一行、每一列及每一個(gè)九宮格中各未知單元格進(jìn)行搜索，對(duì) 每一個(gè)未知數(shù)i在相關(guān)限制區(qū)域中出現(xiàn)的次數(shù)(Counti)及第 j次出現(xiàn)時(shí)的行數(shù)(Rowi (j)與列數(shù)(Columni (j)進(jìn)行 記錄，并在每一個(gè)相關(guān)限制區(qū)域搜索完成后，利用如下策略 判斷算法判定是否具備執(zhí)行某一策略的前提條件： 策略 1 判斷算法：當(dāng) CountCand( r，c)=1 時(shí)，

14、則單元 格(r，c)中僅存在唯一候選數(shù)，具備執(zhí)行策略1的條件； 策略 2 判斷算法：當(dāng) Counti=1 時(shí)，數(shù)字 i 僅在未知單元 格( Rowi ( 1)， Columni ( 1)出現(xiàn)過一次，則該單元格具 備執(zhí)行策略 2 的條件； 策略 3判斷算法：當(dāng) Counti1=2，Counti2=2 且 Rowi1( 1 ) =Rowi2( 1 )； Rowi1 ( 2)=Rowi2( 2)； Columni1 ( 1 )=Columni2 ( 1 )； Columni1 ( 2)=Columni2 ( 2)時(shí)，說明未知數(shù) i1 ， i2 僅存在于單元格 ( Rowi1 ( 1 )， Colum

15、ni1 ( 1 )和( Rowi1 ( 2)， Columni1 ( 2)中，適用于策略 3； 策略4判斷算法：當(dāng)完成搜索九宮格(r，c)時(shí)(r, c) 代表九宮格左上角的坐標(biāo))，若Rowi (1) =Rowi (2)二， 或Columni (1) =Columni (2)=，則說明該九宮格內(nèi)的 數(shù)字 i 位于同一行或同一列中，則適用于策略 4； 策略 5 判斷算法： 在完成搜索第 n 行后，若對(duì)于數(shù)字 i： 1Counti3，且 Columni (1)、Columni (Counti )均 為 m 、 m+1 或 m+2 時(shí)( m 為 1 或 4 或 7)，則適用于策略 5。 3.2 數(shù)值的初步推斷 欲應(yīng)用上述策略模式求解數(shù)獨(dú)，需要首先根據(jù)有限的提 示數(shù)和數(shù)獨(dú)的基本原則確定各未知單元格的候選數(shù)，并以此 為基礎(chǔ)， 依次執(zhí)行各項(xiàng)策略判斷算法， 進(jìn)而選取恰當(dāng)?shù)牟呗裕?將未知單元格的個(gè)數(shù)及各未知單元格中的候選數(shù)個(gè)數(shù)降至 最小，從而在最大程度上降低后續(xù)計(jì)算的復(fù)雜程度。對(duì)于數(shù) 獨(dú)問題數(shù)值初步推斷的程序流程圖如圖3。 通過執(zhí)行上述數(shù)值初步推斷流程，能夠使各項(xiàng)策略在適 當(dāng)?shù)臄?shù)值分布狀況下得到執(zhí)行，從而保證了程序運(yùn)算的高效 性。 3.3 基于策略模式的回溯法求解 對(duì)于較高難度的數(shù)獨(dú)，單純依靠由上述 5 項(xiàng)求解策略構(gòu)