數(shù)獨游戲課程設(shè)計報告

第第頁數(shù)獨游戲課程設(shè)計報告

“數(shù)獨”是18世紀(jì)瑞士數(shù)學(xué)家歐拉發(fā)現(xiàn)。該游戲是在9×9的單元網(wǎng)格中進(jìn)行，這些網(wǎng)格被分9行、9列和3×3個九宮格。單元網(wǎng)格中已有假設(shè)干數(shù)字，其余均為空格。玩家需要推理出全部剩余空格的數(shù)字，并滿意每一行、每一列、每一個小九宮格內(nèi)的數(shù)字均含1-9且不重復(fù)。每一道合格的“數(shù)獨”謎題都有且僅有唯一答案。

目前，“數(shù)獨”作為一種智力游戲已經(jīng)風(fēng)靡世界，國內(nèi)外很多學(xué)者已對數(shù)獨的求解算法做了深入討論，例如遞歸法[1]、回溯候選數(shù)法[2]、枚舉算法[3]等，但在數(shù)獨的難度劃分與創(chuàng)建方面的討論還很少。由于影響“數(shù)獨”難度的因素有許多，就問題本身而言，難度因素包括最高難度的技巧、各種技巧所用次數(shù)、是否有隱蔽及隱蔽的深度和廣度的技巧組合、當(dāng)前盤面可規(guī)律推導(dǎo)出的個數(shù)等等；就玩家而言，了解的技巧數(shù)量、嫻熟程度、觀測力等也屬于難度劃分應(yīng)考慮的因素。因此，單單利用空格數(shù)或求解時間對題目難度進(jìn)行劃分是不全面的，其難度指標(biāo)定義過于主觀，爭論也不夠細(xì)致，無法真正劃分難度的級別。

本文首先創(chuàng)建符合要求的“數(shù)獨”終盤，然后在終盤的基礎(chǔ)上生成具有數(shù)獨特性的初盤，依據(jù)求解時初級方法和高級方法運用的次數(shù)確定難度評分，從而依據(jù)分?jǐn)?shù)對題目的難度進(jìn)行劃分，以此創(chuàng)建不同等級難度的“數(shù)獨”游戲。

1終盤和初盤生成

首先運用初等行、列變換，構(gòu)造一個新的簡約明白的終盤生成算法，詳細(xì)步驟如下：

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

Step2：從列的角度出發(fā)，仍舊以小九宮為單位，把第一個小九宮的第一列的相鄰三個數(shù)字為一個集體進(jìn)行交替，由此獲得第四個小九宮的一列數(shù)字，第一小九宮的第二、三列也通過這個相同的方法而得到第四個小九宮的其他兩列數(shù)字。剩余的其他小九宮也依據(jù)前述相同的方法可以得到，

將已得到的一個終盤，恰當(dāng)隱去某些格子內(nèi)的值，使之成為合乎數(shù)獨規(guī)章的空格，由此便生成一個數(shù)獨謎題，即初盤。此處，我們隱去的.格子的方法是通過概率隨機(jī)隱去相應(yīng)的格子數(shù)，由于我們所創(chuàng)建的終盤是保證唯一性的，所以此處徑直借助終盤來進(jìn)行檢驗初盤的唯一性。

2難度劃分

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

2.1評分模型建立

我們基于仿照人工求解的方式充分運用基本方法，直到基本方法不再起作用時才運用高級方法。因此基于常用的兩個算法―顯性唯一候選數(shù)法和隱含唯一候選數(shù)法，以及高級方法，我們假設(shè)每個玩家對于每一個空格的求解按以下步驟進(jìn)行：

Step1：當(dāng)玩家第一次運用顯性唯一候選數(shù)法能解出數(shù)獨謎題的一個空格，那么轉(zhuǎn)向下一個空格的求解；

Step2：當(dāng)玩家第一次運用顯性唯一候選數(shù)法不能求解時，那么采納隱性唯一候選法，假設(shè)能求解出該空格，那么進(jìn)行下一個空格的求解；

Step3：當(dāng)玩家先后采納顯性唯一候選數(shù)和隱含唯一候選數(shù)法，依舊不能找出答案，這時利用計算機(jī)隨機(jī)自動生成一個空格的答案，稱此方法為高級方法，然后玩家便可以繼續(xù)進(jìn)行下一個空格的求解；

Step4：當(dāng)求出一個數(shù)獨謎題的全部空格值，游戲結(jié)束。

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

Score=αN1+βN2+γN3

由于高級方法比基本方法的難度大，并且對于同一方法，運用2次要比1次的難度大。所以，為了表達(dá)“數(shù)獨”題目運用不同方法及其相應(yīng)次數(shù)的繁復(fù)度，我們給不同的方法加上適當(dāng)?shù)臋?quán)重。本文定義的權(quán)重如下：α=1，β=2，γ=5

對于上述權(quán)重，根據(jù)隨著方法難度系數(shù)遞增權(quán)重遞增的方式以及盡可能運用不同方法間的權(quán)重差異足夠大的原那么進(jìn)行取值。雖然權(quán)重的取值有肯定的任意性，但通過計算機(jī)仿真可以說明這樣能很好的區(qū)分不同難度等級的“數(shù)獨”題目。

2.2計算機(jī)仿真

依據(jù)我們建立的終盤，隨機(jī)產(chǎn)生1200道題目，然后用本文的人工智能算法求解，并記錄不同題目各種方法運用次數(shù)、空格數(shù)以及最終分?jǐn)?shù)。此處，選取部分仿真結(jié)果如表1所示：

由表1所知：評分?jǐn)?shù)涵蓋區(qū)域較大，有些高難度的初盤的score很大，偏離了初盤score的平均值，不便于我們依據(jù)全部初盤的score徑直劃分難度級別，故我們進(jìn)行歸一化，將每個初盤的score歸一到[0，1]范圍內(nèi)，建立公式如下：

其中：a