人工智能完成總結(jié)報(bào)告

精品文檔 1歡迎下載 完成總結(jié)報(bào)告完成總結(jié)報(bào)告 項(xiàng)目名稱 數(shù)獨(dú)游戲設(shè)計(jì)與實(shí)現(xiàn) 組 員 王鄭合 2014204081 欒杰 2014204080 文寬 2014204104 二 二 二 二 年四月二十四日 精品文檔 2歡迎下載 1 問(wèn)題描述 1 1 問(wèn)題說(shuō)明 數(shù)獨(dú)游戲起源于瑞士 由十八世紀(jì)的瑞士數(shù)學(xué)家歐拉發(fā)明 是一種數(shù)字拼 圖游戲 其游戲規(guī)則是 在 9 9 的大九宮格內(nèi) 已給定若干數(shù)字 其他宮位留白 玩家需自己按 照邏輯推敲出剩下的空格里是什么數(shù)字 必須滿足的條件 每一行與每一列都有 1 到 9 的數(shù)字 每個(gè)小九宮格里 也有 1 到 9 的數(shù)字 并且一個(gè)數(shù)字在每行 每列及每個(gè)小九宮格里只能出現(xiàn)一 次 既不能重復(fù)也不能少 每個(gè)數(shù)獨(dú)游戲都可根據(jù)給定的數(shù)字為線索 推算解答出來(lái) 1 2 數(shù)獨(dú)求解描述 由于數(shù)獨(dú)游戲的推廣與普及 在當(dāng)今世界上有著大量的數(shù)獨(dú)愛(ài)好者 本項(xiàng) 目的目的就是按照數(shù)獨(dú)的游戲規(guī)則 通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)的分析和人工智能算法的 研究 利用計(jì)算機(jī)程序來(lái)實(shí)現(xiàn)對(duì)已知數(shù)獨(dú)游戲的快速求解 1 3 數(shù)獨(dú)出題描述 數(shù)獨(dú)游戲挑戰(zhàn)者的水平各異 對(duì)數(shù)獨(dú)題目的難度要求各不相同 所以本項(xiàng) 目致力于設(shè)計(jì)一種算法 使其在盡可能短的時(shí)間內(nèi)生成不同難度等級(jí)的數(shù)獨(dú)題 以滿足不同水平游戲者的需求 同時(shí) 該算法還要考慮到三個(gè)方面要求 可變 化的難度 解的唯一性和算法復(fù)雜度最小化 精品文檔 3歡迎下載 2 功能分析 2 1 數(shù)獨(dú)求解 數(shù)獨(dú)雖然號(hào)稱是數(shù)學(xué)問(wèn)題 但在求解時(shí)幾乎用不上數(shù)學(xué)運(yùn)算方法 事實(shí)上 它更像是一種思維方式 數(shù)獨(dú)游戲開(kāi)始后 要想在空格中填入正確的數(shù)字 先 要根據(jù)數(shù)獨(dú)游戲規(guī)則對(duì)1 9分別進(jìn)行邏輯判斷 然后選擇正確的數(shù)字填入空格 另外 由于某個(gè)格子填入數(shù)據(jù)時(shí) 有可能還要對(duì)原來(lái)已填入的數(shù)據(jù)進(jìn)行修正 所以可以考慮使用遞推和回溯搜索來(lái)求解數(shù)獨(dú)問(wèn)題 2 2 數(shù)獨(dú)出題 出題時(shí) 要能保證算法生成的數(shù)獨(dú)題具有可變化的難度和唯一解 該算法內(nèi) 部應(yīng)該包含有對(duì)數(shù)獨(dú)題的求解和評(píng)級(jí)功能 本項(xiàng)目使用了一種基于 挖洞 思 想的數(shù)獨(dú)題生成算法 將該算法的設(shè)計(jì)工作分為評(píng)級(jí) 求解和生成三部分工作 利用隨機(jī)數(shù)出現(xiàn)的概率不同來(lái)確定不同的難度 通過(guò)避免重填一個(gè)被 挖去 的格子 或者回溯到一個(gè)曾經(jīng)無(wú)法 挖去 的格子 來(lái)降低算法的復(fù)雜性 2 3 題目保存 當(dāng)用戶需要退出卻仍沒(méi)有完成數(shù)獨(dú)題目的解答時(shí) 可以選擇是否保存當(dāng)前 的求解進(jìn)度 如果需要 本系統(tǒng)會(huì)幫助用戶將目前未完成的數(shù)獨(dú)題目的解答進(jìn) 度保存起來(lái) 以便用戶下次使用本系統(tǒng)時(shí) 可以繼續(xù)解答上次未完成的題目 2 4 題目讀取 用戶可以在程序開(kāi)始運(yùn)行后 選則讀取一道之前保存起來(lái)的題目進(jìn)行解答 被讀取的題目將會(huì)顯示到程序界面上 精品文檔 4歡迎下載 3 系統(tǒng)設(shè)計(jì) 3 1 功能結(jié)構(gòu)圖 本程序主要有數(shù)獨(dú)求解和數(shù)獨(dú)出題兩個(gè)功能 數(shù)獨(dú)求解包括題目檢驗(yàn) 解 題和輸入輸出 數(shù)獨(dú)出題包括答案檢驗(yàn) 難度選擇 出題和輸入輸出 精品文檔 5歡迎下載 3 2 業(yè)務(wù)流程圖 3 3 類圖 SudokuDlg 類 程序的界面類 精品文檔 6歡迎下載 Solve 類 實(shí)現(xiàn)數(shù)獨(dú)題目求解功能 Make 類 實(shí)現(xiàn)數(shù)獨(dú)題目出題功能 Pre 類 對(duì)數(shù)據(jù)進(jìn)行預(yù)處理 3 4 界面設(shè)計(jì) 3 5 算法設(shè)計(jì) 3 5 1 數(shù)獨(dú)求解算法 解決該數(shù)獨(dú)求解問(wèn)題時(shí)的要考慮的主要方面有 判斷題目合法性 即驗(yàn)證給出數(shù)據(jù)本身是否符合游戲規(guī)則 行 列以及 小九宮中從不重復(fù)地出現(xiàn)數(shù)字1 9 采用遞推算法 若可以填入數(shù)字則填入數(shù)字 并入棧以便回溯 否則回 溯至前面填入數(shù)字處重新填數(shù) 所有空白處都要填滿數(shù)據(jù) 其中 最重要的就是如何通過(guò)遞推算法填入正確的數(shù)字 或者通過(guò)回溯算 法重新填入數(shù)字并得到最終解 這是本算法的核心內(nèi)容 回溯法是解決數(shù)獨(dú)問(wèn)題的有效方法 有著較快的解題速度 然而一般的常 用的回溯算法仍然有不足之處 比如會(huì)進(jìn)行重復(fù)的運(yùn)算 所以在采用回溯法之 前 還可以利用一點(diǎn)小技巧 以縮短回溯算法的運(yùn)行時(shí)間 甚至可將運(yùn)行時(shí)間 縮短接近于0 這個(gè)小技巧即在回溯算法的基礎(chǔ)上 采用有限遞推算法進(jìn)行預(yù)處 理 精品文檔 7歡迎下載 算法活動(dòng)圖如下 3 5 1 數(shù)獨(dú)出題算法 要想設(shè)計(jì)一個(gè)算法用以生成各種難度等級(jí)的數(shù)獨(dú)題 通過(guò)對(duì)游戲規(guī)則的分 析 首先從三個(gè)方面定義難度等級(jí) 分別是已知格總數(shù) 已知格的分布和窮舉 搜索復(fù)雜度 本算法采用 挖洞 思想 經(jīng)過(guò)以下步驟生成數(shù)獨(dú)題 用隨機(jī)算法生成一個(gè)數(shù)獨(dú)題目 用求解算法生成終盤 根據(jù)難度挖去部分?jǐn)?shù)字 整個(gè)生成數(shù)獨(dú)題的算法分為兩步執(zhí)行 先 利用拉斯維加斯隨機(jī)算法隨機(jī)生成一個(gè)填滿數(shù) 字且符合游戲規(guī)則的終盤 而后根據(jù)所需求的 難度等級(jí)抹去一些數(shù)字 難度等級(jí)由隨機(jī)數(shù)出 現(xiàn)的概率來(lái)決定 算法活動(dòng)圖如下 精品文檔 8歡迎下載 4 系統(tǒng)實(shí)現(xiàn) 4 1 開(kāi)發(fā)平臺(tái) 本項(xiàng)目基于 Visual Studio 2010 平臺(tái)的 MFC 采用 C 語(yǔ)言進(jìn)行開(kāi)發(fā)與測(cè) 試 4 2 運(yùn)行環(huán)境 本項(xiàng)目可在各個(gè)版本的 Win7 系統(tǒng)或者 Windows XP 系統(tǒng)下運(yùn)行 4 3 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ) 組織數(shù)據(jù)的方式 通常情況下 精心選擇的數(shù)據(jù) 結(jié)構(gòu)可以帶來(lái)?yè)碛懈叩倪\(yùn)行或存儲(chǔ)效率的算法 一般認(rèn)為 一個(gè)數(shù)據(jù)結(jié)構(gòu)是 由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來(lái)的 對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述稱為 精品文檔 9歡迎下載 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí) 現(xiàn)形式 是其在計(jì)算機(jī)內(nèi)的表示 數(shù)獨(dú)從形式上看是一個(gè)方陣 十分適合用數(shù) 組來(lái)表示 4 3 1 主要數(shù)組 本項(xiàng)目中所用到的主要數(shù)組有 int sudoku 82 該數(shù)組的用途是存儲(chǔ)題目以及保存最終結(jié)果 所有的9 9個(gè)數(shù)字被依次存儲(chǔ) 在該數(shù)組中 空白處則初始化為0 之所以把數(shù)組范圍設(shè)計(jì)成82 而不是81 是 為了程序的易讀性 使得數(shù)組元素的最大下標(biāo)可達(dá)81 下同 int fix 82 該數(shù)組的用途是若sudoku數(shù)組中某位置的數(shù)字不為空 則fix數(shù)組相應(yīng)位置 的元素值為1 否則為0 即fix數(shù)組是用來(lái)記錄哪些位置的數(shù)字是已經(jīng)確定下來(lái) 的 int possible 82 10 該數(shù)組的用途是記錄所有未確定數(shù)字的所有可能性 possible數(shù)組各元素 的值在初始化時(shí)被初始化為與其第二維的下標(biāo)一致 即0 9 其中0表示空值 在中間計(jì)算過(guò)程中 若發(fā)現(xiàn)第一維某位置的某種可能性已不復(fù)存在 則將第一 維下標(biāo)是該位置而第二維下標(biāo)是該不再可能的數(shù)字的元素值改為 1 int review 82 該數(shù)組的用途類似于棧 在回溯算法過(guò)程中起到至關(guān)重要的作用 回溯之 前 要把所有fix數(shù)組中值為0的位置依次存放進(jìn)review數(shù)組 回溯中 由低到 高依次逐漸確定這些位置的數(shù)值 無(wú)法確定者 即1 9的數(shù)字都不適合者 則應(yīng) 當(dāng)回退到前一個(gè)位置 并修改其fix數(shù)組中的值 依次類推 直至review數(shù)組所 存放的所有位置的值都能確定 即題目完成 或回退到最初點(diǎn)的前一個(gè)位置 即題目有誤 4 3 2 相關(guān)函數(shù) 本項(xiàng)目中為實(shí)現(xiàn)算法的數(shù)據(jù)結(jié)構(gòu)所用到的主要函數(shù)如下 void setPossible 該函數(shù)是用來(lái)設(shè)置 possible 數(shù)組中元素的值 其具體功能是 對(duì)于 fix 數(shù) 組中每一個(gè)值為 0 的位置 即對(duì)于每一個(gè)沒(méi)有確定下數(shù)字的位置 考察其可能 的數(shù)字是哪些 并記錄下來(lái) 考察的方法是 在 1 9 這些數(shù)字中除去在當(dāng)前行 列 九宮中已有的數(shù)字 剩下的即為可能的取值對(duì)象 bool fixPossible 精品文檔 10歡迎下載 該函數(shù)是用來(lái)修改fix數(shù)組和possible數(shù)組中元素的值 其返回值表示了在 此次運(yùn)行該函數(shù)過(guò)程中是否執(zhí)行了修改 其具體功能是 對(duì)于fix數(shù)組中每一個(gè) 值為0的位置 即對(duì)于每一個(gè)沒(méi)有確定下數(shù)字的位置 考察其可能的數(shù)字的個(gè) 數(shù) 若為1 則將fix數(shù)組該位置的值改為1且sudoku數(shù)組該位置的值改為該唯 一可能的數(shù)字 即該位置的值已確定下來(lái) 且返回真 若沒(méi)有只有一種可能性 的位置 則返回假 bool isExist int i int j 該函數(shù)用于回溯過(guò)程中 其用途是 判斷sudoku數(shù)組中位置為i的元素的值 是否可能為j 即判斷的是位置i所在的行 列以及九宮中是否已經(jīng)存在數(shù)字j 若存在則返回真 否則返回假 4 4 求解算法實(shí)現(xiàn) 4 4 1 有限遞推 在執(zhí)行一次fixPossible函數(shù)之后 就可能會(huì)確定下一些原來(lái)沒(méi)有確定的數(shù) 字 那么此時(shí)possible數(shù)組的值必然也會(huì)變動(dòng) 這是因?yàn)榇_定下的數(shù)字越多 某些位置的可能數(shù)字的數(shù)目就會(huì)減少 那么此時(shí)就應(yīng)再執(zhí)行setPossible函數(shù)修 改possible數(shù)組 而修改之后可能又會(huì)出現(xiàn)一些只有一種可能性的位置 那么 就應(yīng)該再執(zhí)行fixPossible函數(shù) 于是 只要如此循環(huán)往復(fù)下去 就能最大限度 地確定下根據(jù)題目本身含義和規(guī)則而確定下的內(nèi)容 確定的數(shù)字越多 對(duì)于將 來(lái)回溯也就越有利 經(jīng)驗(yàn)表明 有些數(shù)獨(dú)題直接就可以通過(guò)執(zhí)行大約10多次的 有限遞推循環(huán)體解決 一般情況下 有限遞推的循環(huán)結(jié)束只有兩種情況 一是 推出了全部結(jié)果 二是fixPossible函數(shù)返回值為假 即不存在只有一種可能性 的位置 預(yù)處理的主要代碼見(jiàn)附錄 4 4 2 回溯 回溯是數(shù)獨(dú)求解算法中最為關(guān)鍵的部分 其主要步驟是 按下標(biāo)的由低到高掃描fix數(shù)組 將值為0的位置記錄進(jìn)review數(shù)組 記 錄的順序也是由低到高 最后記錄下fix數(shù)組中為0位置的個(gè)數(shù)再加1 把review數(shù)組看作棧 記錄棧頂 先設(shè)置一個(gè)bool型標(biāo)志變量flag并初始化為true 下面各步驟都將在一 個(gè)條件始終為真的死循環(huán)中進(jìn)行 該循環(huán)由一條對(duì)flag進(jìn)行真假判斷的語(yǔ)句分 成兩大部分 若當(dāng)前棧頂是經(jīng)過(guò)了回退操作而達(dá)到的 則flag會(huì)已被記錄為 精品文檔 11歡迎下載 false 否則flag為true 死循環(huán)結(jié)束的條件是review數(shù)組 棧 中top與max的 值相等 即解出最終結(jié)果 或者是無(wú)解 最終top小于0 在死循環(huán)中 若flag 為true 則進(jìn)入步驟 否則進(jìn)入步驟 若flag為true 則說(shuō)明棧頂是經(jīng)過(guò)正常的假設(shè)而達(dá)到的 并非由回退達(dá) 到 那么根據(jù)possible數(shù)組以及isExist函數(shù)對(duì)棧頂所保存位置的可能出現(xiàn)的數(shù) 字進(jìn)行判斷 把遇到的第一個(gè)可能數(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)用在棧頂所 保存的位置 則說(shuō)明前面的假設(shè)有錯(cuò)誤 此時(shí)應(yīng)當(dāng)回退 即fix數(shù)組和sudoku數(shù) 組的該位置重設(shè)為0 top減1 并將flag的值設(shè)為false 然后結(jié)束本輪循環(huán)體 繼續(xù)下一輪的循環(huán) 若flag為false 說(shuō)明是經(jīng)過(guò)了回退才達(dá)到現(xiàn)在這個(gè)棧頂?shù)?那么若仍然 沒(méi)有可能的數(shù)字可以應(yīng)用在當(dāng)前棧頂所保存的位置上 則繼續(xù)執(zhí)行出棧操作 即fix數(shù)組和sudoku數(shù)組的該位置的值重設(shè)為0 top減1 否則將遇到的第一個(gè) 可能數(shù)字應(yīng)用到該位置 即再設(shè)好sudoku數(shù)組和fix數(shù)組 將top加1 并將flag 的值設(shè)為true 然后結(jié)束本輪循環(huán)體 繼續(xù)下一輪的循環(huán) 回溯的主要代碼見(jiàn)附錄 4 5 出題算法實(shí)現(xiàn) 4 5 1 生成終盤 數(shù)獨(dú)出題時(shí)要先采用拉斯維加斯算法隨機(jī)生成一個(gè)數(shù)獨(dú)題的終盤 首先 在一個(gè)數(shù)獨(dú)空盤中隨機(jī)選中 n 個(gè)格子 在這些格子內(nèi)隨機(jī)填人數(shù)字 1 9 然后 調(diào)用數(shù)獨(dú)求解算法對(duì)這個(gè)已知 n 格的數(shù)獨(dú)題 S n 進(jìn)行求解 如果 S n 有解 則 返回 true 否則返回 false 拉斯維加斯算法的思想便是不斷重復(fù)執(zhí)行上述步 驟 直至其返回值為 true 為止 生成隨機(jī)數(shù)的主要代碼見(jiàn)附錄 4 5 2 挖洞算法 挖洞算法的基本思想就是挖去一個(gè)數(shù)獨(dú)終盤上的一些格子 使其成為有唯 一解的數(shù)獨(dú)題目 然而挖洞的機(jī)制是多種多樣的 本項(xiàng)目為了加快出題算法的 速度 利用不同的隨機(jī)挖洞概率來(lái)區(qū)分不同的難度 挖洞的主要代碼見(jiàn)附錄 精品文檔 12歡迎下載 4 6 程序運(yùn)行截圖 開(kāi)始 數(shù)獨(dú)求解 手動(dòng)輸入題目 數(shù)獨(dú)求解 讀取保存的題目 解出答案 精品文檔 13歡迎下載 數(shù)獨(dú)出題 選擇難度 得出題目 保存題目 保存和打開(kāi)題目的文件格式 精品文檔 14歡迎下載 5 測(cè)試 5 1 解題測(cè)試 選取 5 個(gè)難度共 25 道不同的數(shù)獨(dú)題目進(jìn)行解題測(cè)試 記錄程序運(yùn)行時(shí)間 檢驗(yàn)運(yùn)算結(jié)果是否正確 并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析 難度 1 題目12345Average 時(shí)間14ms13ms22ms22ms20ms18 2ms 結(jié)果正確正確正確正確正確 難度 2 題目12345Average 時(shí)間21ms20ms20ms33ms21ms23 0ms 結(jié)果正確正確正確正確正確 精品文檔 15歡迎下載 難度 3 題目12345Average 時(shí)間22ms26ms25ms23ms26ms24 4ms 結(jié)果正確正確正確正確正確 難度 4 題目12345Average 時(shí)間28ms24ms35ms29ms26ms28 4ms 結(jié)果正確正確正確正確正確 難度 5 題目12345Average 時(shí)間28ms50ms22ms44ms29ms34 6ms 結(jié)果正確正確正確正確正確 通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析可知 本算法得出的結(jié)果全部正確 說(shuō)明本算法成功實(shí)現(xiàn)了通過(guò)計(jì)算機(jī)人工智 能方法對(duì)數(shù)獨(dú)問(wèn)題求解 隨著題目難度加大 平均運(yùn)行時(shí)間逐漸加長(zhǎng) 本次試驗(yàn)中 運(yùn)行時(shí)間最長(zhǎng)的題目不超過(guò) 50ms 大多數(shù)題目在 20 30ms 內(nèi)完成 說(shuō)明本算法的運(yùn)行速度是比較快捷的 5 2 出題測(cè)試 5 個(gè)難度各進(jìn)行 5 次數(shù)獨(dú)出題運(yùn)算 記錄運(yùn)行時(shí)間 并比較得出的題目是否 會(huì)有重復(fù) 難度 1 題目12345Average 時(shí)間9ms10ms6ms7ms9ms8 2ms 重復(fù) 無(wú) 難度 2 精品文檔 16歡迎下載 題目12345Average 時(shí)間9ms8ms9ms7ms8ms8 2ms 重復(fù) 無(wú) 難度 3 題目12345Average 時(shí)間9ms9ms6ms5ms9ms7 6ms 重復(fù) 無(wú) 難度 4 題目12345Average 時(shí)間10ms9ms8ms6ms11ms8 8ms 重復(fù) 無(wú) 難度 5 題目12345Average 時(shí)間7ms9ms10ms5ms10ms8 2ms 重復(fù) 無(wú) 通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析可知 本此實(shí)驗(yàn)中 各組均無(wú)重復(fù)的題目出現(xiàn) 說(shuō)明本算法成功實(shí)現(xiàn)了通過(guò)計(jì) 算機(jī)人工智能方法對(duì)數(shù)獨(dú)問(wèn)題的出題 程序的運(yùn)行時(shí)間不隨難度增加而加長(zhǎng) 個(gè)難度的運(yùn)行時(shí)間基本一樣 運(yùn)行時(shí)間基本維持著 8 9ms 左右 說(shuō)明本算法的運(yùn)行速度是比較快捷的 6 工作總結(jié) 較好地完成了數(shù)獨(dú)求解和數(shù)獨(dú)出題的算法的設(shè)計(jì)與實(shí)現(xiàn) 對(duì)算法進(jìn)行功能測(cè)試 驗(yàn)證了算法的有效性 并證明了算法具有良好的 精品文檔 17歡迎下載 時(shí)間效率 實(shí)現(xiàn)了良好的用戶界面 實(shí)現(xiàn)了數(shù)獨(dú)題目的讀取和保存功能 通過(guò)本項(xiàng)目 對(duì)人工智能技術(shù)有了進(jìn)一步的了解 并初步掌握了 MFC 編 程 鍛煉了團(tuán)隊(duì)合作能力 7 項(xiàng)目安排 任務(wù)負(fù)責(zé)人時(shí)間 項(xiàng)目建議書(shū)王鄭合 文寬 欒杰 9 19 9 30 數(shù)獨(dú)求解功能王鄭合 欒杰 10 1 10 21 數(shù)獨(dú)出題功能王鄭合 文寬 10 1 10 21 測(cè)試欒杰 10 22 10 23 中期進(jìn)展報(bào)告王鄭合 文寬 欒杰 10 24 10 28 界面文寬 10 29 11 4 功能集成王鄭合 11 5 11 9 測(cè)試與改進(jìn)文寬 欒杰 11 10 11 20 完成總結(jié)報(bào)告王鄭合 文寬 欒杰 11 21 11 25 精品文檔 18歡迎下載 參 考 文 獻(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 著 潘愛(ài)民等譯 C Primer 第三版 M 中 國(guó)電力出版社 2002 4 王曉東 算法設(shè)計(jì)與分析 M 第一版 清華大學(xué)出版社 2003 5 王萬(wàn)良 人工智能及其應(yīng)用 M 第二版 高等教育出版社 2008 附 錄 預(yù)處理算法的主要代碼 預(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 精品文檔 19歡迎下載 所有值為0的位置入棧 for int i 1 i 0 宏定義 用于調(diào)試程序 if flag int j for j 1 j max return 1 b