人工智能完成總結報告.doc

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