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