數獨游戲設計與源碼

1、數據結構大型作業(yè)實驗報告書 數據結構大型作業(yè)實驗報告書 設計題目： “數獨”游戲設計與求解 設計題目： “數獨”游戲設計與求解 一． 一．題目說明 題目說明 數獨的游戲規(guī)則： 數獨的游戲規(guī)則： 1、在 9×9 的大九宮格內，已給定若干數字，其他宮位留白，玩 的大九宮格內，已給定若干數字，其他宮位留白，玩 家需要自己按照邏輯推敲出剩下的空格里是什么數字。 家需要自己按照邏輯推敲出剩下的空格里是什么數字。 2、 必須滿足的條件：

2、每一行與每一列都有 、 必須滿足的條件：每一行與每一列都有 1 到 9 的數字，每個小 的數字，每個小九宮格里也有 九宮格里也有 1 到 9 的數字， 并且一個數字在每行、 每列及每 的數字， 并且一個數字在每行、 每列及每個小九宮格里只能出現(xiàn)一次，既不能重復也不能少。 個小九宮格里只能出現(xiàn)一次，既不能重復也不能少。 3、每個數獨游戲都可根據給定的數字為線索，推算解答出來。 、每個數獨游戲都可根據給定的數字為線索，推算解答出來。 按照

3、數獨的游戲規(guī)則，用計算機實現(xiàn)已知數獨的求解和數獨題目 按照數獨的游戲規(guī)則，用計算機實現(xiàn)已知數獨的求解和數獨題目的出題。 的出題。 二． 二．數據結 數據結構說明 構說明 數據結構一維數組、二維數組以及類似于“?！钡臄祿Y構。 數據結構一維數組、二維數組以及類似于“棧”的數據結構。 主要操作有：進棧，出棧，棧頂元素的操作等等 主要操作有：進棧，出棧，棧頂元素的操作等等 三． 三．抽象數據類型 抽象數據類型(Abstract Data Ty

4、pe (Abstract Data Type 簡稱 簡稱 ADT) ADT) 五個全局變量數組，其中兩個二維數組，三個一維 五個全局變量數組，其中兩個二維數組，三個一維int stack[82] int stack[82] 類似于“?！睌祿Y構的數組，實現(xiàn)“回溯”算法 類似于“?！睌祿Y構的數組，實現(xiàn)“回溯”算法的關鍵所在?；厮葜?，把所有 的關鍵所在。回溯之前，把所有 fix fix 值為 值為 0 的數據存 的數據存如 sta

5、ck stack 數組中，即進棧?；厮葜兄饾u確定這些位置 數組中，即進棧?；厮葜兄饾u確定這些位置的數值，無法確定者（即 的數值，無法確定者（即 1-- --9 都不適合的）則應回 都不適合的）則應回退到前一位置， 修改其 到前一位置， 修改其 fix fix 值， 以此類推。 直至 值， 以此類推。 直至 stack stack中所有的值都確定下來（即題目完成） ，或者回退到 中所有的值都確定下來（即題目完成） ，或者回退到了最初點的前

6、一位置（說明題目有誤） 。 了最初點的前一位置（說明題目有誤） 。 四． 四．算法設計 算法設計 程序可以考慮人工智能的算法。 所謂人工智能的算 程序可以考慮人工智能的算法。 所謂人工智能的算法，應當是算法設計者對該游戲的特性有較為深入的 法，應當是算法設計者對該游戲的特性有較為深入的了解，依據其內在聯(lián)系設計出的和人類思維相似的解 了解，依據其內在聯(lián)系設計出的和人類思維相似的解決算法。但這似乎太過復雜，所以這里決定采用“回 決算法。但這

7、似乎太過復雜，所以這里決定采用“回溯”的方法解決數獨問題。 溯”的方法解決數獨問題。 基本框架如下： 基本框架如下： 五．數獨程序代碼： 五．數獨程序代碼： #include“stdio.h“ //標準輸入輸出頭文件 標準輸入輸出頭文件 #include“conio.h“ //包含 包含 getch()的頭文件 的頭文件 從界面讀取數 從界面讀取數據 到 據 到a[10][10] a[10][10] 將 a[10][10] a[10][