完成總結報告項目名稱：數獨游戲設計與實現組 員：王鄭合 2014204081 欒杰 2014204080 文寬 2014204104 二二二二年三月二十四日1 問題描述1.1 問題說明數獨游戲起源于瑞士，由十八世紀的瑞士數學家歐拉發明，是一種數字拼圖游戲，其游戲規則是：在99的大九宮格內，已給定若干數字，其他宮位留白，玩家需自己按照邏輯推敲出剩下的空格里是什么數字。必須滿足的條件：每一行與每一列都有1到9的數字，每個小九宮格里也有1到9的數字，并且一個數字在每行、每列及每個小九宮格里只能出現一次，既不能重復也不能少。每個數獨游戲都可根據給定的數字為線索，推算解答出來。 1.2 數獨求解描述 由于數獨游戲的推廣與普及，在當今世界上有著大量的數獨愛好者，本項目的目的就是按照數獨的游戲規則，通過對數據結構的分析和人工智能算法的研究，利用計算機程序來實現對已知數獨游戲的快速求解。1.3 數獨出題描述數獨游戲挑戰者的水平各異，對數獨題目的難度要求各不相同，所以本項目致力于設計一種算法，使其在盡可能短的時間內生成不同難度等級的數獨題，以滿足不同水平游戲者的需求。同時，該算法還要考慮到三個方面要求：可變化的難度、解的唯一性和算法復雜度最小化。2 功能分析2.1 數獨求解數獨雖然號稱是數學問題, 但在求解時幾乎用不上數學運算方法，事實上它更像是一種思維方式。數獨游戲開始后，要想在空格中填入正確的數字，先要根據數獨游戲規則對1-9分別進行邏輯判斷，然后選擇正確的數字填入空格。另外，由于某個格子填入數據時，有可能還要對原來已填入的數據進行修正，所以可以考慮使用遞推和回溯搜索來求解數獨問題。2.2 數獨出題出題時，要能保證算法生成的數獨題具有可變化的難度和唯一解,該算法內部應該包含有對數獨題的求解和評級功能。本項目使用了一種基于“挖洞”思想的數獨題生成算法，將該算法的設計工作分為評級、求解和生成三部分工作。利用隨機數出現的概率不同來確定不同的難度，通過避免重填一個被“挖去”的格子，或者回溯到一個曾經無法“挖去”的格子，來降低算法的復雜性。2.3 題目保存當用戶需要退出卻仍沒有完成數獨題目的解答時，可以選擇是否保存當前的求解進度。如果需要，本系統會幫助用戶將目前未完成的數獨題目的解答進度保存起來，以便用戶下次使用本系統時，可以繼續解答上次未完成的題目。2.4 題目讀取用戶可以在程序開始運行后，選則讀取一道之前保存起來的題目進行解答，被讀取的題目將會顯示到程序界面上。3 系統設計3.1 功能結構圖本程序主要有數獨求解和數獨出題兩個功能，數獨求解包括題目檢驗、解題和輸入輸出，數獨出題包括答案檢驗、難度選擇、出題和輸入輸出。3.2 業務流程圖3.3 類圖SudokuDlg類：程序的界面類。Solve類：實現數獨題目求解功能。Make類：實現數獨題目出題功能。Pre類：對數據進行預處理。3.4 界面設計3.5 算法設計3.5.1 數獨求解算法解決該數獨求解問題時的要考慮的主要方面有： 判斷題目合法性，即驗證給出數據本身是否符合游戲規則，行、列以及小九宮中從不重復地出現數字1-9； 采用遞推算法，若可以填入數字則填入數字，并入棧以便回溯，否則回溯至前面填入數字處重新填數； 所有空白處都要填滿數據；其中，最重要的就是如何通過遞推算法填入正確的數字，或者通過回溯算法重新填入數字并得到最終解，這是本算法的核心內容。回溯法是解決數獨問題的有效方法，有著較快的解題速度。然而一般的常用的回溯算法仍然有不足之處，比如會進行重復的運算。所以在采用回溯法之前，還可以利用一點小技巧，以縮短回溯算法的運行時間，甚至可將運行時間縮短接近于0。這個小技巧即在回溯算法的基礎上，采用有限遞推算法進行預處理。算法活動圖如下：3.5.1 數獨出題算法要想設計一個算法用以生成各種難度等級的數獨題，通過對游戲規則的分析，首先從三個方面定義難度等級，分別是已知格總數、已知格的分布和窮舉搜索復雜度。本算法采用“挖洞”思想，經過以下步驟生成數獨題：用隨機算法生成一個數獨題目；用求解算法生成終盤；根據難度挖去部分數字；整個生成數獨題的算法分為兩步執行：先利用拉斯維加斯隨機算法隨機生成一個填滿數字且符合游戲規則的終盤；而后根據所需求的難度等級抹去一些數字，難度等級由隨機數出現的概率來決定。算法活動圖如下：4 系統實現4.1 開發平臺本項目基于Visual Studio 2010平臺的MFC，采用C+語言進行開發與測試。4.2 運行環境本項目可在各個版本的Win7系統或者Windows XP系統下運行。4.3 數據結構數據結構是計算機存儲、組織數據的方式。通常情況下，精心選擇的數據結構可以帶來擁有更高的運行或存儲效率的算法。一般認為，一個數據結構是由數據元素依據某種邏輯聯系組織起來的，對數據元素間邏輯關系的描述稱為數據的邏輯結構；數據必須在計算機內存儲, 數據的存儲結構是數據結構的實現形式， 是其在計算機內的表示。數獨從形式上看是一個方陣, 十分適合用數組來表示。4.3.1 主要數組本項目中所用到的主要數組有：int sudoku82該數組的用途是存儲題目以及保存最終結果,所有的99個數字被依次存儲在該數組中，空白處則初始化為0。之所以把數組范圍設計成82 而不是81，是為了程序的易讀性，使得數組元素的最大下標可達81，下同。int fix82 該數組的用途是若sudoku數組中某位置的數字不為空，則fix數組相應位置的元素值為1，否則為0，即fix數組是用來記錄哪些位置的數字是已經確定下來的。int possible8210該數組的用途是記錄所有未確定數字的所有可能性，possible數組各元素的值在初始化時被初始化為與其第二維的下標一致，即0-9（其中0表示空值）；在中間計算過程中，若發現第一維某位置的某種可能性已不復存在，則將第一維下標是該位置而第二維下標是該不再可能的數字的元素值改為-1。int review82該數組的用途類似于棧，在回溯算法過程中起到至關重要的作用。回溯之前，要把所有fix數組中值為0的位置依次存放進review數組；回溯中，由低到高依次逐漸確定這些位置的數值，無法確定者（即1-9的數字都不適合者）則應當回退到前一個位置，并修改其fix數組中的值，依次類推，直至review數組所存放的所有位置的值都能確定（即題目完成），或回退到最初點的前一個位置（即題目有誤）。4.3.2 相關函數本項目中為實現算法的數據結構所用到的主要函數如下：void setPossible（）該函數是用來設置possible數組中元素的值，其具體功能是：對于fix數組中每一個值為0的位置（即對于每一個沒有確定下數字的位置），考察其可能的數字是哪些，并記錄下來。考察的方法是：在1-9這些數字中除去在當前行、列、九宮中已有的數字，剩下的即為可能的取值對象。bool fixPossible（）該函數是用來修改fix數組和possible數組中元素的值，其返回值表示了在此次運行該函數過程中是否執行了修改。其具體功能是：對于fix數組中每一個值為0的位置（即對于每一個沒有確定下數字的位置），考察其可能的數字的個數， 若為1，則將fix數組該位置的值改為1且sudoku數組該位置的值改為該唯一可能的數字（即該位置的值已確定下來），且返回真；若沒有只有一種可能性的位置， 則返回假。bool isExist（int i，int j）該函數用于回溯過程中，其用途是：判斷sudoku數組中位置為i的元素的值是否可能為j，即判斷的是位置i所在的行、列以及九宮中是否已經存在數字j，若存在則返回真，否則返回假。4.4 求解算法實現4.4.1 有限遞推在執行一次fixPossible函數之后，就可能會確定下一些原來沒有確定的數字，那么此時possible數組的值必然也會變動。這是因為確定下的數字越多，某些位置的可能數字的數目就會減少，那么此時就應再執行setPossible函數修改possible數組。而修改之后可能又會出現一些只有一種可能性的位置，那么就應該再執行fixPossible函數。于是，只要如此循環往復下去，就能最大限度地確定下根據題目本身含義和規則而確定下的內容。確定的數字越多，對于將來回溯也就越有利。經驗表明，有些數獨題直接就可以通過執行大約10多次的有限遞推循環體解決。一般情況下，有限遞推的循環結束只有兩種情況：一是推出了全部結果；二是fixPossible函數返回值為假，即不存在只有一種可能性的位置。預處理的主要代碼見附錄。4.4.2 回溯回溯是數獨求解算法中最為關鍵的部分，其主要步驟是：按下標的由低到高掃描fix數組，將值為0的位置記錄進review數組，記錄的順序也是由低到高，最后記錄下fix數組中為0位置的個數再加1；把review數組看作棧，記錄棧頂；先設置一個bool型標志變量flag并初始化為true，下面各步驟都將在一個條件始終為真的死循環中進行，該循環由一條對flag進行真假判斷的語句分成兩大部分。若當前棧頂是經過了回退操作而達到的，則flag會已被記錄為false；否則flag為true。死循環結束的條件是review數組（棧）中top與max的值相等，即解出最終結果，或者是無解，最終top小于0。在死循環中，若flag為true，則進入步驟，否則進入步驟。若flag為true，則說明棧頂是經過正常的假設而達到的，并非由回退達到, 那么根據possible數組以及isExist函數對棧頂所保存位置的可能出現的數字進行判斷，把遇到的第一個可能數字放進sudoku數組，并把fix數組的該位置的值設為1，并判斷是否已經解出結果，即review數組（棧）中top和max的值是否相等。若相等，則得出結果并退出死循環；若發現1-9都不可能應用在棧頂所保存的位置，則說明前面的假設有錯誤，此時應當回退。即fix數組和sudoku數組的該位置重設為0，top減1，并將flag的值設為false。然后結束本輪循環體，繼續下一輪的循環。若flag為false，說明是經過了回退才達到現在這個棧頂的，那么若仍然沒有可能的數字可以應用在當前棧頂所保存的位置上，則繼續執行出棧操作，即fix數組和sudoku數組的該位置的值重設為0，top減1；否則將遇到的第一個可能數字應用到該位置，即再設好sudoku數組和fix數組，將top加1，并將flag的值設為true。然后結束本輪循環體，繼續下一輪的循環。回溯的主要代碼見附錄。4.5 出題算法實現4.5.1 生成終盤數獨出題時要先采用拉斯維加斯算法隨機生成一個數獨題的終盤。首先，在一個數獨空盤中隨機選中n個格子，在這些格子內隨機填人數字1-9；然后，調用數獨求解算法對這個已知n格的數獨題S(n)進行求解。如果S(n)有解，則返回true，否則返回false。拉斯維加斯算法的思想便是不斷重復執行上述步驟，直至其返回值為true為止。生成隨機數的主要代碼見附錄。4.5.2 挖洞算法挖洞算法的基本思想就是挖去一個數獨終盤上的一些格子，使其成為有唯一解的數獨題目。然而挖洞的機制是多種多樣的，本項目為了加快出題算法的速度，利用不同的隨機挖洞概率來區分不同的難度。挖洞的主要代碼見附錄。4.6 程序運行截圖開始：數獨求解，手動輸入題目：數獨求解，讀取保存的題目：解出答案：數獨出題，選擇難度：得出題目：保存題目：保存和打開題目的文件格式：5 測試5.1 解題測試選取5個難度共25道不同的數獨題目進行解題測試，記錄程序運行時間，檢驗運算結果是否正確，并對實驗結果進行分析。難度1：題目12345Average時間14ms13ms22ms22ms20ms18.2ms結果正確正確正確正確正確-難度2：題目12345Average時間21ms20ms20ms33ms21ms23.0ms結果正確正確正確正確正確-難度3：題目12345Average時間22ms26ms25ms23ms26ms24.4ms結果正確正確正確正確正確-難度4：題目12345Average時間28ms24ms35ms29ms26ms28.4ms結果正確正確正確正確正確-難度5：題目12345Average時間28ms50ms22ms44ms29ms34.6ms結果正確正確正確正確正確-通過對實驗數據的分析可知：本算法得出的結果全部正確，說明本算法成功實現了通過計算機人工智能方法對數獨問題求解；隨著題目難度加大，平均運行時間逐漸加長；本次試驗中，運行時間最長的題目不超過50ms，大多數題目在20-30ms內完成，說明本算法的運行速度是比較快捷的。5.2 出題測試5個難度各進行5次數獨出題運算，記錄運行時間，并比較得出的題目是否會有重復。難度1：題目12345Average時間9ms10ms6ms7ms9ms8.2ms重復-無難度2：題目12345Average時間9ms8ms9ms7ms8ms8.2ms重復-無難度3：題目12345Average時間9ms9ms6ms5ms9ms7.6ms重復-無難度4：題目12345Average時間10ms9ms8ms6ms11ms8.8ms重復-無難度5：題目12345Average時間7ms9ms10ms5ms10ms8.2ms重復-無通過對實驗數據的分析可知：本此實驗中，各組均無重復的題目出現，說明本算法成功實現了通過計算機人工智能方法對數獨問題的出題；程序的運行時間不隨難度增加而加長，個難度的運行時間基本一樣；運行時間基本維持著8-9ms左右，說明本算法的運行速度是比較快捷的。6 工作總結較好地完成了數獨求解和數獨出題的算法的設計與實現；對算法進行功能測試，驗證了算法的有效性，并證明了算法具有良好的時間效率；實現了良好的用戶界面；實現了數獨題目的讀取和保存功能；通過本項目，對人工智能技術有了進一步的了解，并初步掌握了MFC編程；鍛煉了團隊合作能力。7 項目安排任務負責人時間項目建議書王鄭合、文寬、欒杰9.19-9.30數獨求解功能王鄭合、欒杰10.1-10.21數獨出題功能王鄭合、文寬10.1-10.21測試欒杰10.22-10.23中期進展報告王鄭合、文寬、欒杰10.24-10.28界面文寬10.29-11.4功能集成王鄭合11.5-11.9測試與改進文寬、欒杰11.10-11.20完成總結報告王鄭合、文寬、欒杰11.21-11.25參 考 文 獻1 劉曉寶.數獨游戲的解題算法J.電腦編程技巧與維護,2007,(5):64- 67.2 嚴蔚敏,吳偉民.數據結構M.第二版.北京:清華大學出版社,1993:93- 95,43- 45,220- 221.3 Stanley B Lippman, Josee Lajoie 著，潘愛民等譯. C+ Primer( 第三版) M. 中 國電力出版社，2002.4 王曉東.算法設計與分析M.第一版.清華大學出版社，2003.5 王萬良.人工智能及其應用M.第二版.高等教育出版社，2008.附 錄預處理算法的主要代碼：while(1)setPossible();if(!fixPossible(sudoku,fix,possible) /即不存在只有一種可能性的位置break;if(isFull(sudoku) /若已推出全部結果break;if(isFull(sudoku)printAll();/輸出結果回溯算法的主要代碼：if(isFull(sudoku)return true;int top=0;/所有值為0的位置入棧for(int