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

1、數(shù)獨游戲課程設(shè)計報告將“數(shù)獨”智力游戲的難度劃分與創(chuàng)建問題分解為建立終盤和初盤、難度評分、游戲創(chuàng)建。首先采用行列變換的方法建立終盤，然后隱去部分?jǐn)?shù)字并檢驗解唯一性，得到初盤。在已得到初盤的基礎(chǔ)上，根據(jù)求解時初級方法和高級方法使用的次數(shù)確定難度評分，從而依據(jù)分?jǐn)?shù)對題目的難度進(jìn)行劃分，以此創(chuàng)建不同等級難度的“數(shù)獨”游戲。最后通過實驗驗證了模型的實用性。下面是的數(shù)獨游戲課程設(shè)計報告，歡迎來參考！“數(shù)獨”是18世紀(jì)瑞士數(shù)學(xué)家歐拉發(fā)明。該游戲是在9X9的單元網(wǎng)格中進(jìn)行，這些網(wǎng)格被分9行、9列和3X3個九宮格。單元網(wǎng)格中已有若干數(shù)字，其余均為空格。玩家需要推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每

2、一個小九宮格內(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)前盤面可邏輯推導(dǎo)出的個數(shù)等等；就玩家而言，了解的技巧數(shù)量、熟練程度、觀察力等也屬于難度劃分應(yīng)考慮的因素。因此，單單利用空格數(shù)或求解時間對題目難度進(jìn)行劃分是不全面的，其難度指標(biāo)定義過于主觀，討論也不夠細(xì)致

3、，無法真正劃分難度的級別。本文首先創(chuàng)建符合要求的“數(shù)獨”終盤，然后在終盤的基礎(chǔ)上生成具有數(shù)獨特性的初盤，根據(jù)求解時初級方法和高級方法使用的次數(shù)確定難度評分，從而依據(jù)分?jǐn)?shù)對題目的難度進(jìn)行劃分，以此創(chuàng)建不同等級難度的“數(shù)獨”游戲。1 終盤和初盤生成首先運(yùn)用初等行、列變換，構(gòu)造一個新的簡單明了的終盤生成算法，具體步驟如下：Step1：從行的角度出發(fā)，在第一行隨機(jī)輸入1-9的數(shù)字。以一個小九宮為單位，將相鄰三個數(shù)字作為一個集體進(jìn)行交替，由此獲得第二行的數(shù)字，再由第二行的數(shù)字根據(jù)前述方法變換得到第三行的數(shù)字。由此我們得到一個前三行，共有三個小九宮的全部數(shù)字。Step2：從列的角度出發(fā)，仍然以小九宮為單位

4、，把第一個小九宮的第一列的相鄰三個數(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)致了它們的難度不同。因此，我

5、們首先需要依據(jù)這些初盤，建立一個評分模型，得到每個初盤的難度評分值，再根據(jù)這些評分值劃分不同等級的數(shù)獨。2.1 評分模型建立我們基于模仿人工求解的方式充分使用基本方法，直到基本方法不再起作用時才使用高級方法。因此基于常用的兩個算法顯性唯一候選數(shù)法和隱含唯一候選數(shù)法，以及高級方法，我們假設(shè)每個玩家對于每一個空格的求解按以下步驟進(jìn)行：Step1：當(dāng)玩家第一次使用顯性唯一候選數(shù)法能解出數(shù)獨謎題的一個空格，則轉(zhuǎn)向下一個空格的求解；Step2：當(dāng)玩家第一次使用顯性唯一候選數(shù)法不能求解時，則采用隱性唯一候選法，若能求解出該空格，則進(jìn)行下一個空格的求解；Step3：當(dāng)玩家先后采用顯性唯一候選數(shù)和隱含唯一候選

6、數(shù)法，依然不能找出答案，這時利用計算機(jī)隨機(jī)自動生成一個空格的答案，稱此方法為高級方法，然后玩家便可以繼續(xù)進(jìn)行下一個空格的求解；Step4：當(dāng)求出一個數(shù)獨謎題的所有空格值，游戲結(jié)束。假設(shè)N1為基本方法中使用顯性唯一數(shù)法的次數(shù)，N2為基本方法中使用隱性唯一數(shù)法的次數(shù)，N3為使用高級方法的次數(shù)，%,(3,丫分別為不同方法的權(quán)重，從而我們建立一個難度評分模型：Score=%N1+BN2+yN3由于高級方法比基本方法的難度大，并且對于同一方法，使用2次要比1次的難度大。所以，為了體現(xiàn)“數(shù)獨”題目使用不同方法及其相應(yīng)次數(shù)的復(fù)雜度，我們給不同的方法加上適當(dāng)?shù)臋?quán)重。本文定義的權(quán)重如下：=1,(3=2,丫=5對于上述權(quán)重，按照隨著方法難度系數(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)，建立公式如