【文章內(nèi)容簡(jiǎn)介】 和 Expression Blend，這些工具將為程序員與設(shè)計(jì)人員節(jié)省更多的編碼時(shí)間。 總而言之，通過 WPF， .NET Framework 提供了一種比較完整和一致的解決方案，以用于應(yīng)對(duì)用戶界面方面的難題。 數(shù)獨(dú)的通解方法 數(shù)獨(dú)解法全是由規(guī)則衍生出來的，基本解法分為兩類思路，一類為基礎(chǔ)摒除法，一類為 唯一法 [9]。 基礎(chǔ)摒除法就是利用 1～ 9 的數(shù)字在每一行、每一列、每一宮都只能出現(xiàn)一次的規(guī)則進(jìn)行解題的方法。首先，根據(jù)橫列、豎列和宮格的限制條件排除各個(gè)數(shù)格不可能出現(xiàn)的數(shù)字，并從 1－ 9 將各個(gè)可能的候選數(shù)用小字體逐個(gè)寫進(jìn)每個(gè)空白的格子。尋找九宮格摒除解：找到了某候選數(shù)在某一個(gè)九宮格可填入的位置只余一個(gè)的情形 ， 亦即找到了該數(shù)在該九宮格中的填入位置。尋找列摒除解：找到了某候選數(shù)在某列可填入的位置只余一個(gè)的情形 ， 亦即找到了該數(shù)在該列中的填入位置。尋找行摒除解：找到了某候選數(shù)在某行可填入的位置只余一個(gè)的情形 ， 亦即找到 了該數(shù)在該行中的填入位置?；A(chǔ)摒除法的提升方法是區(qū)塊摒除法 ， 是直觀法中使用頻率最高的方法之一。 唯一解法如下：當(dāng)某行已填數(shù)字的宮格達(dá)到 8 個(gè) ， 那么該行剩余宮格能填的數(shù)字就只剩下那個(gè)還沒出現(xiàn)過的數(shù)字了，成為行的唯一解。當(dāng)某列已填數(shù)字的宮格達(dá)到 8 個(gè) ， 那么該列剩余宮格能填的數(shù)字就只剩下那個(gè)還沒出現(xiàn)過的數(shù)字了，成為列的唯一解。當(dāng)某九宮格已填數(shù)字的宮格達(dá)到 8 個(gè) ， 那么該九宮格剩余宮格能填的數(shù)字就只剩下那個(gè)還沒出現(xiàn)過的數(shù)字了，成為九宮格的唯一解。 4 3. 可行性分析與需求分析 系統(tǒng)軟件開發(fā)環(huán)境 系統(tǒng)環(huán)境： Windows Vista 或 Windows 7 以上版本或者 Windows XP 安裝 .NET Framework 硬件環(huán)境：支持 DirectX9/10 的顯卡支持 開發(fā)語言： C和 XAML IDE： Microsoft Visual Studio 20xx、 Expression Blend 系統(tǒng)任務(wù)的可行性分析 經(jīng)濟(jì)可行性 本游戲使用面向?qū)ο缶幊趟枷朐O(shè)計(jì)，易于編寫和維護(hù)，總體開發(fā)成本低。由于游戲規(guī)則簡(jiǎn)單，入門度低，人人都可以玩，而且容易入迷。 技術(shù)可行性 .NET Framework 提供了豐富的 公共語言運(yùn)行庫(kù)和基類庫(kù) ，對(duì)于本游戲的開發(fā)可以簡(jiǎn)化編碼，避免不必要的錯(cuò)誤。同時(shí)使用的 WPF 技術(shù)提供了一種比較完整和一致的解決方案，以用于應(yīng)對(duì)用戶界面設(shè)計(jì)方面的難題。 AI 算法方面，將建立解題器插件，可以提供多種算法來解決數(shù)獨(dú)謎題。充分利用當(dāng)今計(jì)算機(jī)的優(yōu)越性能，使用成熟的算法 —— 遞歸算法，實(shí)現(xiàn)起來容易。 系統(tǒng)安全性分析 游戲使用到的解題器是經(jīng)過 動(dòng)態(tài)加載預(yù)編譯 模塊實(shí)現(xiàn)的， 為了幫助保護(hù)計(jì)算機(jī)系統(tǒng)防止受信任的代碼有意或無意地危害安全 ，使用了 .NET Framework 提供了一種稱為 “代碼訪問安全性 ”的安全機(jī)制 。根據(jù)代碼請(qǐng)求的權(quán)限和安全策略 允許的操作，向加載的每個(gè)程序集授予權(quán)限 ，這將 最大限度地減少由于代碼中的安全脆弱性而造成的損害。 .NET Framework 的 垃圾回收機(jī)制，通過 回收器管理應(yīng)用程序的內(nèi)存分配和釋放 ，從而使內(nèi)存得到優(yōu)化。 垃圾回收器優(yōu)化引擎根據(jù)正在進(jìn)行的分配情況確定執(zhí)行回收的最佳時(shí)間。當(dāng)垃圾回收器執(zhí)行回收時(shí)，它檢查托管堆中不再被應(yīng)用程序使用的對(duì)象并執(zhí)行必要的操作來回收它們占用的內(nèi)存 [10]。 系統(tǒng)功能需求分析 按照用戶需求，本系統(tǒng)大致分為三大功能：游戲界面（ UI）功能、數(shù)據(jù)處理功能和用戶功能。 游戲界面（ UI）功能，向用戶顯 示游戲的信息，包括數(shù)獨(dú)棋盤、計(jì)時(shí)器、游戲菜單等。 數(shù)據(jù)處理功能負(fù)責(zé)內(nèi)部數(shù)據(jù)的處理，是該游戲的核心，包括數(shù)獨(dú)迷局生成、數(shù)獨(dú)填充完成的驗(yàn)證、數(shù)獨(dú)的 AI 解題功能等。 下面介紹用戶功能， 圖表 31 用戶功能用例圖 為用戶功能用例圖，是用戶直接使用的游戲功能，其功能主要通過鼠標(biāo)操作完成。每個(gè)用例的簡(jiǎn)要說明如下： 5 用 戶數(shù) 獨(dú) 游 戲新 游 戲讀 取 游 戲保 存 游 戲游 戲 設(shè) 定電 腦 解 題 圖表 31用戶功能用例圖 A. 新游戲：產(chǎn)生新的數(shù)獨(dú)游戲。 B. 保存游戲： 保存當(dāng)前游戲狀態(tài)。 C. 讀取游戲：讀取保存的游戲狀態(tài)。 D. 游戲設(shè)定：包括設(shè)定游戲生成方法、游戲時(shí)間難易程度和游戲規(guī)格等。 E. 電腦解題：通過電腦解決迷局。 6 4. 系統(tǒng)設(shè)計(jì) 系統(tǒng)模塊劃分 根據(jù)上一章的需求分析的結(jié)果采用模塊化程序設(shè)計(jì)法，將系統(tǒng)分為三大模塊：用戶功能模塊、用戶界面 UI 模塊和數(shù)據(jù)處理模塊。 用 戶 功 能 模 塊新 游 戲游 戲 保 存 、 讀 取 游 戲 計(jì) 時(shí) 電 腦 解 題游 戲 設(shè) 置數(shù) 據(jù) 處 理 模 塊迷 局 生 成 解 題 填 充 數(shù) 字 驗(yàn) 證U I游 戲 菜 單 棋 盤 解 題 器 插 件 其 他 U I計(jì) 時(shí) 器圖表 41 系統(tǒng)模塊圖 圖表 41 系統(tǒng)模塊圖 ，實(shí)線連接的為用戶可見模塊，用戶模塊是用戶可通過鼠標(biāo)操作的模塊； UI模塊為呈現(xiàn)給用戶的界面；虛線連接的為不可見模塊（數(shù)據(jù)處理模塊），即內(nèi)部實(shí)現(xiàn)模塊。 模塊內(nèi)部關(guān)系說明 模塊內(nèi)部關(guān)系說明模塊之間的聯(lián)系是通過內(nèi)部數(shù)據(jù)實(shí)現(xiàn)的，下面介紹模塊之間的聯(lián)系。 繪 圖A I數(shù) 據(jù) 綁 定數(shù) 據(jù)用 戶 按 鍵 事 件觸 發(fā)修 改內(nèi) 部 數(shù)據(jù) 圖表 42模塊關(guān)系圖 圖表 42 模塊關(guān)系圖 所示模塊設(shè)計(jì)相對(duì)獨(dú)立，各個(gè)模塊都是通過內(nèi)部數(shù)據(jù)進(jìn)行聯(lián)系的。 游戲內(nèi)核包括所有游戲信息，全部為類的成員數(shù)據(jù)，而它的各個(gè)模塊則為類的方法（函數(shù)）用于 7 相應(yīng)用戶的按鍵事件。 繪圖（ UI）功能，向用戶顯示游戲的信息，包括數(shù)獨(dú)游戲迷局、計(jì)時(shí)器、游戲菜單等，這些主要由 XAML 來實(shí)現(xiàn)。 當(dāng)用戶按鍵時(shí)觸發(fā) UI 的繪圖，同時(shí)后臺(tái)的代碼處理按鍵事件，從而使得綁定到前臺(tái)的內(nèi)部數(shù)據(jù)改變。 AI 功能負(fù)責(zé)內(nèi)部數(shù)據(jù)的處理，是該游戲的核心，所有功能的實(shí)現(xiàn)幾乎都與本模塊有關(guān)，包括數(shù)獨(dú)迷局游戲生成、數(shù)獨(dú)填充完 成的驗(yàn)證、數(shù)獨(dú)的 AI 解題等。 AI 模塊由很多松散的方法組成，各個(gè)函數(shù)實(shí)現(xiàn)單一的功能，便于修改和移植。 數(shù)獨(dú)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 由于數(shù)獨(dú)游戲的特殊性和模塊設(shè)計(jì)的獨(dú)立性，各個(gè)模塊間的通信必須依靠全局變量來實(shí)現(xiàn)。在此，設(shè)計(jì)類用以封裝所需要的字段和方法，這樣就可以實(shí)現(xiàn)游戲的大部分功能。對(duì)于這個(gè)類中的函數(shù)（方法），類的成員數(shù)據(jù)相當(dāng)于全局變量，這樣各個(gè)函數(shù)的通信就不會(huì)成為問題。 圖表 43數(shù)獨(dú)結(jié)構(gòu)圖 通過觀察一個(gè)典型的 9 9 數(shù) 獨(dú)如 圖表 43 數(shù)獨(dú)結(jié)構(gòu)圖 ，數(shù)獨(dú)是由 3 3 個(gè)宮格組成，而每個(gè)宮格又可以由 3 3 個(gè)數(shù)格組成，在此將其棋盤抽象為最小的數(shù)格。棋盤預(yù)先放入的已知數(shù)應(yīng)該是只讀的，不可以修改，同時(shí)應(yīng)該有用于標(biāo)志數(shù)字是否合法 的字段 。 主要數(shù)據(jù)表示方法： （ 1）棋盤的最小單位 —— 數(shù)格用 Cell 類定義。定義字段 valueValue 存放數(shù)字， readOnlyValue 標(biāo)識(shí)數(shù)格是否為只讀數(shù)據(jù)， possibleValuesValue 存放可填入的數(shù)， isValidValue 標(biāo)識(shí)數(shù)數(shù)格是否成立。 （ 2）宮格用 Box 類定義。動(dòng)態(tài)數(shù)據(jù)集合 Rows 存放宮格里數(shù)格， isValidValue 標(biāo)識(shí)值是否成立。 （ 3）數(shù)獨(dú)棋盤用 Board 類定義。 Board 類及其類似 Box 類，只是字段動(dòng)態(tài)數(shù)據(jù)集合 Rows 存放的是數(shù)獨(dú)棋盤里的宮格， isValidValue 標(biāo)識(shí)填入的數(shù)是否成立， isFullValue 標(biāo)識(shí)棋盤是否填滿。 邏輯處理設(shè)計(jì) 邏輯處理部分主要涉及到的是題目的生成方法，默認(rèn)的題目生成方式采用隨機(jī)生成的方法，速度較快，但生成的題目不一定有解。在玩家選擇相應(yīng)的解題器后，可以通過解題器產(chǎn)生有解的題目。 快速隨即生成數(shù) 獨(dú)題目 一種創(chuàng)建數(shù)獨(dú)迷局的方法是通過使用窮舉法（ Brute Force），通過這種方法可以快速生成大量不同的題目。在 20xx 年， 數(shù)學(xué)家貝米耳與羅思坦算出一共有 6670903752021072936960 種可能的數(shù)獨(dú)謎題[11]。通過用 19 的隨機(jī)數(shù)填充一個(gè)數(shù)組，然后檢查數(shù)組是否滿足數(shù)獨(dú)游戲的三個(gè)屬性：即行、列和宮格不存在沖突的數(shù)字，但是并不是所有產(chǎn)生的游戲都有解。 8 好的數(shù)獨(dú)題目要求要有唯一解而且已知數(shù)要越少越好 。目前 ，對(duì)于 9 9 的數(shù)獨(dú)只要 18 個(gè)數(shù)字就可以產(chǎn)生出唯一解的數(shù)獨(dú)謎題。 如果不要求 對(duì)稱，給定的數(shù)字是 17 個(gè) 就可以產(chǎn)生有解的數(shù)獨(dú)題目，通過使用 17 個(gè)已知數(shù)，數(shù)學(xué)家 Gordon Royle 發(fā)現(xiàn)了 35396 這樣不同的難題 [12]。 到目前為止，少于 17 個(gè)已知數(shù)的數(shù)獨(dú)題目都不能產(chǎn)生唯一解。在此，本游戲采用使用至少 18 個(gè)已知數(shù)來產(chǎn)生數(shù)獨(dú)題目。 本游戲采用的快速生成游戲的實(shí)現(xiàn)方法：隨機(jī)生成一個(gè)數(shù)填充隨機(jī)的還沒有值的數(shù)格，并檢測(cè)該數(shù)所在的行、列和宮格是否已經(jīng)有此數(shù) 。 如果沒有 此數(shù) 則賦值，否則跳出 。 接著， 繼續(xù)前面的步驟，直到填充到指定數(shù)目的數(shù)格。 使用解題器生成數(shù)獨(dú)題目 嚴(yán)格的說，數(shù)獨(dú)題目要求要有唯一解，通過快速法產(chǎn)生的游戲不 一定有解，為此需要解題器的幫助以生成有唯一解的數(shù)獨(dú)游戲。實(shí)現(xiàn)方法如下：首先在將一個(gè)隨機(jī)數(shù)填入空白棋盤里隨機(jī)的一個(gè)數(shù)格，然后讓解題器填充上剩下的所有數(shù)格，接下來就是再挖空一定的數(shù)格。這種方法將花費(fèi)比較長(zhǎng)的時(shí)間，主要取決于解題器算法的效率。 數(shù)獨(dú)解題算法的實(shí)現(xiàn) 本游戲開發(fā)使用了解題器插件，它可以提供多種的解題算法，玩家可以選擇相應(yīng)的解題器用于實(shí)現(xiàn)解題和生成題目。 解題器默認(rèn)使用的是成熟的 算法 —— 遞歸回溯實(shí)現(xiàn)的。雖然，理論上遞歸回溯算法需要多次的調(diào)用函數(shù)自己，需增加額外的系統(tǒng)堆棧，可能消耗大量空間，對(duì)執(zhí)行效率有一 定的影響。但由于處理的數(shù)獨(dú)游戲數(shù)據(jù)量較小，同時(shí)現(xiàn)在計(jì)算機(jī)的高性能也減小了遞歸回溯對(duì)時(shí)間的影響。因此，默認(rèn)采用了代碼清晰簡(jiǎn)潔，可讀性很強(qiáng)的遞歸算法實(shí)現(xiàn)解題。 實(shí)踐證明，成熟的遞歸回溯法解決數(shù)獨(dú)問題，可以 有 著極快的效果。在遞歸之前，可以通過一點(diǎn)小小的預(yù)處理，可以使遞歸算法時(shí)間縮短，這個(gè)處理可以稱為“有限遞推” [13]，算法的大致流程圖如圖表 44 數(shù)獨(dú)遞歸算法流程圖 ： 有 限 遞 推 預(yù) 處 理候 選 數(shù) 列 表變 化結(jié) 束開 始從 有 最 少 候 選 數(shù) 列表 選 取 一 個(gè) 數(shù) 猜 想候 選 數(shù) 列 表 都 只剩 一 個(gè) 候 選 數(shù)否否是是 圖表 44數(shù)獨(dú)遞歸算法流程圖 算法主要如下： （ 1）建立一個(gè)數(shù)獨(dú)棋盤結(jié)構(gòu)的候選數(shù)列表里面包含了每個(gè)數(shù)格的候選數(shù)，對(duì)于已經(jīng)有已知數(shù)的，列表里就只有一個(gè)已知數(shù)。對(duì)于待填數(shù)格，則將所有可能的候選數(shù)填入。 （ 2）然后，“有限遞推”預(yù)處理算法查詢候選數(shù)列表每一行、列和宮格查找已知數(shù)和候選數(shù)有沖突的項(xiàng)，并將其從列表移走。執(zhí)行一次就可能確定下一些原來沒有確定的數(shù)字，那么此時(shí)，原始的候選數(shù)列表的值必然改變。再在次執(zhí)行此過程修訂列表，而修訂之后若還有數(shù)據(jù)改變，那么就 在執(zhí)行此過程了，直到候選數(shù)列表的值不再變化。如此循環(huán)下去，就能最大限度地確定下題目本身含義與規(guī)則而確定下的內(nèi)容。 （ 3）接著，解題器查找包含有最少候選數(shù)的列表，并隨機(jī)選取一個(gè)數(shù)作為正確的數(shù)進(jìn)行猜想。 9 （ 4）在每一次可能的猜測(cè)過程中，解題器通過深拷貝并實(shí)現(xiàn)遞歸回到步驟（ 2）。通過這種方式，若當(dāng)前情況無解的時(shí)候回溯，直到所有的候選數(shù)列表有唯一候選數(shù)。 （ 5）當(dāng)所有的猜測(cè)都嘗試之后如果沒有解，則返回 false。相反，如果棋盤都被填滿之后，并且驗(yàn)證通過，則表示數(shù)獨(dú)謎題有解。 圖表 45解題器類的 UML圖 解題器的類如 圖表 45 解題器類的 UML 圖 ，該解題器類中包含了解題算法的入口點(diǎn)方法 Solve()，外部可直接調(diào)用此公共方法進(jìn)行解題。 Solve()方法中則調(diào)用解題器類私有的遞歸解題方法RecursiveSolve()，在每次遞歸解題方法調(diào)用自己前，需要使用深度拷貝方法 DeepCopy()將當(dāng)前對(duì)象的所有字段進(jìn)行執(zhí)行逐位復(fù)制使其支持遞歸回溯。在把所有候選數(shù)都猜測(cè)完后，調(diào)用驗(yàn) 證方法 Validate()進(jìn)行驗(yàn)證。 UI界面設(shè)計(jì) 游戲的用戶交互界面主要在一個(gè)窗口中呈現(xiàn)，方便用戶操作。 標(biāo)題 游戲菜單 游戲棋盤 計(jì)時(shí)器 解題器插件 圖表 46游戲界面布局 如 圖表 46 游戲界面布局 頂端顯示標(biāo)題，左邊是游戲菜單，右邊是游戲計(jì)時(shí)信息，底部是解題器插件，中間是游戲棋盤。當(dāng)然，這些面板都應(yīng)該與分辨率無關(guān)，以適應(yīng)不同用戶的顯示器。 游戲棋盤設(shè)計(jì) 位于中間的游戲棋盤是本游戲的重點(diǎn)。游戲棋盤默認(rèn)繪制的是 9 9 的標(biāo)準(zhǔn)棋盤，同時(shí)還提供了 4 4 和 16 6 規(guī)格的棋盤。棋盤主要通過自定義控件 SudokuBoard 來實(shí)現(xiàn)。 SudokuBoard 是通過一系列 10 的嵌套的 ItemsControl 控件來繪制展現(xiàn)棋盤。這樣就可以設(shè)置游戲規(guī)格，選擇不同數(shù)目的數(shù)格來實(shí)現(xiàn)生成。 除了生成指