人工智能完成總結(jié)報告.doc

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