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

報告屬性

報告正文

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

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

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

1 終盤和初盤生成

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

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

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

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

2 難度劃分

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

2.1 評分模型建立

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

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

step2：當(dāng)玩家第一次使用顯性唯一候選數(shù)法不能求解時，則采用隱性唯一候選法，若能求解出該空格，則進行下一個空格的求解；

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

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

假設(shè)n1為基本方法中使用顯性唯一數(shù)法的次數(shù)，n2為基本方法中使用隱性唯一數(shù)法的次數(shù)，n3為使用高級方法的次數(shù)，alpha;，beta;，gamma;分別為不同方法的權(quán)重，從而我們建立一個難度評分模型：

score=alpha;n1 beta;n2 gamma;n3

由于高級方法比基本方法的難度大，并且對于同一方法，使用2次要比1次的難度大。所以，為了體現(xiàn)ldquo;數(shù)獨rdquo;題目使用不同方法及其相應(yīng)次數(shù)的復(fù)雜度，我們給不同的方法加上適當(dāng)?shù)臋?quán)重。本文定義的權(quán)重如下：alpha;=1，beta;=2，gamma;=5

對于上述權(quán)重，按照隨著方法難度系數(shù)遞增權(quán)重遞增的方式以及盡可能使用不同方法間的權(quán)重差異足夠大的原則進行取值。雖然權(quán)重的取值有一定的隨意性，但通過計算機仿真可以表明這樣能很好的區(qū)分不同難度等級的ldquo;數(shù)獨rdquo;題目。

2.2 計算機仿真

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

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

其中：a是分?jǐn)?shù)中的最小值，b是分?jǐn)?shù)中的最大值。由此，我們得到歸一化后的不同題目的最終評分。由得分按等距間隔劃分成四個區(qū)域，而這四個區(qū)間就是我們所要求的ldquo;數(shù)獨rdquo;難度級別，分?jǐn)?shù)從小到大地分別記為簡單、中等、高級、骨灰級。

報告格式怎么寫