人工智能項(xiàng)目建議書

項(xiàng)目建議書項(xiàng)目建議書 項(xiàng)目名稱 數(shù)獨(dú)游戲出題與求解設(shè)計(jì) 組 員 李鵬程 吳淵 二 二 二 二 年三月九日 目錄目錄 一 項(xiàng)目說明 2 1 1 整體描述 2 1 2 出題設(shè)計(jì) 2 1 3 求解設(shè)計(jì) 2 二 解決方案 2 2 1 項(xiàng)目分析 2 2 2 求解方案 3 2 3 出題方案 3 2 4 求解方案 4 2 5 開發(fā)平臺(tái) 4 2 6 數(shù)據(jù)結(jié)構(gòu) 4 2 6 1 主要數(shù)組 4 2 6 2 主要函數(shù) 5 2 7 求解算法設(shè)計(jì) 6 2 7 1 有限遞推 6 2 7 2 回溯 6 2 8 出題算法設(shè)計(jì) 7 2 8 1 生成終盤 7 2 8 2 挖洞算法 7 三 方案檢測(cè) 8 四 項(xiàng)目安排 9 參 考 文 獻(xiàn) 9 一 項(xiàng)目說明一 項(xiàng)目說明 1 1 整體描述 數(shù)獨(dú)游戲是一種數(shù)學(xué)方面的游戲 直觀上更像一種拼圖游戲 其游戲規(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ù)字為線索 推算解答出來 1 2 出題設(shè)計(jì) 本項(xiàng)目計(jì)劃設(shè)計(jì)一種算法 在短時(shí)間內(nèi)生成數(shù)獨(dú)題且難度等級(jí)不一致 以 滿足不同水平游戲者的需求 數(shù)獨(dú)游戲挑戰(zhàn)者的水平各異 對(duì)數(shù)獨(dú)題目的難度 要求各不相同 但是有三個(gè)方面需要注意 可變化的難度 解的唯一性和算法 復(fù)雜度最小化 1 3 求解設(shè)計(jì) 本項(xiàng)目的目的就是按照數(shù)獨(dú)游戲的規(guī)則 綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)的分析和人工 智能的算法 利用計(jì)算機(jī)程序來實(shí)現(xiàn)對(duì)已知數(shù)獨(dú)游戲的快速求解 二 解決方案二 解決方案 2 1 項(xiàng)目分析 數(shù)獨(dú)雖然號(hào)稱是數(shù)學(xué)問題 但在求解時(shí)幾乎用不上數(shù)學(xué)運(yùn)算方法 事實(shí)上 它更像是一種思維方式 數(shù)獨(dú)游戲開始后 要想在空格中填入正確的數(shù)字 先 要根據(jù)數(shù)獨(dú)游戲規(guī)則對(duì)1 9分別進(jìn)行邏輯判斷 然后選擇正確的數(shù)字填入空格 另外 由于某個(gè)格子填入數(shù)據(jù)時(shí) 有可能還要對(duì)原來已填入的數(shù)據(jù)進(jìn)行修正 所以可以考慮使用遞推和回溯搜索來求解數(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ù)游戲者需要的難度等級(jí) 我們從已知格的總數(shù)和分布以及窮舉求解 的搜索次數(shù)這三個(gè)方面特性 通過賦權(quán)求和來評(píng)估一個(gè)數(shù)獨(dú)題的難度等級(jí) 然 后 運(yùn)用反證法思想 并結(jié)合深度優(yōu)先搜索求解器一起論證一個(gè) 洞 被 挖 去 后是否能保證該題有唯一解 最后 通過避免重填一個(gè)被 挖去 的格子 或者回溯到一個(gè)曾經(jīng)無法 挖去 的格子 來降低算法的復(fù)雜性 2 2 求解方案 解決該數(shù)獨(dú)求解問題時(shí)的要考慮的主要方面有 從界面或文本讀取數(shù)獨(dú)游戲數(shù)據(jù) 判斷題目合法性 即驗(yàn)證給出數(shù)據(jù)本身是否符合游戲規(guī)則 行 列以及 小九宮中從不重復(fù)地出現(xiàn)數(shù)字1 9 逐個(gè)取得空白處 采用遞推算法 若可以填入數(shù)字則填入數(shù)字 并入棧以便回溯 否則回 溯至前面填入數(shù)字處重新填數(shù) 所有空白處都要填滿數(shù)據(jù) 輸出結(jié)果至屏幕或文件 如此看來 最需要仔細(xì)考慮的就是如何通過遞推算法填入正確的數(shù)字 或 者通過回溯算法重新填入數(shù)字并得到最終解 這個(gè)也就是本項(xiàng)目算法的核心 同時(shí)也是解題的關(guān)鍵 2 3 出題方案 要想設(shè)計(jì)一個(gè)算法用以生成各種難度等級(jí)的數(shù)獨(dú)題 通過對(duì)游戲規(guī)則的分 析 首先從以下三個(gè)方面定義難度等級(jí) 已知格總數(shù) 已知格的分布和窮舉搜 索復(fù)雜度 本算法采用 挖洞 思想 經(jīng)過以下兩步生成數(shù)獨(dú)題 運(yùn)用拉斯維加斯隨機(jī)算法生成一個(gè)終盤 根據(jù)所需要的難度等級(jí)選取一種挖洞順序 制定兩個(gè)約束來控制已知格的分布 通過深度優(yōu)先搜索來求解 從而保證 挖去 一個(gè)數(shù)字后該數(shù)獨(dú)題仍有 唯一解 引入剪枝技術(shù)來避免無效的 挖洞 嘗試 對(duì) 挖好洞 的數(shù)獨(dú)題進(jìn)行等效對(duì)稱變換 以提高游戲題目的多樣性 2 4 求解方案 利用遞推和回溯法完成數(shù)獨(dú)問題求解功能 利用拉斯維加斯隨機(jī)算法 深度優(yōu)先搜索和剪枝技術(shù)完成數(shù)度問題出題 功能 完成界面良好的數(shù)獨(dú)游戲程序 2 5 開發(fā)平臺(tái) 本項(xiàng)目基于 Visual Studio 2010 平臺(tái)的 MFC 采用 C 語言進(jìn)行開發(fā)與測(cè) 試 2 6 數(shù)據(jù)結(jié)構(gòu) 通常情況下 精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來擁有更高的運(yùn)行或存儲(chǔ)效率的 算法 一般認(rèn)為 一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的 對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(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ù)組來表示 2 6 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ù)組是用來記錄哪些位置的數(shù)字是已經(jīng)確定下來 的 int possible 82 10 該數(shù)組的用途是記錄所有未確定數(shù)字的所有可能性 possible數(shù)組各元素 的值在初始化時(shí)被初始化為與其第二維的下標(biāo)一致 即0 9 其中0表示空值 在中間計(jì)算過程中 若發(fā)現(xiàn)第一維某位置的某種可能性已不復(fù)存在 則將第一 維下標(biāo)是該位置而第二維下標(biāo)是該不再可能的數(shù)字的元素值改為 1 int review 82 該數(shù)組的用途類似于棧 在回溯算法過程中起到至關(guān)重要的作用 回溯之 前 要把所有fix數(shù)組中值為0的位置依次存放進(jìn)review數(shù)組 回溯中 由低到 高依次逐漸確定這些位置的數(shù)值 無法確定者 即1 9的數(shù)字都不適合者 則應(yīng) 當(dāng)回退到前一個(gè)位置 并修改其fix數(shù)組中的值 依次類推 直至review數(shù)組所 存放的所有位置的值都能確定 即題目完成 或回退到最初點(diǎn)的前一個(gè)位置 即題目有誤 2 6 2 主要函數(shù) 本項(xiàng)目中為實(shí)現(xiàn)算法的數(shù)據(jù)結(jié)構(gòu)所用到的主要函數(shù)如下 void setPossible 該函數(shù)是用來設(shè)置 possible 數(shù)組中元素的值 其具體功能是 對(duì)于 fix 數(shù) 組中每一個(gè)值為 0 的位置 即對(duì)于每一個(gè)沒有確定下數(shù)字的位置 考察其可能 的數(shù)字是哪些 并記錄下來 考察的方法是 在 1 9 這些數(shù)字中除去在當(dāng)前行 列 九宮中已有的數(shù)字 剩下的即為可能的取值對(duì)象 bool fixPossible 該函數(shù)是用來修改fix數(shù)組和possible數(shù)組中元素的值 其返回值表示了在 此次運(yùn)行該函數(shù)過程中是否執(zhí)行了修改 其具體功能是 對(duì)于fix數(shù)組中每一個(gè) 值為0的位置 即對(duì)于每一個(gè)沒有確定下數(shù)字的位置 考察其可能的數(shù)字的個(gè) 數(shù) 若為1 則將fix數(shù)組該位置的值改為1且sudoku數(shù)組該位置的值改為該唯 一可能的數(shù)字 即該位置的值已確定下來 且返回真 若沒有只有一種可能性 的位置 則返回假 bool isExist int i int j 該函數(shù)用于回溯過程中 其用途是 判斷sudoku數(shù)組中位置為i的元素的值 是否可能為j 即判斷的是位置i所在的行 列以及九宮中是否已經(jīng)存在數(shù)字j 若存在則返回真 否則返回假 2 7 求解算法設(shè)計(jì) 前人的經(jīng)驗(yàn)證明 回溯法是解決數(shù)獨(dú)問題的有效方法 有著較快的解題速 度 然而一般的常用的回溯算法仍然有不足之處 比如會(huì)進(jìn)行重復(fù)的運(yùn)算 所 以在采用回溯法之前 還可以利用一點(diǎn)小小的技巧 以縮短回溯算法的運(yùn)行時(shí) 間 甚至可將運(yùn)行時(shí)間縮短接近于0 這個(gè)小技巧即在回溯算法的基礎(chǔ)上 再采 用有限遞推算法進(jìn)行預(yù)處理 算法的基本框架是 2 7 1 有限遞推 在執(zhí)行一次fixPossible函數(shù)之后 就可能會(huì)確定下一些原來沒有確定的數(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ì)于將 來回溯也就越有利 經(jīng)驗(yàn)表明 有些數(shù)獨(dú)題直接就可以通過執(zhí)行大約10多次的 有限遞推循環(huán)體解決 一般情況下 有限遞推的循環(huán)結(jié)束只有兩種情況 一是 推出了全部結(jié)果 二是fixPossible函數(shù)返回值為假 即不存在只有一種可能性 的位置 2 7 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)行真假判斷的語句分 成兩大部分 若當(dāng)前棧頂是經(jīng)過了回退操作而達(dá)到的 則flag會(huì)已被記錄為 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ù)對(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)用在棧頂所 保存的位置 則說明前面的假設(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 說明是經(jīng)過了回退才達(dá)到現(xiàn)在這個(gè)棧頂?shù)?那么若仍然 沒有可能的數(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) 2 8 出題算法設(shè)計(jì) 整個(gè)生成數(shù)獨(dú)題的算法分為兩步執(zhí)行 先利用拉斯維加斯隨機(jī)算法隨機(jī)生 成一個(gè)填滿數(shù)字且符合游戲規(guī)則的終盤 而后根據(jù)所需求的難度等級(jí)抹去一些 數(shù)字 每抹去一個(gè)數(shù)字就驗(yàn)證一次解的唯一性 如此往復(fù)直至滿足所需的難度 要求為止 最后通過適當(dāng)?shù)牡葍r(jià)對(duì)稱變換后輸出該題 算法的基本框架是 2 8 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 為止 2 8 2 挖洞算法 挖洞算法的基本思想就是挖去一個(gè)數(shù)獨(dú)終盤上的一些格子 使其成為有唯 一解的數(shù)獨(dú)題目 然而挖洞的機(jī)制是多種多樣的 本項(xiàng)目為了加快出題算法的 速度 將貪心算法機(jī)制引入到挖洞算法當(dāng)中 整個(gè)挖洞算法流程中的 5 個(gè)關(guān)鍵 步驟如下 確定挖洞順序 確定挖洞順序即在一個(gè)終盤上 決定哪個(gè)位置的格子先被挖去 哪個(gè)格子 是下一個(gè) 該順序?qū)ι傻念}目中已知格的分布起決定性作用 本項(xiàng)目中選擇 了 3 中有著不同難度效果挖洞順序 由易到難依次是 全盤隨機(jī) 間隔 蛇形 挖洞約束 根據(jù)難度等級(jí)的定義 本項(xiàng)目對(duì)挖洞操作加入兩個(gè)約束來影響已知格的分 布形勢(shì) 第一 已知格數(shù)最多為 81 格 將 1 81 大致均分為 3 個(gè)區(qū)間 對(duì)應(yīng)到 3 個(gè)難度等級(jí) 已知格越少則題越難 若游戲者需要某個(gè)難度的數(shù)獨(dú)題 則在 其對(duì)應(yīng)的區(qū)間內(nèi)隨機(jī)一個(gè)數(shù)作為已知格數(shù)的下界 即當(dāng)挖洞至剩余格數(shù)達(dá)到下 界時(shí)停止 第二 同理 每行 每列剩余的格數(shù)必須多于難度等級(jí)所規(guī)定的下 界 否則禁止此次挖洞操作 每嘗試挖去一個(gè)格子 都要檢驗(yàn)一次挖去該格后 是否與這兩個(gè)約束沖突 一旦沖突則禁止此次挖洞 反證法判斷解的唯一性 借助反證法的思想來隨時(shí)檢驗(yàn)當(dāng)一個(gè)格子中的數(shù)字被挖去后 是否能保證 此題還有唯一的解 剪枝優(yōu)化 通過剪枝優(yōu)化來降低耗費(fèi)在挖洞嘗試中的時(shí)間 等價(jià)變換 為了增加所出題目的多樣性 對(duì)完成以上操作后得到的數(shù)獨(dú)題目進(jìn)行等價(jià) 變換 得到新的數(shù)獨(dú)題目 三 方案檢測(cè)三 方案檢測(cè) 對(duì) A B C 三個(gè)不同難度的已知數(shù)獨(dú)問題 難度 A B C 進(jìn)行多次運(yùn)行 測(cè)試 進(jìn)行定性分析 驗(yàn)證計(jì)算結(jié)果的正確性 記錄并對(duì)比運(yùn)算速度 多次運(yùn)行程序提出數(shù)獨(dú)問題 驗(yàn)證提出的數(shù)獨(dú)問題的合理性 記錄并對(duì) 比運(yùn)算速度 四 項(xiàng)目安排四 項(xiàng)目安排 任務(wù)負(fù)責(zé)人時(shí)間 項(xiàng)目建議書李鵬程 吳淵9 3 9 9 數(shù)獨(dú)求解功能李鵬程 吳淵10 1 10 21 數(shù)獨(dú)出題功能李鵬程 吳淵10 1 10 21 測(cè)試?yán)铢i程 吳淵10 22 10 23 中期進(jìn)展報(bào)告李鵬程 吳淵10 24 10 28 界面李鵬程 吳淵10 29 11 4 功能集成李鵬程 吳淵11