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