完成總結報告
專案名稱：數獨遊戲設計與實現
組員：王鄭合 2014204081
欒傑 2014204080
文寬 2014204104
二〇一八年九月二十四日
數獨遊戲起源於瑞士，由十八世紀的瑞士數學家尤拉發明，是一種數字拼圖遊戲，其遊戲規則是：
①在9×9的大九宮格內，已給定若干數字，其他宮位留白，玩家需自己按照邏輯推敲出剩下的空格裡是什麼數字。
②必須滿足的條件：每一行與每一列都有1到9的數字，每個小九宮格裡也有1到9的數字，並且乙個數字在每行、每列及每個小九宮格裡只能出現一次，既不能重複也不能少。
③每個數獨遊戲都可根據給定的數字為線索，推算解答出來。
由於數獨遊戲的推廣與普及，在當今世界上有著大量的數獨愛好者，本專案的目的就是按照數獨的遊戲規則，通過對資料結構的分析和人工智慧演算法的研究，利用電腦程式來實現對已知數獨遊戲的快速求解。
數獨遊戲挑戰者的水平各異，對數獨題目的難度要求各不相同，所以本專案致力於設計一種演算法，使其在盡可能短的時間內生成不同難度等級的數獨題，以滿足不同水平遊戲者的需求。同時，該演算法還要考慮到三個方面要求：可變化的難度、解的唯一性和演算法複雜度最小化。
數獨雖然號稱是數學問題, 但在求解時幾乎用不上數**算方法，事實上它更像是一種思維方式。數獨遊戲開始後，要想在空格中填入正確的數字，先要根據數獨遊戲規則對1-9分別進行邏輯判斷，然後選擇正確的數字填入空格。另外，由於某個格仔填入資料時，有可能還要對原來已填入的資料進行修正，所以可以考慮使用遞推和回溯搜尋來求解數獨問題。
出題時，要能保證演算法生成的數獨題具有可變化的難度和唯一解,該演算法內部應該包含有對數獨題的求解和評級功能。本專案使用了一種基於「挖洞」思想的數獨題生成演算法，將該演算法的設計工作分為評級、求解和生成三部分工作。利用隨機數出現的概率不同來確定不同的難度，通過避免重填乙個被「挖去」的格仔，或者回溯到乙個曾經無法「挖去」的格仔，來降低演算法的複雜性。
當使用者需要退出卻仍沒有完成數獨題目的解答時，可以選擇是否儲存當前的求解進度。如果需要，本系統會幫助使用者將目前未完成的數獨題目的解答進度儲存起來，以便使用者下次使用本系統時，可以繼續解答上次未完成的題目。
使用者可以在程式開始執行後，選則讀取一道之前儲存起來的題目進行解答，被讀取的題目將會顯示到程式介面上。
本程式主要有數獨求解和數獨出題兩個功能，數獨求解包括題目檢驗、解題和輸入輸出，數獨出題包括答案檢驗、難度選擇、出題和輸入輸出。
sudokudlg類：程式的介面類。
solve類：實現數獨題目求解功能。
make類：實現數獨題目出題功能。
pre類：對資料進行預處理。
解決該數獨求解問題時的要考慮的主要方面有：
①判斷題目合法性，即驗證給出資料本身是否符合遊戲規則，行、列以及小九宮中從不重複地出現數字1-9；
②採用遞推演算法，若可以填入數字則填入數字，併入棧以便回溯，否則回溯至前面填入數字處重新填數；
③所有空白處都要填滿資料；
其中，最重要的就是如何通過遞推演算法填入正確的數字，或者通過回溯演算法重新填入數字並得到最終解，這是本演算法的核心內容。
回溯法是解決數獨問題的有效方法，有著較快的解題速度。然而一般的常用的回溯演算法仍然有不足之處，比如會進行重複的運算。所以在採用回溯法之前，還可以利用一點小技巧，以縮短回溯演算法的執行時間，甚至可將執行時間縮短接近於0。
這個小技巧即在回溯演算法的基礎上，採用有限遞推演算法進行預處理。
演算法活**如下：
要想設計乙個演算法用以生成各種難度等級的數獨題，通過對遊戲規則的分析，首先從三個方面定義難度等級，分別是已知格總數、已知格的分布和窮舉搜尋複雜度。
本演算法採用「挖洞」思想，經過以下步驟生成數獨題：
①用隨機演算法生成乙個數獨題目；
②用求解演算法生成終盤；
③根據難度挖去部分數字；
整個生成數獨題的演算法分為兩步執行：先利用拉斯維加斯隨機演算法隨機生成乙個填滿數字且符合遊戲規則的終盤；而後根據所需求的難度等級抹去一些數字，難度等級由隨機數出現的概率來決定。
演算法活**如下：
本專案基於visual studio 2010平台的mfc，採用c++語言進行開發與測試。
本專案可在各個版本的win7系統或者windows xp系統下執行。
資料結構是計算機儲存、組織資料的方式。通常情況下，精心選擇的資料結構可以帶來擁有更高的執行或儲存效率的演算法。一般認為，乙個資料結構是由資料元素依據某種邏輯聯絡組織起來的，對資料元素間邏輯關係的描述稱為資料的邏輯結構；資料必須在計算機內儲存, 資料的儲存結構是資料結構的實現形式， 是其在計算機內的表示。
數獨從形式上看是乙個方陣, 十分適合用陣列來表示。
本專案中所用到的主要陣列有：
①int sudoku[82]
該陣列的用途是儲存題目以及儲存最終結果,所有的9×9個數字被依次儲存在該陣列中，空白處則初始化為0。之所以把陣列範圍設計成82 而不是81，是為了程式的易讀性，使得陣列元素的最大下標可達81，下同。
②int fix[82]
該陣列的用途是若sudoku陣列中某位置的數字不為空，則fix陣列相應位置的元素值為1，否則為0，即fix陣列是用來記錄哪些位置的數字是已經確定下來的。
③int possible[82][10]
該陣列的用途是記錄所有未確定數字的所有可能性，possible陣列各元素的值在初始化時被初始化為與其第二維的下標一致，即0-9（其中0表示空值）；在中間計算過程中，若發現第一維某位置的某種可能性已不復存在，則將第一維下標是該位置而第二維下標是該不再可能的數字的元素值改為-1。
④int review[82]
該陣列的用途類似於棧，在回溯演算法過程中起到至關重要的作用。回溯之前，要把所有fix陣列中值為0的位置依次存放進review陣列；回溯中，由低到高依次逐漸確定這些位置的數值，無法確定者（即1-9的數字都不適合者）則應當回退到前乙個位置，並修改其fix陣列中的值，依次類推，直至review陣列所存放的所有位置的值都能確定（即題目完成），或回退到最初點的前乙個位置（即題目有誤）。
本專案中為實現演算法的資料結構所用到的主要函式如下：
①void setpossible（）
該函式是用來設定possible陣列中元素的值，其具體功能是：對於fix陣列中每乙個值為0的位置（即對於每乙個沒有確定下數字的位置），考察其可能的數字是哪些，並記錄下來。考察的方法是：
在1-9這些數字中除去在當前行、列、九宮中已有的數字，剩下的即為可能的取值物件。
②bool fixpossible（）
該函式是用來修改fix陣列和possible陣列中元素的值，其返回值表示了在此次執行該函式過程中是否執行了修改。其具體功能是：對於fix陣列中每乙個值為0的位置（即對於每乙個沒有確定下數字的位置），考察其可能的數字的個數， 若為1，則將fix陣列該位置的值改為1且sudoku陣列該位置的值改為該唯一可能的數字（即該位置的值已確定下來），且返回真；若沒有只有一種可能性的位置， 則返回假。
③bool i***ist（int i，int j）
該函式用於回溯過程中，其用途是：判斷sudoku陣列中位置為i的元素的值是否可能為j，即判斷的是位置i所在的行、列以及九宮中是否已經存在數字j，若存在則返回真，否則返回假。
在執行一次fixpossible函式之後，就可能會確定下一些原來沒有確定的數字，那麼此時possible陣列的值必然也會變動。這是因為確定下的數字越多，某些位置的可能數字的數目就會減少，那麼此時就應再執行setpossible函式修改possible陣列。而修改之後可能又會出現一些只有一種可能性的位置，那麼就應該再執行fixpossible函式。
於是，只要如此迴圈往復下去，就能最大限度地確定下根據題目本身含義和規則而確定下的內容。確定的數字越多，對於將來回溯也就越有利。經驗表明，有些數獨題直接就可以通過執行大約10多次的有限遞推迴圈體解決。
一般情況下，有限遞推的迴圈結束只有兩種情況：一是推出了全部結果；二是fixpossible函式返回值為假，即不存在只有一種可能性的位置。
預處理的主要**見附錄。
回溯是數獨求解演算法中最為關鍵的部分，其主要步驟是：
①按下標的由低到高掃瞄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陣列以及i***ist函式對棧頂所儲存位置的可能出現的數字進行判斷，把遇到的第乙個可能數字放進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。然後結束本輪迴圈體，繼續下一輪的迴圈。
人工智慧期末總結
1.人工智慧是何時 何地 怎樣誕生的？1956 年夏季，美國的一些從事數學 心理學 電腦科學 資訊理論和神經學研究的年輕學者，匯聚在 dartmouth 大學，舉辦了一次長達兩個月的學術討論會，認真而熱烈的討論了用機器模擬人類智慧型的問題。在這次會議上，第一次使用了 人工智慧 這一術語，以代表有關機...
人工智慧實驗報告
江蘇科技大學 實驗報告 2012 2013學年第2學期 課程名稱人工智慧 學生姓名陳嘉生 學生學號 1040501211 院系數理學院 專業 資訊與計算科學 2013年 5 月 18 日 一 實驗目的 狀態空間表示法是人工智慧領域最基本的知識表示方法之一，也是進一步學習狀態空間搜尋策略的基礎，本實驗...
人工智慧實驗報告
人工智慧 實驗指導及報告書 2011 2012 學年第 1 學期 姓名 張輔祥 學號 090509110 班級 09計科一 指導教師 電腦科學與工程學院 2011 一 實驗目的 1 理解人工智慧中產生式相關知識的基本原理和方法 二 實驗內容 如圖所示放置3根柱子，其中一根從上往下按由小到大順序串有若...