數獨遊戲課程設計報告

將“數獨”智力遊戲的難度劃分與創建問題分解為建立終盤和初盤、難度評分、遊戲創建。首先採用行列變換的方法建立終盤，然後隱去部分數字並檢驗解唯一性，得到初盤。在已得到初盤的基礎上，根據求解時初級方法和高級方法使用的次數確定難度評分，從而依據分數對題目的難度進行劃分，以此創建不同等級難度的“數獨”遊戲。最後通過實驗驗證了模型的實用性。下面是小編整理的數獨遊戲課程設計報告，歡迎來參考！

“數獨”是18世紀瑞士數學家歐拉發明。該遊戲是在9×9的單元網格中進行，這些網格被分9行、9列和3×3個九宮格。單元網格中已有若干數字，其餘均為空格。玩家需要推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個小九宮格內的數字均含1-9且不重複。每一道合格的“數獨”謎題都有且僅有唯一答案。

目前，“數獨”作為一種智力遊戲已經風靡世界，國內外許多學者已對數獨的求解算法做了深入研究，例如遞歸法[1]、回溯候選數法[2]、枚舉算法[3]等，但在數獨的難度劃分與創建方面的研究還很少。由於影響“數獨”難度的因素有很多，就問題本身而言，難度因素包括最高難度的技巧、各種技巧所用次數、是否有隱藏及隱藏的深度和廣度的技巧組合、當前盤面可邏輯推導出的個數等等；就玩家而言，瞭解的技巧數量、熟練程度、觀察力等也屬於難度劃分應考慮的因素。因此，單單利用空格數或求解時間對題目難度進行劃分是不全面的，其難度指標定義過於主觀，討論也不夠細緻，無法真正劃分難度的級別。

本文首先創建符合要求的“數獨”終盤，然後在終盤的基礎上生成具有數獨特性的初盤，根據求解時初級方法和高級方法使用的次數確定難度評分，從而依據分數對題目的難度進行劃分，以此創建不同等級難度的“數獨”遊戲。

1 終盤和初盤生成

首先運用初等行、列變換，構造一個新的簡單明瞭的終盤生成算法，具體步驟如下：

Step1：從行的角度出發，在第一行隨機輸入1-9的數字。以一個小九宮為單位，將相鄰三個數字作為一個集體進行交替，由此獲得第二行的數字，再由第二行的數字根據前述方法變換得到第三行的數字。由此我們得到一個前三行，共有三個小九宮的全部數字。

Step2：從列的角度出發，仍然以小九宮為單位，把第一個小九宮的第一列的相鄰三個數字為一個集體進行交替，由此獲得第四個小九宮的一列數字，第一小九宮的第二、三列也通過這個相同的方法而得到第四個小九宮的其他兩列數字。剩餘的其他小九宮也根據前述相同的方法可以得到，

將已得到的一個終盤，恰當隱去某些格子內的值，使之成為合乎數獨規則的空格，由此便生成一個數獨謎題，即初盤。此處，我們隱去的格子的方法是通過概率隨機隱去相應的格子數，由於我們所創建的終盤是保證唯一性的，所以此處直接藉助終盤來進行檢驗初盤的'唯一性。

2 難度劃分

在上面的步驟中，我們完成了由終盤生成初盤的過程。在得到龐大的初盤後，由於每個初盤的空格數、空格位置不同，導致了它們的難度不同。因此，我們首先需要依據這些初盤，建立一個評分模型，得到每個初盤的難度評分值，再根據這些評分值劃分不同等級的數獨。

2.1 評分模型建立

我們基於模仿人工求解的方式充分使用基本方法，直到基本方法不再起作用時才使用高級方法。因此基於常用的兩個算法?顯性唯一候選數法和隱含唯一候選數法，以及高級方法，我們假設每個玩家對於每一個空格的求解按以下步驟進行：

Step1：當玩家第一次使用顯性唯一候選數法能解出數獨謎題的一個空格，則轉向下一個空格的求解；

Step2：當玩家第一次使用顯性唯一候選數法不能求解時，則採用隱性唯一候選法，若能求解出該空格，則進行下一個空格的求解；

Step3：當玩家先後採用顯性唯一候選數和隱含唯一候選數法，依然不能找出答案，這時利用計算機隨機自動生成一個空格的答案，稱此方法為高級方法，然後玩家便可以繼續進行下一個空格的求解；

Step4：當求出一個數獨謎題的所有空格值，遊戲結束。

假設N1為基本方法中使用顯性唯一數法的次數，N2為基本方法中使用隱性唯一數法的次數，N3為使用高級方法的次數，α，β，γ分別為不同方法的權重，從而我們建立一個難度評分模型：

Score=αN1+βN2+γN3

由於高級方法比基本方法的難度大，並且對於同一方法，使用2次要比1次的難度大。所以，為了體現“數獨”題目使用不同方法及其相應次數的複雜度，我們給不同的方法加上適當的權重。本文定義的權重如下：α=1，β=2，γ=5

對於上述權重，按照隨着方法難度係數遞增權重遞增的方式以及儘可能使用不同方法間的權重差異足夠大的原則進行取值。雖然權重的取值有一定的隨意性，但通過計算機仿真可以表明這樣能很好的區分不同難度等級的“數獨”題目。

2.2 計算機仿真

依據我們建立的終盤，隨機產生1200道題目，然後用本文的人工智能算法求解，並記錄不同題目各種方法使用次數、空格數以及最終分數。此處，選取部分仿真結果如表1所示：

由表1所知：評分數涵蓋區域較大，有些高難度的初盤的score很大，偏離了初盤score的平均值，不便於我們依據所有初盤的score直接劃分難度級別，故我們進行歸一化，將每個初盤的score歸一到[0，1]範圍內，建立公式如下：

其中：a是分數中的最小值，b是分數中的最大值。由此，我們得到歸一化後的不同題目的最終評分。由得分按等距間隔劃分成四個區域，而這四個區間就是我們所要求的“數獨”難度級別，分數從小到大地分別記為簡單、中等、高級、骨灰級。